为什么这个BigInteger值会导致堆栈溢出异常？C#

Question

我使用BigInteger在C#与阶乘函数连接.该程序闪电般快速计算5000!,但在10000时出现溢出错误!根据wolfram alpha,10000!是约

10000!= 2.8 x 10 ^ 35659

从我在这篇文章中可以看出,BigInteger存储在一个int[]数组中.如果我int正确解释类型,它使用4个字节,意味着10000!使用大约4 x log10(2.8 x 10^35659) = 142636字节,我使用log10(n)(日志到基数10)作为n的位数的近似值.这只有143 MB,但我仍然得到堆栈溢出异常.为什么会这样？

using System;
using System.Numerics;

class Program
{
    static void Main()
    {
        BigInteger hugeFactorial = Calculations.Factorial(5000);
    }
}

class Calculations
{
    public static BigInteger Factorial(int n)
    {
        if (n == 1) return n;
        else return n*Factorial(n - 1);
    }
}

Answer 1

线程的默认堆栈大小为1 MB.您可以在创建新线程时更改它.我会把你的代码编写为(不阻塞调用线程):

TaskCompletionSource<BigInteger> tcs = new TaskCompletionSource<BigInteger>();
var t = new Thread(() => 
    {
        var res = Calculations.Factorial(10000);
        tcs.SetResult(res);
    }, 
    1024*1024*16 //16MB stack size
);
t.Start();
var result = await tcs.Task;
Console.Write(result);

Answer 2

正如循环代码所说,你应该使用至少迭代算法来计算阶乘.

public static BigInteger Factorial(int n)
{
    BigInteger result = 1;
    for (int i = 2; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

有更高效的算法(请看这里).

Answer 3

Factorial对于足够大的调用堆栈，递归调用会导致 stackoverflow。您拨打10000！很可能会达到这个目标。您可能必须将实现更改为迭代算法才能修复溢出。