Double factorial and primorial

Torbjorn Granlund tg at
Fri Dec 23 15:55:37 CET 2011

bodrato at writes:

  When I wrote my sieve, I used to compute the sum of all primes up-to a
  given limit to measure the time required for sieving and looping. As a
  side effect, you also obtain a checksum, to avoid trivial mistakes :-)
Clever. :-)  I pipe the result to the sha1 command.  And yes, I have had
a bug or two.

Do you have a timing point for your code on shell?  My code now needs
0.9 s on shell for the limit 10^9.  The siever is still somewhat slow, I
have done nothing to improve it with unrolling or clever loop indexing.
(It needs 4 cycles per strobe, whereas one cycle should be possible for
most sieving.  Fixing that, I expect to reach 0.5 s while still using
a single heap.)

I had had some fun night-hacking the new code, but I am not sure it will
be useful for your binom code.  I *hope* to:

1. Unify the two current prime sievers
2. Make a good prime sieving interface in GMP, possibly exported
3. Make gmp_nextprime (or its generalised offspring, as per (2)) run
   much faster.

Perhaps your sieving code should be used, perhaps mine, perhaps some


More information about the gmp-devel mailing list