20170308, 13:21  #1 
Oct 2003
Croatia
2^{3}·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?

20170308, 14:58  #2 
Aug 2006
13443_{8} Posts 
Edit: see below.
Last fiddled with by CRGreathouse on 20170308 at 17:33 
20170308, 16:09  #3 
Jun 2003
2·2,347 Posts 
Not quite what you were looking for: https://primes.utm.edu/nthprime/

20170308, 16:15  #4  
Aug 2006
1723_{16} Posts 
Quote:


20170308, 16:33  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
905_{10} 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. 
20170308, 17:18  #6  
"Robert Gerbicz"
Oct 2005
Hungary
11·127 Posts 
Quote:
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. 

20170308, 20:28  #7  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
5×181 Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Max FFT Size?  aketilander  Software  44  20181219 17:58 
Force FFTsize to be used  kruoli  Software  4  20171117 18:14 
Size optimization  Sleepy  Msieve  14  20111020 10:27 
Exponent Size Gap  MiniGeek  PrimeNet  8  20070325 07:29 
FFTSize  andi314  Lounge  14  20070122 00:21 