2 ms·
Are the digits of pi easier or harder to generate than other irrational numbers? The best known algorithms for computing Pi takes O(M(n) log n) time, where M(n
by cperciva 15y ago
Are the digits of pi easier or harder to generate than other irrational numbers?
The best known algorithms for computing Pi takes O(M(n) log n) time, where M(n) is the time required for an n-digit multiplication (approximately O(n log n) using an FFT).
This makes Pi harder than algebraic numbers -- all algebraics can be computed in O(M(n)) time -- and no easier than any other elementary function -- all elementary functions can be computed in O(M(n) log n) time.
There are a few numbers for which the current best known algorithm is slower than Pi, but the only interesting one is Euler's gamma, at O(M(n) (log n)^2).
- waqf 15y agoThis is really interesting and I've never seen it laid out like that. Can you recommend a reference?
- cperciva 15y agoThe best book I know on this topic is Pi and the AGM: http://www.amazon.com/AGM-Computational-Complexity-Mathematical-Monographs/dp/047131515X http://www.amazon.com/AGM-Computational-Complexity-Mathemati...