mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2017-03-08, 13:21   #1
edorajh
 
edorajh's Avatar
 
Oct 2003
Croatia

23×3×19 Posts
Default 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?
edorajh is offline   Reply With Quote
Old 2017-03-08, 14:58   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

134418 Posts
Default

Edit: see below.

Last fiddled with by CRGreathouse on 2017-03-08 at 17:33
CRGreathouse is offline   Reply With Quote
Old 2017-03-08, 16:09   #3
axn
 
axn's Avatar
 
Jun 2003

111258 Posts
Default

Not quite what you were looking for: https://primes.utm.edu/nthprime/
axn is offline   Reply With Quote
Old 2017-03-08, 16:15   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

31·191 Posts
Default

Quote:
Originally Posted by axn View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-03-08, 16:33   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

5·181 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2017-03-08, 17:18   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101011100012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2017-03-08, 20:28   #7
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

5×181 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Max FFT Size? aketilander Software 44 2018-12-19 17:58
Force FFT-size to be used kruoli Software 4 2017-11-17 18:14
Size optimization Sleepy Msieve 14 2011-10-20 10:27
Exponent Size Gap Mini-Geek PrimeNet 8 2007-03-25 07:29
FFT-Size 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.