Re: [math-fun] Turning a fraction into an integer
See https://cp4space.wordpress.com/2013/10/24/enumerating-the-rationals/ Here's a fast implementation of this forward and backward Wilf-Calkin map that NeilB did in Mathematica. In[345]:= newman2pos[71426/7623] // tim During evaluation of In[345]:= 0.001112,0 Out[345]= 999999999 In[347]:= pos2newman[67107847] // tim During evaluation of In[347]:= 0.000729,0 Out[347]= 355/113 calkinwilf[num_, denom_] := Block[{lis = {}, n = num, d = denom}, (While[ n > 1 || d > 1, (lis = Prepend[lis, Boole[n > d]]; If[n > d, n -= d, d -= n])]; lis)]; wilfcalkin[bitlis_List] := Block[{n = 1, d = 1}, (Do[ If[bitlis[[i]] == 0, d += n, n += d], {i, 1, Length[bitlis]}]; Rational[n, d])] newman2pos[num_, denom_] := FromDigits[Prepend[calkinwilf[num, denom], 1], 2]; newman2pos[frac_] := newman2pos[Numerator[frac], Denominator[frac]] pos2newman[0] = 0; pos2newman[pos_] := Sign[pos]*wilfcalkin[IntegerDigits[pos, 2][[2 ;; -1]]] --rwg
Re Adam Goucher's neat summary --- Aboreally speaking, does "Calkin-Wilf" = "Stern-Brocot" ? And (same paragraph) who is "Newnham" ? I think we should be told ... WFL On 11/20/15, Bill Gosper <billgosper@gmail.com> wrote:
See https://cp4space.wordpress.com/2013/10/24/enumerating-the-rationals/ Here's a fast implementation of this forward and backward Wilf-Calkin map that NeilB did in Mathematica. In[345]:= newman2pos[71426/7623] // tim
During evaluation of In[345]:= 0.001112,0
Out[345]= 999999999
In[347]:= pos2newman[67107847] // tim
During evaluation of In[347]:= 0.000729,0
Out[347]= 355/113
calkinwilf[num_, denom_] := Block[{lis = {}, n = num, d = denom}, (While[ n > 1 || d > 1, (lis = Prepend[lis, Boole[n > d]]; If[n > d, n -= d, d -= n])]; lis)];
wilfcalkin[bitlis_List] := Block[{n = 1, d = 1}, (Do[ If[bitlis[[i]] == 0, d += n, n += d], {i, 1, Length[bitlis]}]; Rational[n, d])]
newman2pos[num_, denom_] := FromDigits[Prepend[calkinwilf[num, denom], 1], 2]; newman2pos[frac_] := newman2pos[Numerator[frac], Denominator[frac]]
pos2newman[0] = 0; pos2newman[pos_] := Sign[pos]*wilfcalkin[IntegerDigits[pos, 2][[2 ;; -1]]] --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The Calkin-Wilf and Stern-Brocot trees are distinct. In particular, an in-order tree traversal of the Stern-Brocot tree corresponds to the usual order on the positive rationals, whereas the same cannot be said of the Calkin-Wilf tree. There is, however, a neat involution between them: If we encode each node in an infinite binary tree by a sequence of 'L's and 'R's in the obvious way, then string reversal defines an involution f on the tree. Then the trees are related as follows: "X is labelled by p/q in the Calkin-Wilf tree" <==> "f(X) is labelled by p/q in the Stern-Brocot tree" and vice-versa. Newnham was a typographical error; it should be Newman. Best wishes, Adam P. Goucher
Sent: Friday, November 20, 2015 at 2:11 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Turning a fraction into an integer
Re Adam Goucher's neat summary ---
Aboreally speaking, does "Calkin-Wilf" = "Stern-Brocot" ?
And (same paragraph) who is "Newnham" ?
I think we should be told ... WFL
On 11/20/15, Bill Gosper <billgosper@gmail.com> wrote:
See https://cp4space.wordpress.com/2013/10/24/enumerating-the-rationals/ Here's a fast implementation of this forward and backward Wilf-Calkin map that NeilB did in Mathematica. In[345]:= newman2pos[71426/7623] // tim
During evaluation of In[345]:= 0.001112,0
Out[345]= 999999999
In[347]:= pos2newman[67107847] // tim
During evaluation of In[347]:= 0.000729,0
Out[347]= 355/113
calkinwilf[num_, denom_] := Block[{lis = {}, n = num, d = denom}, (While[ n > 1 || d > 1, (lis = Prepend[lis, Boole[n > d]]; If[n > d, n -= d, d -= n])]; lis)];
wilfcalkin[bitlis_List] := Block[{n = 1, d = 1}, (Do[ If[bitlis[[i]] == 0, d += n, n += d], {i, 1, Length[bitlis]}]; Rational[n, d])]
newman2pos[num_, denom_] := FromDigits[Prepend[calkinwilf[num, denom], 1], 2]; newman2pos[frac_] := newman2pos[Numerator[frac], Denominator[frac]]
pos2newman[0] = 0; pos2newman[pos_] := Sign[pos]*wilfcalkin[IntegerDigits[pos, 2][[2 ;; -1]]] --rwg _______________________________________________ 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
participants (3)
-
Adam P. Goucher -
Bill Gosper -
Fred Lunnon