Primorial and faster binomial.
Torbjorn Granlund
tg at gmplib.org
Fri Apr 20 10:14:48 CEST 2012
bodrato at mail.dm.unipi.it 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.
--
Torbjörn
More information about the gmp-devel
mailing list