> 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.
> 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.
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'.)
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 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.
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 ;).
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.
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.
> "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...
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.
I think an earlier version of this algorithm was implemented as a showcase in one of the corman lisp for windows 16bit examples folder. I was astonished watching it print thousands of digits of pi in under a minutes.
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].
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.
> 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.
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.
