我很好奇,并将越来越大的阶乘插入到 Wolfram alpha 中作为阶乘。例如,I calculated 10,000!
。这是2.846... x 10<sup>35659</sup>
!
我检查了他们的代码解释,看来他们将所有整数存储在一个数组中,并对它们执行某种算法。我很好奇是否有人可以扩展这是什么算法,或者它的代码或伪代码实现是什么样子。
最佳答案
对于大整数算术,目标是同时减少必须对大整数进行的运算次数,并尽可能高效地执行基本运算(求和、除法、乘积等)。
对于阶乘,有许多可用的算法可以减少必须进行的乘法次数(例如递归方法)。此外,乘法是使用可用的最佳算法完成的,按大小递增的顺序通常是:
基本乘法 --> karatsuba --> Tom-Cook --> Schönhage–Strassen 算法
一种算法优于另一种算法的精确大小尚不清楚,并且通常是机器敏感的。
话虽这么说,凡事都有其限度。这是 (10^i) 的时序输出!在 Mathematica 中计算 i 从 1 到 8。
Table[Timing[(10^i)!][[1]], {i, 1, 8}]
{0.000011, 0.00002, 0.000028, 0.000911, 0.015209, 0.20903, 3.99917, 58.9894}
更新:正如我所怀疑的,Wolfram 使用 GMP 进行一些大整数运算。
http://library.wolfram.com/infocenter/Conferences/7518/Macalester_talk.txt
关于algorithm - 计算器(例如 Wolfram alpha)如何计算极大的阶乘?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41192036/