大数乘除怎么实现？

Question

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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