GNU Info

(gmp.info)Factorial Algorithm

---

Next: Binomial Coefficients Algorithm Prev: Other Algorithms Up: Other Algorithms

---

Enter node , (file) or (file)node

Factorial
---------

   Factorials n! are calculated by a simple product from 1 to n, but
arranged into certain sub-products.

   First as many factors as fit in a limb are accumulated, then two of
those multiplied to give a 2-limb product.  When two 2-limb products
are ready they're multiplied to a 4-limb product, and when two 4-limbs
are ready they're multiplied to an 8-limb product, etc.  A stack of
outstanding products is built up, with two of the same size multiplied
together when ready.

   Arranging for multiplications to have operands the same (or nearly
the same) size means the Karatsuba and higher multiplication algorithms
can be used.  And even on sizes below the Karatsuba threshold an NxN
multiply will give a basecase multiply more to work on.

   An obvious improvement not currently implemented would be to strip
factors of 2 from the products and apply them at the end with a bit
shift.  Another possibility would be to determine the prime
factorization of the result (which can be done easily), and use a
powering method, at each stage squaring then multiplying in those
primes with a 1 in their exponent at that point.  The advantage would
be some multiplies turned into squares.