2 ms·
Are pi digits useful for anything? Maybe some encryption technique or random number generation? Are the digits of pi easier or harder to generate than other irr
by guelo 15y ago
Are pi digits useful for anything? Maybe some encryption technique or random number generation? Are the digits of pi easier or harder to generate than other irrational numbers?
- cperciva 15y agoAre 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...