function fastmult
% multiply two numbers using FFT
A = 12341234;
B = 567800;

% The algorithm looses precision for large numbers in base 10
base = 3;

% rewrite A, B as digits
a = digits(A,base);
b = digits(B,base);

n = max(length(a),length(b));
N = 2^( ceil(log2(2*n+1)) );

aN=zeros(1,N);
bN=zeros(1,N);
aN(1:length(a))=a;
bN(1:length(b))=b;

% cN is then a convolution of aN and bN
% thus is contains the "digits" of the product between A&B
cN=real(ifft(fft(aN).*fft(bN)));
C =number(cN,base);

fprintf('Relative error: abs(A*B-C)/abs(A*B)=%e\n',abs(A*B-C)/abs(A*B));

% represent D as a sequence of digits
function d = digits(D,base)
assert(D>0 && base>0 && mod(D,1)==0 && mod(base,1)==0);
d = [];
while D > 0,
    d = [d,mod(D,base)];
    D = floor(D/base);
end

% compute number from its digits representation
function D = number(d,base)
D=sum(d.*base.^(0:length(d)-1));