Continue from the last article on factorial.
The final state after GMP's factorial algorithm's preparation can be expressed with this formula:
[possibly wrong. Tested with a few numbers and the result seems to be right]
According to this formula, there suppose to be around
n/2 + log^2 n/3 multiplications. Θ(n), but suppose to be faster than pure binary split + FFT multiplication because there are lesser multiplication involved.From the ideal chain multiplication for 3 positive integers article, we can conclude the order of multiplication does not have a huge effect on the time complexity, but the amount of multiplication does.
I say this should be the fastest method factorial can get without prime factorization.
Prime Factorization method
We know that every number can be expressed as a multiple of some power of some primes.
12 = 2^2 * 3
The factorial can be expressed in the same way.
10! = 2^8 * 3^4 * 5^2 * 7
Nice equations below 
The 2nd equation are simply products of all the largest power of prime p dividing n! Which was found by Legendre.
The 3rd and the 4th equation are some improvement to the equation in order to reduce the calculations for the logs.
In these equations, there are a few things await for clarification, π(n) is the prime-counting function. P with subscript k means the kth prime number. g^(k) (x) means recursively call this function to work on it's returning value k times. for example, g^(3)(x) = g(g(g(x))).
The last equation, with the least usage of log,π(√n). If we keep expanding like to π(n^1/k), we can eliminate more logs. But here, for convenience, let's not consider that.
What is the algorithm like and how efficient will this algorithm be?
- Find all the prime numbers between 3 to n
- create an array a1 with all the primes between 3 to √n
- create an array a2 with all the prime numbers between √n to n/2
- create an array a3 with all the prime numbers between n/2 to n
//end of preparation.
- use binary split method to calculate the product of all numbers in a3
- use binary split method to calculate the product of all numbers in a2 and squares it
- calculate the power for each prime in the array a1, and record them in array e1
- find a method to calculate multi-exponentiation, chose one to calculate the product of a1 with their respective exponents from e1.
- multiply the result from 5, 6 and 8.
- find number 2's exponents, say, x, then add x binary zeros after the result from 9
Clues about it's time complexity
- Find all the primes between 0 to n with the fastest algorithm known, sieve of Atkin, have a time complexity of O(n/log log n).
- There are around n/ln n primes between 0 to n
- the highest exponent (the exponent for 2) is converging toward n when n->∞
- The amount of multiplication expected after preparation are n/ln n + O(log n) = O(n/log n) multiplications.
As you can see, this algorithm is fairly obvious, even though I figured it out by myself, but it's certain someone before me have found it before. If you know who that was, please leave a comment so I can give credit to him. 
I can't compare this to the speed of the fastest known factorial method, Prime Swing Luschny . Unless I can understand how those swing numbers are generated.
Bookmark/Search this post with:
.
Or you could get rid of the
Or you could get rid of the logarithms altogether, check eq. (5) of the Factorial entry at Mathworld.
http://mathworld.wolfram.com/Factorial.html
nice. it is going to use the
nice. it is going to use the digit sum function, I will look into it later :)
Edit:
I can't find a efficient algorithm for digit sum, looks like still have to use logs
Swing numbers
swing(n) = n! / (n/2)!^2
(which is not a binomial factor at least for odd n). i got this from reverse engineering of this:
private final LargeInteger recFactorial(int n)
{
if (n < 2) return LargeInteger.ONE;
return recFactorial(n / 2).square().multiply(swing(n));
}
from http://www.javajungle.de/math/factorial/SrcJava/FactorialSwing.html
thx, that could be helpful
thx, that could be helpful on understanding why prime swing is fast or how it works.
Post new comment