Re:Computation of the n'th digit of pi in any base in O(n^2)...
by cbright on Saturday November 11, 2023 @03:06AM
(#38228437)
> 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.
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.