gmp-discuss Digest, Vol 203, Issue 3
Seth Troisi
braintwo at gmail.com
Sun Jun 5 21:04:34 CEST 2022
Kim Walisch also has a primesieve library which is more of a fair
comparison than primecount (which doesn't take an optional start)
At 1e4 we're probably measuring disc latency, process creation, ..., memory
allocs, ...
I have to sieve up to 1e9 primes on my system to take > .1 seconds
```
$ ./primesieve -t1 1e15-1e4 1e15
Seconds: 0.019
Primes: 268
$ ./primesieve -t1 1e15-1e9 1e15
Seconds: 0.373
Primes: 28954129
$ time ./primes 999999999990000 1000000000000000|wc
268 268 4288
real 0m0.477s
$ time ./primes 99999990000000 1000000000000000|wc
28954129 28954129 463266064
real 1m48.190s
```
On Sun, Jun 5, 2022 at 3:00 AM <gmp-discuss-request at gmplib.org> wrote:
> Send gmp-discuss mailing list submissions to
> gmp-discuss at gmplib.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
> https://gmplib.org/mailman/listinfo/gmp-discuss
> or, via email, send a message with subject or body 'help' to
> gmp-discuss-request at gmplib.org
>
> You can reach the person managing the list at
> gmp-discuss-owner at gmplib.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of gmp-discuss digest..."
>
>
> Today's Topics:
>
> 1. Re: about prime number generation (Hans ?berg)
> 2. Re: about prime number generation (Adrien Prost-Boucle)
> 3. Re: about prime number generation (Hans ?berg)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Sat, 4 Jun 2022 14:39:05 +0200
> From: Hans ?berg <haberg-1 at telia.com>
> To: Marco Bodrato <bodrato at mail.dm.unipi.it>
> Cc: John Gatrell <gatrelljm at gmail.com>, gmp-discuss at gmplib.org
> Subject: Re: about prime number generation
> Message-ID: <80C090C9-E119-42CE-AB61-6308C0E996EE at telia.com>
> Content-Type: text/plain; charset=utf-8
>
>
>
> > On 4 Jun 2022, at 11:39, Marco Bodrato <bodrato at mail.dm.unipi.it> 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
>
> On a MBP 2.4 GHz, I get
> primegen-0.97 % time ./primes 999999999990000 1000000000000000|wc
> 268 268 4288
> 0.81s user 0.01s system 99% cpu 0.828 total
>
> By contrast, time ./primes 1 1000000000000000|wc does not seem worth
> waiting for.
>
> > For sure, it did not sieve all the primes up to 10^15;
>
> So it seems.
>
> > 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.
>
> The WP page Prime-counting function, sec. Inequalities [1], gives upper
> and lower bounds for the ?-th prime ?(?), with the gap 0.1?, which is large
> for ? = 10??. So perhaps one can use the formulas for ?(?) to successively
> half it down, and then use a sieve for a smaller range.
>
> 1. https://en.wikipedia.org/wiki/Prime-counting_function
>
>
> I compared timing of bitmaps std::vector<bool> with byte-based integral
> types std::vector<int8_t> etc.: Interestingly, for Eratosthenes, a bitmap
> is 7-9 times slower than for multiples, but for Atkin only 50% or so. There
> is not much difference between 8, 16, 32 and 64 bit integral types,
> possibly somewhat slower for the larger ones.
>
>
>
>
> ------------------------------
>
> Message: 2
> Date: Sat, 04 Jun 2022 16:26:33 +0200
> From: Adrien Prost-Boucle <adrien.prost-boucle at laposte.net>
> To: Marco Bodrato <bodrato at mail.dm.unipi.it>, Hans ?berg
> <haberg-1 at telia.com>
> Cc: John Gatrell <gatrelljm at gmail.com>, gmp-discuss at gmplib.org
> Subject: Re: about prime number generation
> Message-ID:
> <6f8a56f946c1ee38acb65adf2f72a74d19927678.camel at laposte.net>
> Content-Type: text/plain; charset="UTF-8"
>
> 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
>
>
>
> ------------------------------
>
> Message: 3
> Date: Sat, 4 Jun 2022 18:59:26 +0200
> From: Hans ?berg <haberg-1 at telia.com>
> To: Marco Bodrato <bodrato at mail.dm.unipi.it>
> Cc: John Gatrell <gatrelljm at gmail.com>, gmp-discuss at gmplib.org
> Subject: Re: about prime number generation
> Message-ID: <876E8195-7F87-4FA3-BE06-D9C0EACD5274 at telia.com>
> Content-Type: text/plain; charset=utf-8
>
>
> > On 4 Jun 2022, at 11:39, Marco Bodrato <bodrato at mail.dm.unipi.it> wrote:
> >
> > 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 :-)
>
> I made some timings on a MBP 2.4 GHz, up to 10??, and it is linear ?(?)
> with measured time about 21? ns. For the range 10???10??+10??, the time is
> about 26? ns with the interval size ? = 10??. And it does not use much
> memory. It means that ? = 10?? would take about 5.8 hours. But it runs in
> only one thread, so eventual parallelization might reduce that.
>
> primegen-0.97 % time ./primes 1 100000000000 | openssl sha3-256
> SHA3-256(stdin)=
> 2143522c6172590ab377e9a19649cfcc55305f4fb020cda23a50678c3cf57f9e
> ./primes 1 100000000000 2102.12s user 19.70s system 96% cpu 36:33.87 total
>
> primegen-0.97 % time ./primes 1000000000000 1100000000000 | openssl
> sha3-256
> SHA3-256(stdin)=
> 9042899f10d0923b5538577d6c015546dda5f285a3718462efb2d8414bb8fe93
> ./primes 1000000000000 1100000000000 2630.41s user 14.32s system 98% cpu
> 44:39.89 total
>
>
>
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss
>
>
> ------------------------------
>
> End of gmp-discuss Digest, Vol 203, Issue 3
> *******************************************
>
More information about the gmp-discuss
mailing list