Friday, January 19, 2007

Calculating n!

One can calculate n! with n-1 multiplications and n-1 additions.

But one can also do so with about n/2 multiplications and n additions. How is this possible?

Also, does anybody know an even better way?

6 comments:

Anonymous said...

There is an overview of algorithms for factorial at http://www.luschny.de/math/factorial/FastFactorialFunctions.htm. Wikipedia has some references at http://en.wikipedia.org/wiki/Factorial#Computation.

Andres said...

Anonymous,

I went through the first link, but the listed algorithms do not seem to have links to anywhere.

Split-recursive multiplication works very well, it begins being faster than naive multiplication at about 190!. For 10,000 factorial, it is about 10 times faster already.

The factorials I would like to calculate do not quite allow prime factorization because the integer range is huge.

However, it is interesting to mention that I did not see references to the method behind my post :)... so the exercise is still not solved!

Thanks,
Andres.

Andres said...

Update: I found a reference to the method that caused me to post this exercise.

However, it must be implemented poorly because it is stated that doing that will be ~1.5x slower than split-recursive.

That is not what I observe in my implementation. In fact, it should not even be slower to begin with. How come more multiplications take less time? It does not make a lot of sense.

What I see here is that, if anything, the method behind this exercise can be a *tiny* bit faster than split recursive.

Thanks,
Andres.

lvovin said...

Induction.

We need to multiply n(n-1)(n-2) ... 2.

We can calculate n(n-1) - one multiplication and addition.

Then we need to obtain n(n-1)(n-2)(n-3).

n(n-1) = n^2 - n
(n-2)(n-3) = n^2 - 5n + 6

So if we have the former, then we can obtain the latter by adding c = -4n + 6. This value can be obtained on each step inductively by subtracting 8.

So to calculate n(n-1)(n-2)(n-3) we need to perform the following operations:

1. n^2 - one multiplication
2. n^2 - n - one addition
3. (n^2 - n) + (-4n + 6) - one addition
4. (n^2 - n) * ((n^2 - n) + (-4n + 6)) - one mul, on subsequent steps the first (n^2 - n) should be replaced with previous result of step 4.
5. (-4n + 6) - 8 - one addition for the next induction step

So we have 2 multiplications and 3 additions for four factorial components. Plus initially we should calculate -4n + 6.
So the upper bound for operations is n / 2 multiplications and n additions.

Anonymous said...

Concerning the first comment:

> I went through the first link, but the listed algorithms
> do not seem to have links to anywhere.

There is a link to both C# and Java source code for all the algorithms in the lower part of the page:
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
This page also has statistics on the number of arithmetic operations performed. Other links on the page lead to comparisons and benchmark results for various algorithms.

Andres said...

Ivovin,

That is very interesting indeed! What I did was something very similar. If you start with

n(n-1)...2

Then you can select k := n + 1 // 2, and rewrite

(k+j)(k+j-1)...k...(k-j+1)(k-j)

Of course if n is even you can't select an individual k in the middle, but dealing with that is trivial.

So now, you can multiply by peeling the onion from the outside. The first pair of factors is

(k+j)(k-j)

Which conveniently reduces to

k^2-j^2

The next pair of factors is

(k+j-1)(k-j+1)

Which again conveniently reduces to

k^2-(j-1)^2

But k^2 you had from before... and as you can see now, you will have to calculate all squares from 1 to j. This, however, you can do without multiplication because the sum of the first j odd integers is j^2. So you keep a running total and a variable for the next odd integer and you are set.

Therefore, to calculate n!, we have to calculate (essentially) n/2 square differences.

The square k^2 only needs to be calculated once. The n/2 squares of j can be calculated with 2*n/2 = n additions (one for k^2-j^2, one for the next odd integer, times n/2 squares of j).

What is left is to multiply together essentially n/2 factors, for which we can delegate matters to split recursive again.

Thus, n/2 multiplications and n additions to calculate n!. I hope you like it :).

Thanks,
Andres.