[math-fun] 3. Re: Another approximation of pi
Continued fraction of ln(pi^7) leads to an approximation of pi as e^87/76 = 3.1416, and C.F. ln(pi^19) gives e^41129/35929 = 3.14159264. Also iteration of a complex number near Seahorse Valley (Mandelbrot Set) can be used to approximate pi
pi has maximal Kolmogorov complexity. 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? Brent Meeker On 10/14/2012 3:53 PM, Stuart Errol Anderson wrote:
Continued fraction of ln(pi^7) leads to an approximation of pi as e^87/76 = 3.1416, and C.F. ln(pi^19) gives e^41129/35929 = 3.14159264.
Also iteration of a complex number near Seahorse Valley (Mandelbrot Set) can be used to approximate pi _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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.
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.) -- g
From: Gareth McCaughan <gareth.mccaughan@pobox.com>
To: math-fun@mailman.xmission.com Sent: Sunday, October 14, 2012 5:18 PM Subject: Re: [math-fun] 3. Re: Another approximation of pi
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.
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.)
-- g
_______________________________________________
A program that calculates pi to N places requires memory that grows as some function f(N), and f(N) must grow unboundedly large with N. This is true for any irrational, since a finite state machine eventually repeats, and thus can only calculate rationals. So perhaps the complexity of an irrational number can be characterized by the slowest growing memory needed for its calculation. -- Gene
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
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
participants (5)
-
Eugene Salamin -
Gareth McCaughan -
meekerdb -
rcs＠xmission.com -
Stuart Errol Anderson