3 ms·
> This amount is only off by about 4% from the actual answer, 37,607,912,018. This doesn't seem very good? Is this the best we can do today?
by jzer0cool 6y ago
> This amount is only off by about 4% from the actual answer, 37,607,912,018.
This doesn't seem very good? Is this the best we can do today?
- pmiller2 6y agoNot even close. The prime number theorem itself gives Li(x) as an approximation to pi(x), where Li(x) = \int_2^x dt / (ln t). (If you don't read LaTeX, this says "integral from 2 to x of dt / ln t". Li(x) can be numerically evaluated with pretty good accuracy. Here is the approximation to pi(10^12) using Li(x) in Wolfram Alpha: https://www.wolframalpha.com/input/?i=Round%5BLogIntegral%5B10%5E12%5D+-+LogIntegral%5B2%5D%5D https://www.wolframalpha.com/input/?i=Round%5BLogIntegral%5B... The numerical value is 37607950280. Compared with the true value of 37607912018, this gives a relative error of around 1.0 * 10^-6, or 5 correct digits. Edit: Here is an algorithm to approximate pi(x) more directly: https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorithm https://en.wikipedia.org/wiki/Meissel%E2%80%93Lehmer_algorit...
- Someone 6y agoNo. We can compute the number exactly without computing all primes below a trillion (that’s why this article can mention the exact answer). See https://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_π(x) https://en.wikipedia.org/wiki/Prime-counting_function#Algori... For those working on a language that supports automatic differentiation: implement such an algorithm, and differentiate it to get a primality test. I think that would be a good test for your compiler.