4 ms·

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!

by sp332 3y ago

credit_guy 3y ago
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 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 ago
  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.
  - credit_guy 3y ago
    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-100-trillion-digits-of-pi-on-google-cloud https://cloud.google.com/blog/products/compute/calculating-1...
- dgacmu 3y ago
  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.
- 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]

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!

by sp332 3y ago

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!

credit_guy 3y ago

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 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 ago
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.
- credit_guy 3y ago
  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-100-trillion-digits-of-pi-on-google-cloud https://cloud.google.com/blog/products/compute/calculating-1...
dgacmu 3y ago
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.
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]