Primorial and faster binomial.
Torbjorn Granlund
tg at gmplib.org
Thu Apr 19 14:23:55 CEST 2012
bodrato at mail.dm.unipi.it writes:
I pushed some new code in the main repository:
- a prime-factor-based implementation for the binomial,
- a new function to compute the primorial.
Very nice!
Both are based on the bit-wise prime-sieve I wrote for the factorial,
that's why I moved it in the main directory, it is now called
gmp_primesieve, but this name might be a bad idea, since it does not use
the gmp_primesieve_t type...
The gmp_primesieve_t stuff will be replaced, perhaps with your new stuff
or some variant of it.
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
produces a list of limb-sized factors and calls mpz_prodlimbs. It
implements one of the possible definitions of primorial(N): product of
primes <= N, NOT the product of the N smaller primes...
It seems wasteful to maintain the full bit array, but on 2nd though it
is small compared to the result, for large 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.
There still are a lot of duplicated tables, macros and small functions,
that should be shared among fac_ui, bin_uiui, primorial_ui...
We can clean that up in due time. It is nice to have this new code in
place!
--
Torbjörn
More information about the gmp-devel
mailing list