c# - 具有非常大阶乘的任意精度算术

Question

这是一道数学题，不是编程才能有用的东西!

我想计算非常大的数的阶乘(10^n，其中 n>6)。我达到了任意精度，这对像 1000! 这样的任务非常有帮助。但它显然会以更高的值死掉(StackOverflowException :))。我不是在寻找直接的答案，而是在寻找有关如何进一步进行的一些线索。

    static BigInteger factorial(BigInteger i)
    {
        if (i < 1)
            return 1;
        else
            return i * factorial(i - 1);
    }
    static void Main(string[] args)
    {
        long z = (long)Math.Pow(10, 12);
        Console.WriteLine(factorial(z));
        Console.Read();
    }

我必须从 System.Numerics.BigInteger 辞职吗？我在想一些在文件中存储必要数据的方法，因为 RAM 显然会用完。优化在这一点上非常重要。那么您会推荐什么？

此外，我需要尽可能精确的值。忘了说我不需要所有这些数字，只需要最后 20 个。

Answer 1

正如其他答案所示，递归很容易被删除。现在的问题是:您能否将结果存储在 BigInteger 中，还是必须使用某种外部存储设备？

您需要存储 n! 的位数大致与 n log n 成正比。 (这是 斯特林近似 的一种弱形式。)所以让我们看看一些尺寸:(请注意，我在这篇文章的早期版本中犯了一些算术错误，我正在此处更正。)

(10^6)! takes order of 2 x 10^6 bytes = a few megabytes
(10^12)! takes order of 3 x 10^12 bytes = a few terabytes
(10^21)! takes order of 10^22 bytes = ten billion terabytes

几兆将适合内存。几 TB 很容易掌握，但您可能需要编写一个内存管理器。百亿太字节需要全世界所有科技公司的综合资源，但这是可行的。

现在考虑计算时间。假设我们每台机器每秒可以执行一百万次乘法运算，并且我们可以以某种方式将工作并行化到多台机器上。

(10^6)! takes order of one second on one machine
(10^12)! takes order of 10^6 seconds on one machine = 
                     10 days on one machine = 
                     a few minutes on a thousand machines.
(10^21)! takes order of 10^15 seconds on one machine = 
                        30 million years on one machine =
                        3 years on 10 million machines
                        1 day on 10 billion machines (each with a TB drive.)

所以 (10^6)!在你的掌握之中。 (10^12)!你将不得不编写你自己的内存管理器和数学库，你需要一些时间才能得到答案。 (10^21)!你将需要组织世界上所有的资源来解决这个问题，但这是可行的。

或者您可以找到另一种方法。