6 ms·
Computation of the n'th digit of pi in any base in O(n^2) (1997)
- sp332 3y agoI 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!
- credit_guy 3y agoWe 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 https://bellard.org/pi/pi2700e9/pipcrecord.pdf [2] https://en.wikipedia.org/wiki/Chudnovsky_algorithm https://en.wikipedia.org/wiki/Chudnovsky_algorithm
- lll-o-lll 3y agoCalculating 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.
- credit_guy 3y agoIf 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-100-trillion-digits-of-pi-on-google-cloud https://cloud.google.com/blog/products/compute/calculating-1...
- dgacmu 3y agoThe 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.
- cbright 3y ago> 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.
- deleted 3y ago[deleted]
- Funnyduck99 3y agoIs this good? I would think finding nth digit of pi would be O(n)
- sp332 3y agoThat 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.
- shzhdbi09gv8ioi 3y agoIf 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 https://en.wikipedia.org/wiki/Bellard%27s_formula
- davesque 3y agoSquinting 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.
- alanbernstein 3y agoThat'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?
- davesque 3y agoI 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.
- davesque 3y agoBut I know I'm reaching here. I just like fantasizing about math :).
- westurner 3y agoIs 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 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-square-probability-amplitude-why-not-direct-values#comment630152_280748 https://physics.stackexchange.com/questions/280748/why-do-we...
- someplaceguy 3y agoThat's impressive, but not as impressive as this: https://twitter.com/InternetH0F/status/1721641836404408536 https://twitter.com/InternetH0F/status/1721641836404408536
- TeMPOraL 3y agoThat's easy. The hard question is, in what base this answer is correct?
- prerok 3y agoIn 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 :)
- nwellnhof 3y agopi is '10' in base pi.
- TeMPOraL 3y agoYeah, 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 ;).
- nurettin 3y agoI 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. edit: it was just atan https://github.com/sharplispers/cormanlisp/blob/master/examples/pi.lisp https://github.com/sharplispers/cormanlisp/blob/master/examp...
- starcraft2wol 3y agoMath illiteracy is high in this thread.