How does a calculator (such as wolfram alpha) calculate extremely large factorials?

Question

I was curious, and plugged increasingly large factorials into wolfram alpha as factorials. For example, I calculated 10,000!. This is 2.846... x 1035659!

I checked out their code interpretation, and it appears they store all of the integers in an array and perform some sort of algorithm on them. I'm curious if anyone could expand what algorithm this is, or what a code or pseudocode implementation of this would look like.

Answer 1

For large integer arithmetic the goal is to simultaneously reduce the number of operations you have to make on your big integers as well as perform your basic operations (sums, divisions, products, etc.) as efficiently as possible.

In the case of factorials there are many algorithms available which can reduce the number of multiplications one has to make (a recursive approach for example). Further, the multiplication is done using the best algorithms available which in order of increasing size is usually:

basic multiplication --> karatsuba --> Tom-Cook --> Schönhage–Strassen algorithm

The precise size where one algorithm becomes better than another is not well known and is usually machine sensitive.

That being said everything has its limit. Here is an output of the timing of (10^i)! computed in Mathematica for i from one to eight.

Table[Timing[(10^i)!][[1]], {i, 1, 8}]
{0.000011, 0.00002, 0.000028, 0.000911, 0.015209, 0.20903, 3.99917, 58.9894}

update: As I suspected, Wolfram uses GMP for some of it's big integer operations.

http://library.wolfram.com/infocenter/Conferences/7518/Macalester_talk.txt