Possible minimum-memory method for computing pi to N bits, albeit extremely slowly: For K = 0 to N, use the BBP formula for the Kth bit. This will require O(logN) storage: several registers of size logN to hold the state of the BBP calculation. You'll also need to be aware of the Chudnovsky result, which, IIRC, is that |pi - p/q| > q^-13. That is, you can't get too many consecutive 0s or 1s before a round-up-or-down situation is resolved. However, if you want the answer in decimal, you may need space to hold most of the .301 N digits, which would bump the space to O(N). Rich ------ Quoting meekerdb <meekerdb@verizon.net>:
On 10/14/2012 5:18 PM, Gareth McCaughan wrote:
On Monday 15 October 2012 00:12:21 meekerdb wrote:
pi has maximal Kolmogorov complexity. What do you mean?
Surely the Kolmogorov complexity of a thing is the length of the shortest program that produces it? You can write a very short program that produces pi. Pi has very *small* Kolmogorov complexity.
Sorry, brain fade there.
But rational approximations to pi don't. Is there some way to define the minimum algorithm for computing pi to say N decimal places. And if so, what is the length of the algorithm as a function of N? Ultimately constant, because for large N the best way to make a program that outputs N digits of pi is to make a program that outputs pi and look only at the first N digits.
(If you insist on having it stop at the right place, then it goes like constant + complexity(N); the second term looks like log(N) for almost all N.)
The shortest program to output pi is probably longer than the shortest program to output 3.14, so I'm wondering how the length increases with the number of decimal places. Are approximations like 31^(1/3) actually computationally efficient?
Brent
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun