mersenneforum.org Pi(x) value for x at 10^16 size
 Register FAQ Search Today's Posts Mark Forums Read

 2017-03-08, 13:21 #1 edorajh     Oct 2003 Croatia 23×3×19 Posts Pi(x) value for x at 10^16 size Is there any tool or software that can return pi(x) value for numbers at 10^16 size?
 2017-03-08, 14:58 #2 CRGreathouse     Aug 2006 134418 Posts Edit: see below. Last fiddled with by CRGreathouse on 2017-03-08 at 17:33
 2017-03-08, 16:09 #3 axn     Jun 2003 111258 Posts Not quite what you were looking for: https://primes.utm.edu/nthprime/
2017-03-08, 16:15   #4
CRGreathouse

Aug 2006

31·191 Posts

Quote:
 Originally Posted by axn Not quite what you were looking for: https://primes.utm.edu/nthprime/
A great tool, very fast and nothing to install, but 3 * 10^13 < 10^16.

 2017-03-08, 16:33 #5 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 5·181 Posts https://github.com/kimwalisch/primecount The currently fastest available implementation. Threaded as well. You definitely would want to use instead of primesieve. Same author. Perl/ntheory (available with Strawberry Perl, or install Math::Prime::Util from your distro or CPAN). perl -E "say prime_count(1e16)" Used to be just a little faster than primecount, but Kim has done some fantastic work and made his faster, and once you get to use multiple threads it is a lot faster at this size. For 1e16 it is about 21 seconds for Perl/ntheory, and Kim reports 2.67 seconds multithreaded for his latest code. Wow.
2017-03-08, 17:18   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101011100012 Posts

Quote:
 Originally Posted by CRGreathouse A great tool, very fast and nothing to install, but 3 * 10^13 < 10^16.
This is similar to the Mathematica's idea, and it is very good for "smallish" x<=N values: up to some limit N compute the primes, and store the count at each n==0 mod S.

primepi(x)=primepi(c)+#{p:c<p<=x}, where c=S*floor(x/S), and here primepi(c) has been precomputed. (or use c'=c+S if x mod S>S/2)

Making a table for N=10^16 and for say S=10^8 wouldn't be that hard, you need less than 1GB of Ram to store the table. Using this setup it would take much less than 1 sec to get primepi(x) for any x<=10^16.

2017-03-08, 20:28   #7
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

5×181 Posts

Quote:
 Originally Posted by R. Gerbicz Making a table for N=10^16 and for say S=10^8 wouldn't be that hard, you need less than 1GB of Ram to store the table. Using this setup it would take much less than 1 sec to get primepi(x) for any x<=10^16.
I use stepped tables for N < 3e9 using 4k of data. There's a script included with my package that takes parameters step/start/stop and creates tables ready to plug in to the header file. Extending that to 3e10 with 3e8 steps goes to 8k and is well under a second to get values. Extending to 3e11 with 3e8 steps is 44k of table data and still well under a second.

My table generator gets pretty slow at these sizes as it wasn't really intended for that. It'd make more sense to load up TOeS's extensive count tables and build something using those, though they're lacking in resolution vs. the 1e8 (or 3e8) target (as are Nicely and Kulcha's tables). They have what we need to 1e14 though.

For my implementations, past 66M is slower than just running LMO. Using those steps it looks like it would cross over somewhere in the 8e12 range. There exist faster sieves and a faster LMO which would modify those numbers. Table sizes would probably come out to under 1GB for 10^16.

 Similar Threads Thread Thread Starter Forum Replies Last Post aketilander Software 44 2018-12-19 17:58 kruoli Software 4 2017-11-17 18:14 Sleepy Msieve 14 2011-10-20 10:27 Mini-Geek PrimeNet 8 2007-03-25 07:29 andi314 Lounge 14 2007-01-22 00:21

All times are UTC. The time now is 16:42.

Sat Sep 19 16:42:53 UTC 2020 up 9 days, 13:53, 0 users, load averages: 1.08, 1.36, 1.39