Actually it does use linear number of multiplications. Computing Factorial in poly-logarithmic time would yield attack for the RSA encryption, as gcd(n, (sqrt(n)! modulo n )) is one of n's divisors.
The only advantage over a naive approach [ which takes Omega((nlog n)^2) ] is that Python's implementation of multiplication of large numbers is o( n^2 ). If we combine that with logarithmic depth of recursion, and the fact that there are 2^i calls at the i-th level of recursion we get running time of:
sum _{i=1} ^ {log n} 2^i * time_of_mul( (n(log n-i)) / 2^i )
Where time_of_mul( x ) is time necessary to multiply to numbers of length x. Above bound comes from the fact that length of x! is roughly xlog x bits.
This sum if one uses FFT-style multiplication can give something like O(n log^3 n )
Utility Mill is another wonderful Blended Technologies project.
copyright, owned and operated by Blended Technologies LLC.