Double factorial and primorial
Torbjorn Granlund
tg at gmplib.org
Wed Dec 21 16:29:39 CET 2011
nisse at lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund <tg at gmplib.org> writes:
> For primes < 2*S, we sieve as usually, i.e., good old Eratosthenes. For
> primes > 2*S we insert the squares in a minheap.
One could do a kind of unified way. Use a current block (bitmap). Get
the smallest element from the heap (p and a multiple of p), mark it in
thee bitmap, and continue to mark larger multiples (like good old
Erathostenes). When you get a multiple beyond the end of the current
block, put that back into the heap.
It is certainly possible to handle all primes, also those < 2*S
with the heap.
I am suggesting this structure
for i = 0 ... Pi(2*S)
p = primevec[i].p
s = primevec[i].off
while s < S
sieve[s] = 1;
primevec[p].off = s - 2*S
while true
p,off = pop(heap)
if (off >= s0 + 2*S)
break
sieve[off - s0] = 1;
I.e., two non-nested loops. By deparating primes into those < 2*S and
thos larger, the 2nd loop above will not need any inner loop.
> Representation is not clear. Perhaps 19 bits for the heap keys, that
> would alloow for the remaining 45 bits to be used by the prime.
I'm not sure what you mean by heap key. As far as I understand, the
primary elements in the heap (used for the sorting) would be multiples
of the primes, and I doubt these will fit in 19 bits). And then for each
multiple, we also need to know what the prime is. I imagine it would be
well sufficient with two arrays, one with 64-bit elements for the
multiples (the heap), and one with 32-bit array used for indexing the
list of primes (swapped together with the heap elements), but there's
room for more cleverness.
I meant 19 bits for the primes, 45 bits for the offsets. But it should
be better to use 1/3 of the bits for the primes, 2/3 for the offsets.
The "heap key" to use is the offsets. 64 bits should suffice for
prime+offset.
--
Torbjörn
More information about the gmp-devel
mailing list