SuperPi@home 高精度计算内核测试程序

count

楼主的程序时间复杂度是 O(n^2) 的。这可太不好了。

count

更精确的程序时间复杂度应是 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秒.
数据更大时，差距将极其明显。

hackerboy

感谢count的提示。此程序确实没用FFT算法，将在下一版中加入。

satellite

下载不了，为什么呢？

hackerboy

确实下载不了了。你需要的话我可以发给你。也可以看这里，我把他嵌如网页http://hackerboygn.91x.net/Pi.htm

satellite

能发给我吗？[email protected] 谢谢

hackerboy

<B>以下是引用<I>satellite</I>在2004-10-20 14:14:12的发言：</B>
<P>能发给我吗？[email protected]
<P>谢谢

<P>
<P>请收邮件。没发对的话请到
<P>http://www.equn.com/ofs/job.php?action=download&amp;fid=1&amp;tid=16&amp;download=1_16_1084537888.rar%2CSuperPi%40home.rar%2C0%2C0%2Czip
<P>http://www.equn.com/ofs/read.php?fid=1&amp;tid=16&amp;fpage=2
<P>下载，不过要先注册！

[此贴子已经被作者于2004-10-20 18:48:52编辑过]