Primorial and faster binomial.

Torbjorn Granlund tg at
Fri Apr 20 10:14:48 CEST 2012

bodrato at writes:

  Yet, it fits in the result area and is overwritten by it.

Such small overhead is impressive!

  The result area is preallocated with an overestimate: N*3/2 bits ...

Now I am less impressed.  :-)
  Not storing the full bit-array is a possible improvement for bin_uiui:
  current code computes (and stores) the full array for the interval [5..N],
  then it uses only [5..N/2] and (in the next step) [N-K..N]...

So for K != N/2 we compute a few extra primes?  If N is really huge and
K is small but not too small for your current thresholds, then this
might be a problem.
  >   The current code uses the basecase below an hard-coded threshold on K,
  >   and anytime K < N/16. Tuning, and a deeper analysis are needed.
  > Have you measured the worst-case factor between the time of this
  > approach and the best function?  Perhaps it is tiny.
  No, I didn't, but I fear it can be big.

I suppose we should make some measurements.  I prefer to have slowdown
by incorrectly choosing the basecase method than incorrectly choosing
the sophisticated method, since then the sophisticated method is never
actually harmful.


More information about the gmp-devel mailing list