Double factorial and primorial

Torbjorn Granlund tg at gmplib.org
Thu Dec 22 06:49:19 CET 2011


I implemented a variant where all primes live in the heap, perhaps
exactly what Niels suggested.

It is just proof-of-concept code, and the initial prime table is made
naively using trial division.  After that, there is no division or
multiplication.

This code computes all primes < 10^9 in 2s (on a Phenom II 3.2 GHz).
That is about 40 times faster than the current gmp_nextprime code.

The comparison is quite unfair, since the new code has no "nextprime"
interface.  It also uses 100 times more memory.

95% of the time is spent in heap_remove, unsurprisingly.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ehsieve.c
Type: application/octet-stream
Size: 3835 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20111222/f26f16d0/attachment.obj>
-------------- next part --------------

-- 
Torbj?rn


More information about the gmp-devel mailing list