Fast binomial function
Torbjorn Granlund
tg at gmplib.org
Mon Feb 8 13:55:32 CET 2010
"peter.luschny" <peter.luschny at googlemail.com> writes:
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.
Good! While GMP 5.0.1 often use much less memory than GMP 5.0.0, we
still have work to do in the memory greed area.
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.
Actually, not much work in this area has happened yet. I have thought
about what to do, algorithm-wise ad implementation-wise, but not done
any serious coding.
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].
Excellent! This is a very welcome contribution to the GMP project!
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.
Nice! But surely you will call our multiply functions, where we will
make up for any memory you saved. :-)
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.
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
These are impressive numbers.
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),
Would you be willing to work on that, or at least identify any issues?
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.
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).
The GMP project needs some paperwork for contributions such as yours.
Please see http://www.gnu.org/licenses/why-assign.html for some
background information. The code contributed will then be released
under "LGPL 3 or later". I suggest that we handle this off-list.
--
Torbjörn
More information about the gmp-discuss
mailing list