MATLAB 大數乘法

一、模擬大數乘法

輸入是用字元串表示的乘數與被乘數，輸出也需要轉化為字元串。

思路是用數組的每個元素表示每一位的數，乘數與被乘數每一位都相乘，對應值再相加，最後for循環處理進位。

function re = simuMultiply(a,b)
A = a - 0;
B = b - 0;
D = arrayfun(@(k) sum(diag(rot90(A*B),k)),(1-numel(b)):(numel(a)-1));
for ii = length(D):-1:2
D(ii-1) = D(ii-1) + floor(D(ii)/10);
D(ii) = mod(D(ii),10);
end
re = [int2str(D(1)) cast(D(2:end)+0,char)];
end

二、卷積演算法

卷積的概念這裡就不解釋了，每一位對應相乘後對應相加的意義恰好與卷積相通。

function re = convMultiply(a,b)
D = conv(a - 0,b-0);
for ii = length(D):-1:2
D(ii-1) = D(ii-1) + floor(D(ii)/10);
D(ii) = mod(D(ii),10);
end
re = [int2str(D(1)) cast(D(2:end)+0,char)];
end

三、FFT快速演算法

根據頻域相乘等於時域卷積的原理，可以用FFT演算法實現卷積。事實上，MATLAB中的卷積就是用FFT實現的。

function re = fftMultiply(a,b)
A = a - 0;
B = b - 0;
D = ifft(fft([zeros(size(B)) A]).*fft([zeros(size(A)) B]));
for ii = length(D):-1:2
D(ii-1) = D(ii-1) + floor(D(ii)/10);
D(ii) = mod(D(ii),10);
end
re = [int2str(D(1)) cast(D(2:end-1)+0,char)];
end

四、速度比較

a = randi([0,9],[1,1e5]);
a = num2str(a,%d);
b = randi([0,9],[1,1e5]);
b = num2str(b,%d);

%% 10000位×10000位乘法
tic;simuMultiply(a,b);toc
% Out of Memory,內存不足，無法計算
tic;convMulitply(a,b);toc
% 時間已過 0.260405 秒。
tic;fftMultiply(a,b);toc
% 時間已過 0.053287 秒。

總結：模擬計算的方法中間結果太多，內存佔用大。卷積與FFT的方法佔用內存小，速度相近，但總的來說，直接使用FFT更快。

推薦閱讀：