Marco Bodrato bodrato at
Thu Nov 19 08:21:45 UTC 2015


Il Ven, 13 Novembre 2015 9:00 pm, Torbjörn Granlund ha scritto:
> Well, my code is somewhat larger.  I didn't write this for publication,
> but to explore some algorithm teaks for fast sieving.

I stole the 105-table idea from your code, translating it into a 70-bit
pattern for current code in GMP, to pre-sieve by 5 and 7.
We may try a strategy or-ing two patterns, to pre-sieve also by 11 and 13.

Il Ven, 13 Novembre 2015 6:43 pm, Jerome BENOIT ha scritto:
> For timing, you may also consider primesierve:

After a couple of naive timing tests, that code seems 2-3 times faster
than current code in GMP (a few hundred lines of code only: ).
The speed of prime-sieving has little impact on the speed of the library.

Of course, if someone wants to hint some faster sieving strategy that fits
in a thousand lines of code, it will be welcome!



More information about the gmp-discuss mailing list