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

本文关键字：栈溢出 堆栈 异常 BigInteger 为什么 | 更新日期: 2023-09-27 18:23:56

我在C#中使用BigInteger和阶乘函数。该程序具有闪电般的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的位数的近似值。这只有143MB，但我仍然得到堆栈溢出异常。为什么会发生这种情况？

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);
    }
}

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

线程的默认堆栈大小为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);

正如loopedcode所说，您应该至少使用迭代算法来计算阶乘。

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

还有更高效的算法（请看这里）。

Factorial的递归调用会导致足够大的调用堆栈出现stackoverflow。你的电话10000！很可能达到这个目标。您可能需要将实现更改为迭代算法来修复溢出。

相关文章：