DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH
 

(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