about prime number generation

[Adrien Prost-Boucle]

Hi,

Given the relatively small range of numbers involved,
999999999990000 to 1000000000000000,
the Miller-Rabin primality test is deterministic with the right set of bases.
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases

I tested with an old personal 64b implementation.
On my laptop, it takes 6 ms to find the 268 primes in that range.
Other interest is that there is no memory allocation.

Other algorithms or implementations could be faster.
But for short ranges, the segmented sieving approach is not that great.
Enumerating primes up to sqrt(1000000000000000) = 31622776
takes around 4 seconds on my laptop (personal code).
So that is probably where most time is spent with segmented sieve.

Regrads,
Adrien


On Sat, 2022-06-04 at 11:39 +0200, Marco Bodrato wrote:
> Ciao,
> 
> Il 2022-06-01 22:18 Hans Åberg ha scritto:
> > > On 1 Jun 2022, at 12:54, John Gatrell <gatrelljm at gmail.com> wrote:
> > > On the other hand if you could invent a segmented version of Atkin, 
> > > that would change everything.
> > 
> > There is a program using Atkin by Bernstein from 1999:
> > http://cr.yp.to/primegen.html
> > 
> > This link says there is a segmented version in section 5 of the
> > original Atkin/Bernstein  paper. It is unclear if the program above
> > has it.
> 
> The program by Bernstein is old, but it still compiles and works after 
> more than 20 years. It was (and it is) a very well written program!
> 
> I've not found a licence for that code, and I didn't read the sources, 
> but I'm sure it is able to sieve ranges of numbers.
> 
> On a slow computer, it takes 4 seconds to list the 268 primes between
> 10^15-10^4 and 10^15.
> 
> ~/src/primegen-0.97$ time ./primes 999999999990000 1000000000000000|wc
>      268     268    4288
> 
> real    0m4,186s
> user    0m4,126s
> sys     0m0,026s
> 
> For sure, it did not sieve all the primes up to 10^15; the very fast 
> primecount program (by Kim Walisch) needs more time to simply count them 
> all :-)
> 
> ~/src/primegen-0.97$ time primecount -t1 1000000000000000
> 29844570422669
> 
> real    0m17,905s
> user    0m17,471s
> sys     0m0,054s
> 
> 
> On the other side, I believe also that GMP will not try to compete with 
> primecount in speed. It is based on extremely specialized libraries.
> 
> I installed the pre-packaged program for my Linux distribution, and I
> see:
> 
> ~/src/primegen-0.97$ ldd $(which primecount)
>         linux-vdso.so.1 (0x00007ffe591f1000)
>         libprimecount.so.7 => /lib/x86_64-linux-gnu/libprimecount.so.7 
> (0x00007f3589249000)
>         libprimesieve.so.9 => /lib/x86_64-linux-gnu/libprimesieve.so.9 
> (0x00007f3589212000)
> [...]
> 
> ~/src/primegen-0.97$ ls -lL 
> /lib/x86_64-linux-gnu/libprime{count,sieve}.so.?
> -rw-r--r-- 1 root root 383032 Maj  8 16:22 
> /lib/x86_64-linux-gnu/libprimecount.so.7
> -rw-r--r-- 1 root root 219168 Maj  8 14:04 
> /lib/x86_64-linux-gnu/libprimesieve.so.9
> 
> ~/src/primegen-0.97$ ls -lL /lib/x86_64-linux-gnu/libgmp.so.10
> -rw-r--r-- 1 root root 525152 Nov 15  2021 
> /lib/x86_64-linux-gnu/libgmp.so.10
> 
> Counting both libraries needed by primecount, they are larger than the 
> full GMP library.
> 
> Ĝis,
> m
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss