Double factorial and primorial

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> Sieving bits (not bytes) there would help, since the sieving accounts
> for 0% of the time.

[...]

> Even if bit fiddling would make that part 10 times slower, it will still
> be hard to measure.

Then I imagine it would be good to use Marco's layout, with one bit for
each number equal to ±1 (mod 6). (The Erathostenes code I wrote a while
ago uses the easier representation of one bit per odd number).

> One idea I had was to split the heap in to a bunch of heaps, say 64.
> The current sieving code would then use a heap at a time, separately.
> One may put a prime in any heap, no intelligent criteria are needed.

So you get lower depth, and better locality. The larger number the
beter, until you have so many that a significant proportion of them will
have all elements beyond the end of the current sieving block.

One trick: Use the least few bits of the prime to select which heap it
goes into, then you don't new to allocate any space for those bits in
the heap elements. Could even make a big difference for the 32-bit case,
where I think a 20 bit offset and 10 bit prime is a bit too small for
the range we want to be able to sieve.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.