triplecorrelation.com

We all know that convolution and multiplication are Fourier transforms of each other as operations.  It may be less well known that multiplication of numbers is essentially convolution of their digits.  For example, if we multiply “123″ by “321″, the result “39483″ is also obtained by convolving vectors [1,2,3] with [3,2,1].  In MATLAB or Octave, we can see this by

result =  conv([1,2,3],[3,2,1])

We get that “result” is [3,8,14,8,3].   If we scan the vector from right to left and carry any digits in the 10-s or higher places leftward, we get the answer [3,8+1,4,8,3] = [3,9,4,8,3].   

There is really no better way than convolution to multiply large integers, particularly those that exceed the bit depth available for standard arithmetic.  Consider mutiplying ‘123456789′ with ‘987654321′.  In MATLAB, we get

123456789*987654321 = 1.2193e+017

If we instead multiply by convolving the digits with carry, we get the actual result:

 121932631112635269.

 Here is a MATLAB script that implements multiplication of arbitrary length strings. 

function result = multiplystrings(a,b)
% uses convolution to multiply the two strings a and b
% for example
% result = multiplystrings(’123′,’321′)
% gives
% result = ‘39843′;
% This is a great way to multiply large integers
% r kakarala
na = length(a); nb = length(b);

for k = 1:na
anum(k) = a(k)-’0′;
end; % make “a” a vector

for k = 1:nb
bnum(k) = b(k)-’0′;
end; % and “b” as well

resultnum = conv(anum,bnum); % multiply!
nr = length(resultnum);
carry = 0;

for k = nr:-1:1 % convert it back to a string
v = resultnum(k) + carry;
d = rem(v,10); % separate digit and higher place digits
carry = (v-d)/10;  % this handles carries greater than a single digit as well
result(k) = char(d+’0′); %convert back to a character
end;
if (carry > 0)
result = [num2str(carry) result];
end;