16.7.2 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.

This document was generated on February 16, 2012 using texi2html 5.0.