更精确的程序时间复杂度应是 O（(n log n)^2） (log 以2为底)
这说明了一个严重的问题：
hackerboy的程序中的乘法函数是用的“经典”方法。
就是类似于以下代码（C语言, invBas是进位制的倒数）
void Mul(long*a, long Asize, long*b, long Bsize,
long*c, long Csize);
{ long i, j, carry=0;
double tmp;
Csize=Asize+Bsize;
for (i =0; i<Bsize; i++)
{
for (j = 0; i<Asize; j++)
{
tmp=a[j]*b[i]+carry
carry=(long)(tmp*invBas)
c[i+j]+=(long)(tmp-carry*Bas)
}
}
if c[Asize+Bsize]=0 then Csize--;
return 0;
}
有一句话说的好：当n大时，O(n^2)的汇编程序 不如O(n)的Basic程序。
因此我建议楼主改用 FFT 乘法。这样其时间复杂度可降为 O(n(logn)^2)。
比如说，原来计算 5000 位要5秒,计算 10000 位要23秒。
设改进后计算 5000 位也要5秒,则计算 10000 位只要11秒.
数据更大时，差距将极其明显。
