Why does this BigInteger value cause a stack overflow exception? C#

Question

I am using BigInteger in C# in connection with the factorial function. The program has a lightning fast calculation of 5000!, but has an overflow error at 10000!. According to wolfram alpha, 10000! is approximately

10000! = 2.8 x 10^35659

From what I can tell from this post, a BigInteger is stored in an int[] array. If I interpret the int type correctly, it uses 4 bytes, meaning that 10000! uses about 4 x log10(2.8 x 10^35659) = 142636 bytes, where I use log10(n) (the log to base 10) as an approximation to the number of digits of n. This is only 143 MB, but I still get a stack overflow exception. Why does this happen?

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

@IvanStoev yes, Stack overflow exception. It says: "An unhandled exception of type 'System.StackOverflowException' occurred" Let me correct my post. — HowDoICSharply
– HowDoICSharply, Commented Nov 21, 2015 at 22:42
You just answered you question. Do you see a word "BigInteger" in the exception? Do you see a word "stack"? Which code is using stack? — Ivan Stoev
– Ivan Stoev, Commented Nov 21, 2015 at 22:53
Goes wrong on x64 jitter, it needs 208 bytes of stack space for the method. 5000 x 208 == kaboom, the stack size is 1MB. You'll have to write an iterative version instead of the recursive one you have now. A for(;;) loop. — Hans Passant
– Hans Passant, Commented Nov 21, 2015 at 22:54
I looked at the machine code. 208 is specific to RyuJIT, the x64 jitter included with VS2015. It uses AVX instructions, makes it more stack hungry. Otherwise a detail, the code can be bombed arbitrarily by making the argument large enough. — Hans Passant
– Hans Passant, Commented Nov 21, 2015 at 23:18

Eser · Accepted Answer · 2015-11-21 23:15:59Z

9

Default stack size for threads is 1 MB. You can change it while creating a new thread. I would write your code as(without blocking the calling thread):

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

edited Nov 21, 2015 at 23:15

answered Nov 21, 2015 at 22:54

Eser

12.6k2 gold badges24 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Community · Accepted Answer · 2017-05-23 12:18:30Z

7

As loopedcode said you should use at least iteration algorithm to calculate factorial.

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

There are even more efficient algorithms (look here).

edited May 23, 2017 at 12:18

CommunityBot

11 silver badge

answered Nov 21, 2015 at 23:04

ApceH Hypocrite

1,11312 silver badges28 bronze badges

Comments

loopedcode · Accepted Answer · 2015-11-21 22:42:10Z

5

Recursive call of Factorial results in stackoverflow for a large enough call stack. Your call for 10000! is likely hitting that mark. You will probably have to change your implementation to iterative algorithm to fix overflow.

answered Nov 21, 2015 at 22:42

loopedcode

4,9131 gold badge24 silver badges22 bronze badges

1 Comment

HowDoICSharply Over a year ago

Ok, thank you. I didn't know of this "call stack", but from what I can understand, the bound on the call stack is not some intrinsic property of my computer, but rather a parameter in C# that I can change.

Collectives™ on Stack Overflow

Why does this BigInteger value cause a stack overflow exception? C#

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related