% Given two strings representing non-negative integers, find their sum
% Assume the input strings are named s1 and s2 and the output string is s3
%
% Algorithm: 
%   repeat the following, starting with the least significant digit: 
%      convert the ith digits of s1 and s2 to numbers, add, add a carry
%      convert the least significant digit of the sum to a character
%      and insert into the answer as the ith digit.  Save the carry for
%      the next sum.  If there is a carry at the end, stick it on the
%      front of s3.
function s3 = addBigInt(s1,s2);

if length(s1) < 1 & length(s2) < 1 s3 = '0';  % if s1,s2 == [] answer = 0
elseif length(s1) < 1 s3 = s2;        % if s1 == [] then s2 is the answer
elseif length(s2) < 1 s3 = s1;        % if s2 == [] then s1 is the answer
else
   carry = 0;                         % define the carry
   s3 = '';                           % define the answer
   dh = max(length(s1),length(s2));   % maximum number of digits to worry about

   % From least significant digit, change digit chars to numbers, add with
   % carry to get new carry and new digit, convert new digit back to char
   % and stick into solution.  If a number runs out of digits, use 0.
   for i=1:dh
      if i <= length(s1) n1 = s1(length(s1)+1-i)-'0'; else n1 = 0; end 
      if i <= length(s2) n2 = s2(length(s2)+1-i)-'0'; else n2 = 0; end
      n = n1 + n2 + carry;            % add the ith digits of s1, s2 and carry
      carry = floor(n/10);            % save the carry
      s3 = [char(mod(n,10)+'0') s3];  % compute the answer digit
   end
   
   % If there is a carry at the end, change to char and stick it at front 
   if carry > 0 s3 = [char(carry+'0') s3]; end
end