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.
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