Primorial and faster binomial.

[Torbjorn Granlund]

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