March 2019 - mathfun@mailman.xmission.com

Re: [math-fun] Pi to 31.4 trilllion digits
by Bill Gosper 18 Mar '19

18 Mar '19

[DanA wrote] PS Let me add some afterthoughts: ----- Question: --------- Are there algorithms relating the cfe's of x and y with the cfe of simple functions of x and y like x + y x - y x * y x / y x ^ y —Dan Dan, it's grim: In[257]:= Coth /@ {1/2, 1, 2} Out[257]= {Coth[1/2], Coth[1], Coth[2]} These coths are related by the double angle formula (1+c^2)/2/c. But look at the CFs: In[258]:= ContinuedFraction[#, 5] & /@ % Out[258]= {{2, 6, 10, 14, 18}, {1, 3, 5, 7, 9}, {1, 26, 1, 3, 1}} Coth 2 evidently = 1/2,3/2,5/2,..., but normalizing pseudorandomizes: In[301]:= ContinuedFraction[FromContinuedFraction[{1, 3, 5, 7, 9}/2]] Out[301]= {1, 26, 1, 4, 2, 2, 1, 2} Unlike the linear conversions in my old http://www.tweedledum.com/rwg/cfup.htm, even the spigot conversion of x={2, 6, 10, 14, 18,...} to (1+x^2)/2/x = {1, 3, 5, 7, 9,..} is non finite state: Initialize V(x) to the symbolic expression (1+x^2)/2/x . Input terms via x → 2+1/x, 6+1/x, ... . Output t =⎣V(1)⎦ when it equals ⎣V(∞)⎦. V → 1/(V - t). (This is easy. Try it.) Input and output will strictly alternate until the input of 26 and the output of 13 leaves V = (2 (1654632 + 86200843 x + 1122694538 x^2))/ (229783 + 11709446 x + 149100967 x^2) (!) which can further output 15(!) This was unavoidable. The larger terms of the input contributed information faster than the smaller output terms were removing it. For a conversion to be finite state, the input and output information densities must match exactly. There might be (necessarily non-unique) number representations less efficient than decimal or cf that might reveal number-theoretic secrets. —rwg

1 1

Re: [math-fun] Pi to 31.4 trilllion digits
by Dan Asimov 17 Mar '19

17 Mar '19

PS Let me add some afterthoughts: ----- Question: --------- Are there algorithms relating the cfe's of x and y with the cfe of simple functions of x and y like x + y x - y x * y x / y x ^ y —Dan

2 1

Re: [math-fun] Pi to 31.4 trilllion digits
by Dan Asimov 17 Mar '19

17 Mar '19

Re continued fraction expansions (CFE's) defined via: Given x in (0, 1), let c(1) = floor(1/x); x(1) = frac(1/x) (= 1/x - floor(1/x)) ... ... c(n+1) = floor(1/x(n)) x(n+1) = frac(1/x(n)) ... Then the integer sequence (c(1), c(2), ..., c(n), ...) is the cfe of x. Question: --------- Are there algorithms relating the cfe of x with the cfe of simple functions of x like f(x) = Kx (K a real constant) f(x) = x + K f(x) = x^p (p > 0) f(x) = log(1/x) f(x) = e^x ??? —Dan

1 0

Re: [math-fun] Pi to 31.4 trilllion digits
by Bill Gosper 17 Mar '19

17 Mar '19

http://www.tweedledum.com/rwg/cfup.htm Rich contributed the idea that you can finesse successive approximations with a feedback loop. E.g., Solve e^(ix)=-1 by Newton's method. The rate of output exceeds the rate of input. "Mike's" cf has a vanishing rate of convergence! In[246]:= ContinuedFraction[ContinuedFractionK[(2 k - 1)^2, 6, {k, 999}], 9] Out[246]= {0, 7, 15, 1, 292, 1, 10, 9, 3} In[248]:= ContinuedFraction[ContinuedFractionK[(2 k - 1)^2, 6, {k,∞}], 9] Out[248]= {0, 7, 15, 1, 292, 1, 1, 1, 2} DanA is right—the cf is more fun: https://community.wolfram.com/groups/-/m/t/1581809 I tried to dissuade people from decimalizing π, but I had to decimalize my rational approximation (getting 17M) to check against Kanada's reigning 16M. My 17M record lasted a couple of weeks. Regrettably, the cf (also 17M) stood for decades, as nobody followed my lead. (Actually, I suspect the Chudnovskys of having multiG terms, but didn't brag for some reason.) Anyone familiar with Sagan's Contact novel will understand Marc LeBrun's suggestion to publlsh a gig or two of π as "The Saganic Verses." It seemed even dumber than decimal for Sagan's superbeings to expand in base 11 (unless they had a fingerlike sex organ), but Lo: Base 11 has the convergence rate closest to Gauss-Kuzmin! —rwg Can somebody forward this to the Chudnovskys, or provide an e-address? On 2019-03-15 16:47, rcs(a)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(a)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(a)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. >>> ----- >>> >>> _______________________________________________

1 0

Re: [math-fun] Pi to 31.4 trilllion digits
by rcs＠xmission.com 16 Mar '19

16 Mar '19

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(a)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(a)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(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > -- > Mike Stay - metaweta(a)gmail.com > http://math.ucr.edu/~mike > https://reperiendi.wordpress.com > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

2 1

[math-fun] Uninvented chesslike math games
by Dan Asimov 15 Mar '19

15 Mar '19

Since the last World Championship matches (at least for humans) I've been thinking a bit about a hobby going back to my childhood, but which I've all but ignored for decades: chess. Having watched a bunch of chess videos on YouTube, I have a heightened respect for the depth of the game, oxymoron though that may be. So I'm wondering: What might be the characteristics of a continuous-time, idealized 2-player game that captures the most essential features of chess, whatever you yourself may deem them to be (assuming you play the game)? What I'm *not* asking for is a fully thought-out game, just what would be nice for it to be like. I will post my own very preliminary thoughts on this soon, but don't want to muddy the waters with those right now. —Dan

1 0

Re: [math-fun] Pi to 31.4 trilllion digits
by Dan Asimov 15 Mar '19

15 Mar '19

Hmm. Is there a simple connection between the CFE of real number x and that of 1/x ??? —Dan Simon Plouffe wrote: ----- ... the generalized continued fraction of Pi, (or 1/Pi) ... -----

2 1

Re: [math-fun] Pi to 31.4 trilllion digits
by Dan Asimov 15 Mar '19

15 Mar '19

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. -----

5 4

Re: [math-fun] Statistics for a class of random solids, a drunkard's walkthrough
by Keith F. Lynch 15 Mar '19

15 Mar '19

Steve Witham <sw(a)tiac.net> wrote: > "Keith F. Lynch" <kfl(a)KeithLynch.net> wrote: >> Do you mean that the values of the three coordinates are >> independently normally distributed, or that the distance from the >> origin is? It's not obvious to me that these would give the same >> distribution. > Allan Wechsler <acwacw(a)gmail.com> answered this on 3/10, but I > didn't find his answer searching for "do you mean," and also there > are some extra quirks in the following response: > Ignoring constants, the normal distribution is like 1/exp(x^2). > Independent distributions for the three axes combine by multiplying: > 1 / (exp(x^2) exp(y^2) exp(z^2) )= 1/exp(x^2 + y^2 + z^2) > Say r is the distance from the origin, r^2 = x^2 + y^2 + z^2. > So the distribution is like 1/exp(r^2). Except for constants. > And I think the converse has to be true too. Thanks. That's the rare explanation that not only leaves me with no doubt, but that makes me kick myself for not having come up with it myself.

1 0

[math-fun] Pi to 31.4 trilllion digits
by Simon Plouffe 15 Mar '19

15 Mar '19

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. Best regards, Simon Plouffe

2 3