algorithm - 计算器(例如 wolfram alpha)如何计算极大的阶乘？

Question

我很好奇，并将越来越大的阶乘作为阶乘插入到 wolfram alpha 中。例如，I calculated 10,000! .这是 2.846... x 10<sup>35659</sup> !

我检查了他们的代码解释，他们似乎将所有整数存储在一个数组中，并对它们执行某种算法。我很好奇是否有人可以扩展这是什么算法，或者它的代码或伪代码实现是什么样的。

Answer 1

对于大整数运算，目标是同时减少必须对大整数进行的运算次数，并尽可能高效地执行基本运算(求和、除法、乘积等)。

在阶乘的情况下，有许多可用的算法可以减少必须进行的乘法次数(例如递归方法)。此外，乘法是使用可用的最佳算法完成的，按大小递增的顺序通常是:

基本乘法 --> 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