Primorial and faster binomial.

[bodrato at mail.dm.unipi.it]

Ciao!

Il Gio, 19 Aprile 2012 2:23 pm, Torbjorn Granlund ha scritto:
> bodrato at mail.dm.unipi.it writes:
>   The current mpz_primorial_ui function is almost trivial, it sieves all
>   primes up to the given limit (storing the full bit-array), then it

> It seems wasteful to maintain the full bit array, but on 2nd though it
> is small compared to the result, for large N.

Yet, it fits in the result area and is overwritten by it. The result area
is preallocated with an overestimate: N*3/2 bits ...

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]...

>   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.

-- 
http://bodrato.it/papers/