Computation of the n'th digit of pi in any base in O(n^2) (1997)(bellard.org)
bellard.org
Computation of the n'th digit of pi in any base in O(n^2) (1997)
https://bellard.org/pi/pi_n2/pi_n2.html
37 comments
Math illiteracy is high in this thread.
I thought we only had algorithms to do this in hexadecimal or other power-of-2 bases. Looks like arbitrary bases including base 10 have been doable since 1996!
We had the algorithm for the hexadecimal digits in 1997, and this post refers to it as reference 2. That algorithm runs in constant time, which is a pretty big deal.
This algorithm here runs in O(n^2). I'm not sure how impressed I should be. Bellard himself wrote this paper [1] in 2010 where he showed how he calculated 2.7 trillion decimal digits of pi. The algorithm was essentially linear (with some logs and powers of logs thrown in there, like in all self-respecting algorithms). Of course, 2010 was 13 years after 1997, maybe in 1997 O(n^2) was the best someone could get. I'm getting the impression however that the ingredients for the 2010 record were all there since the record established by the Chudnovsky brothers in 1988 [2].
[1] https://bellard.org/pi/pi2700e9/pipcrecord.pdf
[2] https://en.wikipedia.org/wiki/Chudnovsky_algorithm
This algorithm here runs in O(n^2). I'm not sure how impressed I should be. Bellard himself wrote this paper [1] in 2010 where he showed how he calculated 2.7 trillion decimal digits of pi. The algorithm was essentially linear (with some logs and powers of logs thrown in there, like in all self-respecting algorithms). Of course, 2010 was 13 years after 1997, maybe in 1997 O(n^2) was the best someone could get. I'm getting the impression however that the ingredients for the 2010 record were all there since the record established by the Chudnovsky brothers in 1988 [2].
[1] https://bellard.org/pi/pi2700e9/pipcrecord.pdf
[2] https://en.wikipedia.org/wiki/Chudnovsky_algorithm
Calculating n digits of pi is not the same problem as calculating the nth digit of pi. O(n^2) does indeed appear to be as good as that gets.
If O(n^2) was the best, then how did Google calculate 100 trillion digits (10^14) of pi [1]? That would require a constant times 10^28 operations. Let's say the constant is 1, and all operations are the cheapest operations and you use an A100 GPU. That A100 GPU can do about 10^15 operations per second of Int8 type. You'd need 10^13 seconds of GPU time, which you could get with, say, 10000 GPUs in 1 billion seconds (30 years). I don't think Google did that.
[1] https://cloud.google.com/blog/products/compute/calculating-1...
[1] https://cloud.google.com/blog/products/compute/calculating-1...
> this post refers to it as reference 2. That algorithm runs in constant time, which is a pretty big deal.
Not constant time; the analysis in the paper shows that the nth digit can be computed in O(n log n M(log n)) bit operations, where M(j) is the bit complexity of multiplying two j bit numbers.
Not constant time; the analysis in the paper shows that the nth digit can be computed in O(n log n M(log n)) bit operations, where M(j) is the bit complexity of multiplying two j bit numbers.
[deleted]
The algorithms to calculate all of the digits use o(n) memory. This uses o(1). It's always nifty when you can trade time for memory like that.
Is this good? I would think finding nth digit of pi would be O(n)
If it's good?
It took the world record in calculating Pi, so I'd say Yes, it was good.
> Bellard's formula was discovered by Fabrice Bellard in 1997. It is about 43% faster than the Bailey–Borwein–Plouffe formula (discovered in 1995).
https://en.wikipedia.org/wiki/Bellard%27s_formula
> Bellard's formula was discovered by Fabrice Bellard in 1997. It is about 43% faster than the Bailey–Borwein–Plouffe formula (discovered in 1995).
https://en.wikipedia.org/wiki/Bellard%27s_formula
That only works until you run out of resolution in your floating-point representation. When you have to start manually keeping track of digits, that's when things slow down.
Squinting at this, I wonder if it's at all valid to say that the existence of a quadratic time algorithm to calculate pi has anything to do with the fact that the implicit formula of a circle is made up of quadratic terms.
In other words, if pi basically sums up the most important fact about a circle's geometry, then it's reasonable to expect that geometry to be represented somehow in the important facts about algorithms that calculate pi.
In other words, if pi basically sums up the most important fact about a circle's geometry, then it's reasonable to expect that geometry to be represented somehow in the important facts about algorithms that calculate pi.
That's an interesting concept. I think similar spigot algorithms are known for other transcendentals, and I suspect if you compared them you would not find a general trend of deep connections between algorithmic complexity and the geometric features of the corresponding value. What would you look for in the spigot algorithm for e, or log 2?
I suppose e's connection to hyperbolic geometry might suggest a relationship with the implicit formula x^2 - y^2 = 1. And I guess log2's behavior would be very much connected to that since it only differs from the natural log by a constant factor.
But I know I'm reaching here. I just like fantasizing about math :).
Is there unitarity, symmetry, or conservation when x^2 ± y^2 = 1?
We square complex amplitudes to make them real.
https://twitter.com/westurner/status/967970148509503488 :
> "Partly because, mathematically, wavefunctions are vectors in a L^2 Hilbert space, which is complex-valued. Squaring the amplitude, rather Ψ∗Ψ=|Ψ|^2 is one way to ensure that you get real-valued probabilities, which is also related to the fact that […]" https://physics.stackexchange.com/questions/280748/why-do-we...
We square complex amplitudes to make them real.
https://twitter.com/westurner/status/967970148509503488 :
> "Partly because, mathematically, wavefunctions are vectors in a L^2 Hilbert space, which is complex-valued. Squaring the amplitude, rather Ψ∗Ψ=|Ψ|^2 is one way to ensure that you get real-valued probabilities, which is also related to the fact that […]" https://physics.stackexchange.com/questions/280748/why-do-we...
Well, that constant factor is irrational..
There are different ways to define pi. In real analysis, you first define the exponential function: exp(x) = sum (x^k)/(k!), then cosine: cos(x) = Re(exp(i*x)), where i is the imaginary unit, and then show that cos(x) has exactly one root in [0,2], which you call pi/2.
Your statement suggests that the definition via the circle is more fundamental that other definitions, which it isn't, e.g. because it requires a very special metric in Euclidean space (of which there are infinitely many), while real analysis only requires a metric on the real numbers.
Your statement suggests that the definition via the circle is more fundamental that other definitions, which it isn't, e.g. because it requires a very special metric in Euclidean space (of which there are infinitely many), while real analysis only requires a metric on the real numbers.
[deleted]
That's impressive, but not as impressive as this: https://twitter.com/InternetH0F/status/1721641836404408536
I didn't believe the screenshot, but this is real with ChatGPT 3.5 (the green avatar).
https://chat.openai.com/share/aadf6a17-f40e-4ea6-8f5e-236bc2...
ChatGPT 4 gives a more correct answer:
> Pi is an irrational number, meaning it has an infinite number of digits that don't repeat in a predictable pattern. So, there's no such thing as the "last" digits of pi.
https://chat.openai.com/share/6a7c0221-0aca-48af-8938-e4d98e...
https://chat.openai.com/share/aadf6a17-f40e-4ea6-8f5e-236bc2...
ChatGPT 4 gives a more correct answer:
> Pi is an irrational number, meaning it has an infinite number of digits that don't repeat in a predictable pattern. So, there's no such thing as the "last" digits of pi.
https://chat.openai.com/share/6a7c0221-0aca-48af-8938-e4d98e...
I just tried it with ChatGPT 3.5:
> The decimal representation of pi is infinite and non-repeating, so it doesn't have "last 8 digits" in the way a finite number would. However, if you're looking for the first few digits of pi, they are 3.14159265. If you need more digits, you can find them using various sources or tools that provide the decimal expansion of pi.
> The decimal representation of pi is infinite and non-repeating, so it doesn't have "last 8 digits" in the way a finite number would. However, if you're looking for the first few digits of pi, they are 3.14159265. If you need more digits, you can find them using various sources or tools that provide the decimal expansion of pi.
You got more lucky than me because I tried a few times and I got the same answer with different digits every time. Also similar correct answers using ChatGPT 4 every time.
Better, but irrational numbers can have a predictable pattern like "0.110100100010000" ( E.g "0.1 10 100 1000 10000" )
I'd argue that every computable number has “a predictable pattern” in its digits.
I guess it depends.
A cryptographically secure pseudorandom number generator lets me pump out a stream of digits that's certainly computable, but unless you know my private key, you won't be able to predict it.
(Finding out the private key from the stream is 'computable', because the definition of computable is comfortable with running exponentially long brute force searches. But that's why 'computable' is not a useful definition in practice. You want something that captures 'tractable', not just 'possible on a Turing machine at all'.)
A cryptographically secure pseudorandom number generator lets me pump out a stream of digits that's certainly computable, but unless you know my private key, you won't be able to predict it.
(Finding out the private key from the stream is 'computable', because the definition of computable is comfortable with running exponentially long brute force searches. But that's why 'computable' is not a useful definition in practice. You want something that captures 'tractable', not just 'possible on a Turing machine at all'.)
It a quite tautology. How do you define "predictability"?
The most intuitive answer is just computability.
The most intuitive answer is just computability.
That simple sequence, 1, 10, 100 etc, the digit is at least computable in O(1) time which is maybe a good way to look at predictability. It's a simple rule and no effort similar to computing every digit before it is required.
If you store the number of zeros as value z, computing z+1 is O(log n) in the long run for unbounded values of z.
If you define predictable as computable with finite memory, it is correct.
If you have finite memory, you have a finite number of states and will eventually return to a previous state. In your example, you eventually will run out of memory to track the number of consecutive zeros.
If you have finite memory, you have a finite number of states and will eventually return to a previous state. In your example, you eventually will run out of memory to track the number of consecutive zeros.
That's easy. The hard question is, in what base this answer is correct?
In base pi, the pi number is 1. Similarly, if we would take any base, which is a factor of pi, we could have any number be the last digit.
All the above is a joke, of course, as it does not really tackle the problem :)
All the above is a joke, of course, as it does not really tackle the problem :)
Yeah, that's what my joke is about - once we allow for fractional bases, I'm pretty sure we can find one where the last digits of Pi are the ones ChatGPT gave. The trick is, to write down the base as a number, without referencing Pi, you'll have to do the equivalent of finding those last digits in Base 10, i.e. infinite work. This is to illustrate conservation of effort ;).
edit: it was just atan https://github.com/sharplispers/cormanlisp/blob/master/examp...