Exact fast factorial computation

141 Views Asked by At

For calculating a power, i.e. $a^b$, well-known fast algorithm exists, based on bitwise decomposition of $b$ and sequential squaring of $a$. Are there similar fast algorithms for calculating a factorial? Most fast factorial algorithms I found focus on optimal reordering of variable-complexity bigint multiplications, but not on reducing the number of bigint operations. The only one I found reduces multiplications twice using a recurrent way of evaluating the sequence $A_n=n\times(N+1-n)$, of course by the price of using several additions instead of a multiplication. Is it possible to calculate $N!$ using $O(\log N)$ operations, are there such algorithms?