首页 > 大数乘除怎么实现?

大数乘除怎么实现?

大数加减想明白了,但乘除不是很懂


以2位数为例
(a*10+b) * (c*10+d) = (a*c)*100 + (a*d+c*b)*10 + b*d
剩下的无非就是不大数乘法不大数加法进位了。


乘法基本就是他们说的那样
除法看这里。。
http://picks.logdown.com/posts/197262-polynomial-division


http://www.jjj.de/fxt/fxtbook.pdf 你可以看看这个文档,算是对各种计算最全的了,其中28章有快速计算大数乘法的算法,跟楼上的描述差不多。


要实现O(NlogN)的大数乘法,使用“快速傅里叶变换”(FFT),或者变种“快速数论变换”(FNTT),两者实现和性能差不多,各有优劣和适用情景。原理呀,维基百科上就有,但看懂需要不低的数学基础。算法实现起来也相对复杂,不过核心部分也就30行C++左右。其它算法如什么KR的,都无法达到O(NlogN),但可以和FFT/FNTT混合着用从而突破位数限制。

实现大数乘法后,用牛顿迭代法将除法转换为乘法,时间复杂度同样是O(NlogN)。

[夹带私货]我曾写过一文介绍圆周率计算方法,含基于快速傅里叶变换的大数乘法、除法、开方的算法介绍,有点长就不贴来了,外链一下:

http://www.guokr.com/blog/444081/


推荐一个有意思的相乘算法:阿拉伯乘法,解决大整数相乘问题。https://github.com/qiwsir/algorithm/blob/master/big_int.md

【热门文章】
【热门文章】