Re: [math-fun] Pi to 31.4 trilllion digits
Gosper's algorithms for doing arithmetic with continued fractions are perfectly capable of converting the generalized CF to the vanilla CF. And also, converting these to decimal or factorial base etc. and back. They are very spigoty. The main drawback is maintaining a required internal state, which often grows larger as the spigot progresses. Gosper is better at explaining this than I am, but the main idea is to keep your number represented as (aX+b)/(cX+d), with the understanding that X is yet to be calculated, but is known to be either between 0 & 1, or 1 & infinity. A,b,c,d are (big) integers. Suppose we go with the [0,1] convention; and we are converting to decimal. We maintain the fraction (aX+b)/(cX+d) as having a value between 0 and 1. To get the next digit out, multiply by 10. I.e., a & b are multiplied by 10. If the values at X=0 and X=1 both have the same integer part, that's the next digit, say D. Subtract it off to get back between 0 & 1. anew = a - Dc, bnew = b - Dd. If the values at X=0 and 1 don't have the same integer part, we need more information about X. If X is being supplied as a regular continued fraction, we have X = 1/(Q+Xnew), where Q is the next term in the continued fraction (the Partial Quotient), and Xnew is the tail. The arithmetic to "ingest" Q is to replace X by 1/(Q+Xnew) in the fraction (aX+b)/(cX+d) and simplify the expression to [a+b(Q+Xnew)]/[c+d(Q+Xnew)], getting anew = b, bnew = a+bQ, and similarly for cnew and dnew. We retest whether we can emit another digit; if not, we need a more accurate X, so we input more of the continued fraction. This is very spigoty, but a,b,c,d usually grow. For a random CFrac, I think one digit per partial quotient is about right. The updates are easily modified to accommodate generalized CFracs. You can add X and Y by starting with the form (X+Y)/1, and using the general form (aXY+bX+cY+d)/(eXY+fX+gY+h); this also works for multiplication and division, with starting forms (XY)/1 or X/Y. It's equally good at converting decimal to CFs, or doing arithmetic on decimals or CFs, etc. You can even link together these CF machines to compute complicated expressions like pi+e, or recursive stuff like R <- 1 + 1/(1+R) to get sqrt(2) or more complicated algebraic numbers. The method also works with a lot of infinite series. Gosper briefly held the record for computing pi; he may have used a CF directly, or one of the other series, and then converted it to CF form. I don't recall how slow Mike's GCF for pi is; it might be merely sluggish, or even non-convergent. Wrt converting binary fractions into (or out of) decimal, the work can be done in roughly O( N (logN)^2 loglogN) computation steps for N digits or bits. Suppose you have an N bit fraction: Compute a power 10^2^k in binary, that has more than N/2 bits. Multiply your target number by this power of 10, and discard the integer part. Truncate the fraction to N/2 bits. Also truncate your original target number to N/2 bits. You now have two half-size conversions to do. Iterate logN times, getting down to single digits. Concatenate the digits. The first multiply cost is about O(N logN loglogN) steps, and the successive iterations are about the same ... twice as many multiplications of half-length numbers. Total cost roughly O( N (logN)^2 loglogN). Some fixups are needed for edge cases, like long strings of 9s, but it doesn't cost much. Rich --- Quoting Mike Stay <metaweta@gmail.com>:
It depends. There are generalized continued fractions where it's very easy, like ? = 3 + 1^2 / (6 + 3^2 / (6 + 5^2 / (6 + 7^2 ( 6 + ... ) ) ) ) Nobody knows a spigot-like algorithm for the simple continued fraction of pi.
On Fri, Mar 15, 2019 at 1:25 PM Dan Asimov <dasimov@earthlink.net> wrote:
What might be interesting would be to see kajillions of "digits" of the continued fraction expansion (CFE) of ?. At least, that's independent of how many fingers we have.
Are there good algorithms for calculating a high "digit" of the CFE of ? without knowing the previous ones?
?Dan
Simon Plouffe schrieb: ----- Pi has been calculated to 31.4 trillion digits : http://www.numberworld.org/blogs/2019_3_14_pi_record/
they used the Chudnovsky formula, the Bellard formula and mine just to be certain. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Sorry: spigot, yes, but pick up in the middle of the number without computing anything that comes before, no. On Fri, Mar 15, 2019 at 5:48 PM <rcs@xmission.com> wrote:
Gosper's algorithms for doing arithmetic with continued fractions are perfectly capable of converting the generalized CF to the vanilla CF. And also, converting these to decimal or factorial base etc. and back. They are very spigoty. The main drawback is maintaining a required internal state, which often grows larger as the spigot progresses.
Gosper is better at explaining this than I am, but the main idea is to keep your number represented as (aX+b)/(cX+d), with the understanding that X is yet to be calculated, but is known to be either between 0 & 1, or 1 & infinity. A,b,c,d are (big) integers. Suppose we go with the [0,1] convention; and we are converting to decimal. We maintain the fraction (aX+b)/(cX+d) as having a value between 0 and 1. To get the next digit out, multiply by 10. I.e., a & b are multiplied by 10. If the values at X=0 and X=1 both have the same integer part, that's the next digit, say D. Subtract it off to get back between 0 & 1. anew = a - Dc, bnew = b - Dd.
If the values at X=0 and 1 don't have the same integer part, we need more information about X. If X is being supplied as a regular continued fraction, we have X = 1/(Q+Xnew), where Q is the next term in the continued fraction (the Partial Quotient), and Xnew is the tail. The arithmetic to "ingest" Q is to replace X by 1/(Q+Xnew) in the fraction (aX+b)/(cX+d) and simplify the expression to [a+b(Q+Xnew)]/[c+d(Q+Xnew)], getting anew = b, bnew = a+bQ, and similarly for cnew and dnew.
We retest whether we can emit another digit; if not, we need a more accurate X, so we input more of the continued fraction. This is very spigoty, but a,b,c,d usually grow. For a random CFrac, I think one digit per partial quotient is about right.
The updates are easily modified to accommodate generalized CFracs. You can add X and Y by starting with the form (X+Y)/1, and using the general form (aXY+bX+cY+d)/(eXY+fX+gY+h); this also works for multiplication and division, with starting forms (XY)/1 or X/Y. It's equally good at converting decimal to CFs, or doing arithmetic on decimals or CFs, etc.
You can even link together these CF machines to compute complicated expressions like pi+e, or recursive stuff like R <- 1 + 1/(1+R) to get sqrt(2) or more complicated algebraic numbers. The method also works with a lot of infinite series.
Gosper briefly held the record for computing pi; he may have used a CF directly, or one of the other series, and then converted it to CF form. I don't recall how slow Mike's GCF for pi is; it might be merely sluggish, or even non-convergent.
Wrt converting binary fractions into (or out of) decimal, the work can be done in roughly O( N (logN)^2 loglogN) computation steps for N digits or bits.
Suppose you have an N bit fraction: Compute a power 10^2^k in binary, that has more than N/2 bits. Multiply your target number by this power of 10, and discard the integer part. Truncate the fraction to N/2 bits. Also truncate your original target number to N/2 bits. You now have two half-size conversions to do. Iterate logN times, getting down to single digits. Concatenate the digits. The first multiply cost is about O(N logN loglogN) steps, and the successive iterations are about the same ... twice as many multiplications of half-length numbers. Total cost roughly O( N (logN)^2 loglogN). Some fixups are needed for edge cases, like long strings of 9s, but it doesn't cost much.
Rich
--- Quoting Mike Stay <metaweta@gmail.com>:
It depends. There are generalized continued fractions where it's very easy, like ? = 3 + 1^2 / (6 + 3^2 / (6 + 5^2 / (6 + 7^2 ( 6 + ... ) ) ) ) Nobody knows a spigot-like algorithm for the simple continued fraction of pi.
On Fri, Mar 15, 2019 at 1:25 PM Dan Asimov <dasimov@earthlink.net> wrote:
What might be interesting would be to see kajillions of "digits" of the continued fraction expansion (CFE) of ?. At least, that's independent of how many fingers we have.
Are there good algorithms for calculating a high "digit" of the CFE of ? without knowing the previous ones?
?Dan
Simon Plouffe schrieb: ----- Pi has been calculated to 31.4 trillion digits : http://www.numberworld.org/blogs/2019_3_14_pi_record/
they used the Chudnovsky formula, the Bellard formula and mine just to be certain. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike https://reperiendi.wordpress.com
participants (2)
-
Mike Stay -
rcs＠xmission.com