Buy GNU books!
|[ < ]||[ > ]||[ << ]||[ Up ]||[ >> ]||[Top]||[Contents]||[Index]||[ ? ]|
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.
|webmaster donations bookstore||delorie software privacy|
|Copyright © 2003 by The Free Software Foundation||Updated Jun 2003|