Calculate factorials in C#

Question

How can you calculate large factorials using C#? Windows calculator in Win 7 overflows at Factorial (3500). As a programming and mathematical question I am interested in knowing how you can calculate factorial of a larger number (20000, may be) in C#. Any pointers?

[Edit] I just checked with a calc on Win 2k3, since I could recall doing a bigger factorial on Win 2k3. I was surprised by the way things worked out.

1. Calc on Win2k3 worked with even big numbers. I tried !50000 and I got an answer, 3.3473205095971448369154760940715e+213236

2. It was very fast while I did all this.

The main question here is not only to find out the appropriate data type, but also a bit mathematical. If I try to write a simple factorial code in C# [recursive or loop], the performance is really bad. It takes multiple seconds to get an answer. How is the calc in Windows 2k3 (or XP) able to perform such a huge factorial in less than 10 seconds? Is there any other way of calculating factorial programmatically in C#?

Answer 1

Have a look at the BigInteger structure:

http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx

Maybe this can help you implement this functionality.

CodeProject has an implementation for older versions of the framework at http://www.codeproject.com/KB/cs/biginteger.aspx.

Answer 2

If I try to write a simple factorial code in C# [recursive or loop], the performance is really bad. It takes multiple seconds to get an answer.

Let's do a quick order-of-magnitude calculation here for a naive implementation of factorial that performs n multiplications. Suppose we are on the last step. 19999! is about 2¹⁸ bits. 20000 is about 2⁵ bits; we'll assume that it is a 32 bit integer. The final multiplication therefore involves the addition of up to 2⁵ partial results each roughly 2¹⁸ bits long. The number of bit operations will therefore be on the order of 2²³.

That's for the last stage; there will be 20000 = 2¹⁶ such operations at each stage, so that is a total of about 2³⁹ operations. Some of them will of course be cheaper, but we're going for an order of magnitude here.

A modern processor does about 2³² operations per second. Therefore it will take about 2⁷ seconds to get the result.

Of course, the big integer library writers were not naive; they take advantage of the ability of the chip to do many bit operations in parallel. They're probably doing the math in 32 bit chunks, giving speedups of a factor of 2⁵. So our total order-of-magnitude calculation is that it should take about 2² seconds to get a result.

2² is 4. So your observation that it takes a few seconds to get a result is expected.

How is the calc in Windows 2k3 (or XP) able to perform such a huge factorial in less than 10 seconds?

I don't know. Extreme cleverness in exploiting the math operations on the chip probably. Or, using a non-naive algorithm for calculating factorial. Or, possibly they are using Stirling's Approximation and getting an inexact result.

Is there any other way of calculating factorial programmatically in C#?

Sure. If all you care about is the order of magnitude then you can use Stirling's Approximation. If you care about the exact value then you're going to have to compute it.