Fast binomial function

[peter.luschny]

Hi all,

yesterday I saw 5.0.1 released. Congrats.

I can assert that some tests with large factorial or
binomial values which failed under 5.0.0 on my system
with two gigas ram with 'out of memory' now do run.

Functions like the binomial functions have not yet
a 'fast' implementation. I am aware that at least one
person of the GMP team is working to improve the situation.
On the other hand these new implementations are not yet
included in the 5.0.1 release.

So it might be useful for some people to have a fast solution
in the meantime. Therefore I offer an implementation of
a fast factorial and a fast binomial function [1].

My implementation of the binomial function is based on
P. Goetgheluck, Computing Binomial Coefficients,
American Math. Monthly 94 (1987), 360-365.

However, the implementation pays special attention to
the memory consumption. In fact it uses only PrimePi(n)
longs. As far as I know there is no mention in the
literature to a binomial algorithm with this feature.

The speedup is remarkable. For some input values the
binomial function is several hundred or even several
thousand times faster than the 5.0.* equivalents.

Cheers Peter

Testing binomial: 400000,133333
ParallelBinomial: 0.015 sec
PrimeBinomial:    0.026 sec
GMP5Binomial:     4.938 sec

Testing binomial: 1600000,533333
ParallelBinomial: 0.078 sec
PrimeBinomial:    0.125 sec
GMP5Binomial:    91.063 sec

Testing binomial: 6400000,2133333
ParallelBinomial:    0.422 sec
PrimeBinomial:       0.610 sec
GMP5Binomial:     1733.750 sec

P.S. The sources also include some experimental parallel
implementations which make use of the boost library.
It is easy to exclude them if you not want them.
Caveat: The functions are not tested to the extend
library functions are supposed to be tested. Please
contact me by private email if you notice a problem.

[1] http://www.luschny.de/math/factorial/fastbinomialandfactorial.zip