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

I say this should be the fastest method factorial can get without prime factorization.

Prime Factorization method
We know2 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?

1. Find all the prime numbers between 3 to n
2. create an array a1 with all the primes between 3 to √n
3. create an array a2 with all the prime numbers between √n to n/2
4. create an array a3 with all the prime numbers between n/2 to n

//end of preparation.

5. use binary split method to calculate the product of all numbers in a3
6. use binary split method to calculate the product of all numbers in a2 and squares it
7. calculate the power for each prime in the array a1, and record them in array e1
8. find a method to calculate multi-exponentiation, chose one to calculate the product of a1 with their respective exponents from e1.
9. multiply the result from 5, 6 and 8.
10. find number 2's exponents, say, x, then add x binary zeros after the result from 9

Clues about it's time complexity

1. 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).
2. There are around n/ln n primes between 0 to n
3. the highest exponent (the exponent for 2) is converging toward n when n->∞
4. 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 Luschny3 . Unless I can understand how those swing numbers are generated.

1. 1. The speed gain from binary split came from the change of algorithm and the order, but not the order alone.
2. 2. if you don't...why are you reading this...?
3. 3. proven by the benchmark from Peter Luschny's site

Factorial algorithms are the main topic I'm working on from 2 months ago. A lot interesting founds.
The naive algorithm was discussed in a previous post.
This post will introduce a new way to find the factorials. The algorithm used in GMP was described briefly in the manual.

The first step is to find out all the 2 factors. I don't know how exactly GMP would do that. Divide all the number have the potential of having 2s? find how many binary zeros in the end of the number and remove them? Could be any of those.

Second step is to collect up the terms. Which will result some possible powers like (3*5)^3.

Third step is to multiple everything inside each term, using binary split method that is nice in chain multiplication.

Some of my analysis result.
1. All odd number except 1 will be a factor.
2. There will be around floor(base 2 log(n)) terms when finding the factorial of n

Considering binary splitting multiplication will take the most of the time because it contains n/2 multiplications. The process suppose to run at O(n log(n)^3) when used with FFT based multiplication according to mathematical constants and computations site's description on binary splitting. I guess the GMP one could run faster because factor 2 is out and exponentiation by squaring further increase the speed.

According to my previous post about chain multiplication of 3 numbers, it's certain the most naive top to bottom recursive factorial algorithm that times itself by n*(n-1)*(n-2)...*2 is slower than the bottom to top 2*3*4....*n.
This post is about the proof of the concept.

T(n) as the time complexity of top to bottom multiplication for n!
B(n) as the time complexity of bottom to top multiplication for n!
The relationship can be presented like this

How do we compare these two values? calculate those 2 functions from 1 to 10000 does show B(n) is faster and grow slower. It is good evidence, still it's not a proof. Let's work on the proof now.
Take off those floor function and the + 1, these have to little significance on the growth. Change log to general log instead of base 2 log. Easier on writing and the properties of each express will hold. Because all log functions have the same logarithmic growth rate. And in this general log, it's not possible to have a number lesser than one since there is a + 1 in the expression we can't see.

Suddenly, the entire expression became easier. It doesn't take a genius to see that:
in the B(n),
log k logarithmically increases
log((k-1)!) = increases at lesser than linearlogarithmic rate but faster than linear rate.
e^n < n! < n^n
n < log(n!) < log(n^n)
n < log(n!) < n log n

In T(n), log(n!/(n-k)!) is increasing and log(n-k) is decreasing
log(n!/(n-k)!) increases like log((k-1)!)
log(n-k) decreases logarithmically

T(n) might actually smaller than B(n)!
Let's put everything inside one log.

Now, we can take off this log sign. Why? because log is a continuous increasing function. so the relationship between both summations is still the same without the log. This same technique can be applied to the log in the exponents. Notice I have removed the B(n) and T(n). B(n) and T(n) are not approximate to the 2 expression right now, but each expression still corresponds to the same greater or lesser relationship between B(n) and T(n).

Now, because I don't have the most amazing brain in the world, I will do some cheat...
I removed the bases, only leave the exponents!
The growth of the exponents is WAY faster than the base(factorial growth VS linear growth), it's ok to ignore the base.
Note I have also changed the first expression's k's initial value to 1.
So everything come down to this comparison

n! is equal to n*(n-1)!, because the 2nd expression got a n!, it is greater than the 1st expression. so calculate factorial by multiply from 2 to n is faster than n to 2.
More rigor proof is required if I want to publish a paper...