winxos 发表于 2010-2-16 10:48:10

请教一下大数优化问题

今日对自己写的大数做了一些测试，发现速度比郭老大以及GMP库要慢的非常的多，
用硬乘来实现100000！GMP库用了58s，我采用C++静态数组做用了240s左右，采用vector动态分配来做用了330s，
对于vector的速度比数组访问要慢一些这个我可以理解，
我采用的一亿进制，用int数组类型来存放，大数乘法采用的模拟手算，
我听说采用FFT来做乘法大概只有25%左右的提速，但是我的时间却是GMP的4倍以上，
不知道到底是框架本身就不一样呢还是哪些优化的地方没有做好？
下面是我的vector的一个版本：
http://hi.baidu.com/ncutlw/blog/item/2ec3163b26dd7de115cecba8.html

liangbch 发表于 2010-2-19 12:05:52

简单的看了一下，你的算法大概相当于我的 大数阶乘值计算从入门到精通中的入门篇二,算法上有待改进。
为了改进速度，基本上有2个方法：
1.采用多位数乘以多位数的乘法来代替一位乘以多位的乘法，而且尽量使得相乘的2个数尽可能位数相当。
2.采用更加有效的大数乘法，根据不同的运算规模，可使用硬乘法，Karatsuba算法，Toom-Cook算法。

winxos 发表于 2010-2-19 18:37:38

2# liangbch
谢谢liang老大指点，
不过看起来要提速的话，还需要学很多东西呢。

gxqcn 发表于 2010-2-20 08:06:15

浏览了一遍楼主的代码，提几个小建议：
1、最好新增平方函数，尤其是你有指数运算时；
2、尽量减少返回一个临时类，比如 a=b*c，它将存在一个潜在的拷贝过程；
3、指数运算有待优化，仅仅“loglen = log((double)b)/(log(2.0f)-1e-6)” 这条语句将浪费不少时钟。

winxos 发表于 2010-2-20 12:09:14

浏览了一遍楼主的代码，提几个小建议：
1、最好新增平方函数，尤其是你有指数运算时；
2、尽量减少返回一个临时类，比如 a=b*c，它将存在一个潜在的拷贝过程；
3、指数运算有待优化，仅仅“loglen = log((double) ...
gxqcn 发表于 2010-2-20 08:06 http://bbs.emath.ac.cn/images/common/back.gif
谢谢郭大指点，
我怎么感觉速度差别那么大不紧紧是那些细节造成的？
好几倍的速度差异总是觉得很难理解。
所谓的平方函数是说专门针对平方来写一个函数因为平方相对乘法简单一些？
临时变量的问题我也只是知道这个东西，平时没有想过可以去减少这个临时变量的使用，自己不知道这些细节到底会造成多大的累积时间消耗？
对于指数运算我采用动态规划来（二分）做了一个，速度大概快了一倍左右，就是内存消耗大了一些。
再次谢谢郭大和liang大，我会继续努力的。
页: [1]
查看完整版本: 请教一下大数优化问题