Fast binomial function

[peter.luschny]

Hi Torbjorn!

> >  So it might be useful for some people to have a fast solution...

> These are impressive numbers.

Yes and no. The algorithms they compare are in different weight classes.
It is more a warning how easily naive implementations can fail if things
grow large. In some respect the challenge of Paul Zimmermann was more
instructive. It showed that there are differences in the 'non-naive' class
worth to study.

> We need to pay attention to the performance of small operands too, to
> make sure we at least do not get slowdown in some range.  If the new
> code is slower for such operands, we need to setup algorithm selection
> with a cutoff point (for factorial) and a cutoff line (for binomial),

> If the code is slower under a certain n for n-factorial, we could
> hopefully write something simple for smaller n.  The current code is
> awfully complex, so hopefully we will not need to keep it.  If we in the
> process can speed up the operation for small n compared to today's GMP
> code, even better.

I do not think this will be too hard. The new code is amazingly simple and
straightforward, the only overhead small input will experience is the setup
of the prime sieve. Therefore I rewrote the simple sieve today and made it
faster about 1.5 - 1.8 times. (For large n this is of no importance because in
the long run the time spent with Eratosthenes will be swallowed by the big O.)

> Would you be willing to work on that, or at least identify any issues?

I think I am not well prepared for this.

> Algorithm selection is probably harder for binomial, since we now have
> to choose algorithm from two parameters, n and k (where we can assume k
> <= n/2).

Well, on the other hand the prime factoring approach flattens things out
in some way and makes the influence of n predominant. No, I think the
structure of the prime factorisation of the binomial does not call for much
attention to this question.

What I am looking at now is the best way to use parallel computing for
combinatorial functions. My next goal is to compute the factorial of 10^9
with about 4000[dd/ms] (decimal digit per millisecond) [1] on a personal
computer at the end of this year.

Cheers Peter

[1] http://www.luschny.de/math/factorial/FactorialDigits.html
(((FactorialDigits(9)/4000)/1000)/60) = 35.69043968 min