Comments (4)
Question:
Is it better to use [low, high]
instead of [low, high[
?
Answer:
In order to simplify the formula for min_index_2nd_prime
it is best to use [low, high[
. This was determined by printing and examining all minimum and maximum values using primecount.
from primecount.
It works! Implemented by #20.
from primecount.
Here I try to code the formulas above in C++. We need to add some more bounds checking to avoid array of bounds accesses:
uint64_t min_index_1st_prime = pi[x_star] + 1;
uint64_t min_1st_prime = primes[min_index_1st_prime];
// x / (primes[i] * primes[i+1]) >= low
// primes[i] * primes[i+1] <= x / low
// primes[i] < sqrt(x / low)
// primes[i+1] <= sqrt(x / low) || primes[i+1] >= sqrt(x / low)
uint64_t x_div_low = x / low;
uint64_t sqrt_low = min(isqrt(x_div_low), x13);
uint64_t max_index_1st_prime = pi[sqrt_low];
if (primes[max_index_1st_prime] < max_prime &&
primes[max_index_1st_prime] * primes[max_index_1st_prime+1] > x_div_low)
max_index_1st_prime -= 1;
uint64_t min_2nd_prime = min(x / (high * primes[b]), max_prime);
uint64_t min_index_2nd_prime = pi[min_2nd_prime] + 1;
min_index_2nd_prime = max(min_index_2nd_prime, b + 1);
min_2nd_prime = primes[min_index_2nd_prime];
uint64_t max_2nd_prime = min(x / (low * primes[b]), isqrt(x / primes[b]));
uint64_t max_index_2nd_prime = pi[max_2nd_prime];
from primecount.
x / (primes[b] * primes[q]) >= x^(1/3)
Hence we should start the segmentation with low = x^(1/3)
using a segment size of e.g. z and the algorithm finishes when high = x^(1/2)
.
More accurately the algorithm finishes at:
min_index_1st_prime = pi[x_star] + 1;
high = x / (primes[min_index_1st_prime] * primes[min_index_1st_prime+1]) + 1
from primecount.
Related Issues (20)
- primecount-backup prints incorrect time elapsed HOT 1
- Idea for improvement to LMO/pi_lmo5.cpp HOT 5
- Incorrect Common Lisp bindings link HOT 1
- Integer overflow in phi(x, a)
- Build on windows using mingw fail HOT 12
- Data Races in LoadBalancerS2.cpp HOT 3
- add pkg-config config? HOT 5
- need to set LD_LIBRARY_PATH for default install on Debian 11 HOT 15
- describing how to build dynamically linked (lib)primecount without root HOT 6
- brew install on macOS installs primecount 7.0 and no library HOT 5
- Question regarding PhiTiny _sieve array HOT 11
- Question regarding PhiTiny test HOT 4
- Please create discussions
- Broken WITH_POPCNT logic HOT 17
- By 2025 change default setting to WITH_DIV32=OFF in CMakeLists.txt HOT 5
- By 2027 change default setting to WITH_LIBDIVIDE=OFF in CMakeLists.txt HOT 1
- Primecount fails at runtime with GCC-12 & MinGW/MSYS2 (Windows 10) HOT 2
- xavier gourdon's paper HOT 3
- Riemann R approximation is a little off HOT 3
- prime_pi of a negative number fails with Bus error HOT 6
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from primecount.