在我的空闲时间,我正在准备面试问题,例如:实现乘以数字数组的数字.很显然,我不得不把它从划痕像语言写Python或Java,所以像"使用GMP"的答案是不能接受的(这里所说:了解Schönhage-Strassen的算法(巨大的整数乘法)).
对于range那两个数字的大小(即数字位数),我应该选择
Schönhage-Strassen O(n log n log log n)总是一个很好的解决方案吗？维基百科中提到,Schönhage-Strassen的建议超越的数字2^2^15来2^2^17.怎么办时,一个号码是可笑的巨大(例如10,000,以40,000十进制数字),但第二只包含几个数字的？
所有这4种算法是否容易并行化？
您可以浏览 GNU 多精度算术库的源代码并查看它们在算法之间切换的阈值。
更务实的是，您应该只分析算法的实现。GMP 在优化方面投入了大量精力，因此他们的算法将具有与您不同的常数因子。这种差异很容易使阈值移动一个数量级。找出代码输入大小增加时时间交叉的位置，并相应地设置阈值。
我认为所有算法都适合并行化，因为它们主要由分而治之的过程组成。但请记住，并行化是另一件事，它会使阈值发生很大的变化。