Fast binomial function

[Torbjorn Granlund]

"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