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!
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://cloud.google.com/blog/products/compute/calculating-1...
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.