(gmp.info.gz) Factorial Algorithm
Info Catalog
(gmp.info.gz) Prime Testing Algorithm
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Binomial Coefficients Algorithm
Factorial
---------
Factorials are calculated by a combination of removal of twos,
powering, and binary splitting. The procedure can be best illustrated
with an example,
23! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23
has factors of two removed,
23! = 2^19.1.1.3.1.5.3.7.1.9.5.11.3.13.7.15.1.17.9.19.5.21.11.23
and the resulting terms collected up according to their multiplicity,
23! = 2^19.(3.5)^3.(7.9.11)^2.(13.15.17.19.21.23)
Each sequence such as 13.15.17.19.21.23 is evaluated by splitting
into every second term, as for instance (13.17.21).(15.19.23), and the
same recursively on each half. This is implemented iteratively using
some bit twiddling.
Such splitting is more efficient than repeated Nx1 multiplies since
it forms big multiplies, allowing Karatsuba and higher algorithms to be
used. And even below the Karatsuba threshold a big block of work can
be more efficient for the basecase algorithm.
Splitting into subsequences of every second term keeps the resulting
products more nearly equal in size than would the simpler approach of
say taking the first half and second half of the sequence. Nearly
equal products are more efficient for the current multiply
implementation.
Info Catalog
(gmp.info.gz) Prime Testing Algorithm
(gmp.info.gz) Other Algorithms
(gmp.info.gz) Binomial Coefficients Algorithm
automatically generated byinfo2html