大数加减想明白了,但乘除不是很懂
以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