[Tutor] Stern-Brocot tree: more fun math
Gregor Lingl
glingl@aon.at
Wed, 9 Jan 2002 03:22:25 +0100
This is a multi-part message in MIME format.
------=_NextPart_000_0088_01C198BC.DC399780
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Dear all,
inspired by PV's Stern-Brocot-program I thought this to be an ideal =
opportunity
to try out Kirby's fraction-objects.
I produced a slightliy enhanced version of the F class in order
to have 'big fractions' and to be able to compare them.
Moreover I used the strange but convenient fact that this class allows
the definition of the fraction 1/0.
Then I developed another recursive solution (considering trees to be =
naturally
recursive data-structures) - may be it's mathematically less =
pretentious, but=20
it works.
Here is the code of the program:
def median(l, r):
return F(l.num+r.num, l.den+r.den)
### Stern-Brocot-tree-traversal back and forth
trace =3D 0
def frac2path(f, path =3D [], left =3D F(0,1), right =3D F(1,0)):
m =3D median(left,right)
if trace: print m
if f =3D=3D m:
return path
elif f < m:
return frac2path(f, path+["L"], left, m)
else:
return frac2path(f, path+["R"], m, right)
def path2frac(p, left =3D F(0,1), result =3D F(1,1), right =3D F(1,0)):
if not p:
return result
if trace: print result
if p[0]=3D=3D"L":
return path2frac(p[1:], left, median(left,result), result)
else:
return path2frac(p[1:], result, median(result,right), right)
=20
### Kirby's fraction-class, slightly enhanced
class F:
def __init__(self,numer,denom):
# reduce inputs to lowest terms
numer =3D long(numer) # NEW: for 'big fractions'
denom =3D long(denom)
gcd =3D self.gcd(numer,denom)
self.num =3D numer//gcd
self.den =3D denom//gcd
def __add__(self,other):
# find lowest common multiple
a,b =3D self.num, other.num
comden =3D self.lcm(self.den, other.den)
if comden !=3D self.den:
a *=3D comden//self.den
if comden !=3D other.den:
b *=3D comden//other.den
return F(a+b,comden)
def __sub__(self,other):
return self + (-other)
def __neg__(self):
return F(-self.num,self.den)
def __lt__(self,other): # NEW: for comparison: m<n
return (self.num*other.den) < (other.num*self.den)
def __eq__(self,other): # NEW: for comparison: m=3D=3Dn
return (self.num*other.den) =3D=3D (other.num*self.den)
def gcd(self,a,b):
# find greatest common divisor of a,b
if b=3D=3D0: return a
else: return self.gcd(b,a%b)
def lcm(self,a,b):
# find lowest common multiple of a,b
return a*b//self.gcd(a,b)
def __repr__(self):
# represent as (a/b)
return "(%s/%s)" % (self.num, self.den)
### And now a test - run:
>>> frac2path(F(173,100))
['R', 'L', 'R', 'R', 'L', 'R', 'R', 'L', 'L', 'R', 'L']
>>> path2frac(['R', 'L', 'R', 'R', 'L', 'R', 'R', 'L', 'L', 'R', 'L'])
(173/100)
>>> trace =3D 1
>>> frac2path(F(173,100))
(1/1)
(2/1)
(3/2)
(5/3)
(7/4)
(12/7)
(19/11)
(26/15)
(45/26)
(64/37)
(109/63)
(173/100)
['R', 'L', 'R', 'R', 'L', 'R', 'R', 'L', 'L', 'R', 'L']
>>> path2frac(['R', 'L', 'R', 'R', 'L', 'R', 'R', 'L', 'L', 'R', 'L'])
(1/1)
(2/1)
(3/2)
(5/3)
(7/4)
(12/7)
(19/11)
(26/15)
(45/26)
(64/37)
(109/63)
(173/100)
>>>=20
...
>>> trace =3D 0
>>> path2frac(root_list) # the one of PV
(17083879020/9863382151)
>>>=20
Hope, you found this interesting
Gregor
-------------------------------------------------------------------------=
-
P.S.: In my eyes the lack of class-methods in Python is still=20
a little bit annoying.
------=_NextPart_000_0088_01C198BC.DC399780
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 6.00.2600.0" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT size=3D2>
<DIV><FONT face=3DArial size=3D2>Dear all,</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>inspired by PV's Stern-Brocot-program I =
thought=20
this to be an ideal opportunity</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>to try out Kirby's =
fraction-objects.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>I produced a slightliy enhanced version =
of the F=20
class in order</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>to have 'big fractions' and to be able =
to compare=20
them.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Moreover I used the strange but =
convenient fact=20
that this class allows</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>the definition of the fraction =
1/0.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Then I developed another recursive =
solution=20
(considering trees to be naturally</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>recursive data-structures) - may be =
it's=20
mathematically less pretentious, but </FONT></DIV>
<DIV><FONT face=3DArial size=3D2>it works.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Here is the code of the =
program:</FONT></DIV>
<DIV> </DIV>
<DIV>def median(l, r):<BR> return F(l.num+r.num,=20
l.den+r.den)</DIV>
<DIV> </DIV>
<DIV>### Stern-Brocot-tree-traversal back and forth</DIV>
<DIV> </DIV>
<DIV>trace =3D 0</DIV>
<DIV> </DIV>
<DIV>def frac2path(f, path =3D [], left =3D F(0,1), right =3D=20
F(1,0)):<BR> m =3D =
median(left,right)<BR> if=20
trace: print m<BR> if f =3D=3D=20
m:<BR> return=20
path<BR> elif f <=20
m:<BR> return frac2path(f, =
path+["L"],=20
left, m)<BR> =20
else:<BR> return frac2path(f,=20
path+["R"], m, right)</DIV>
<DIV> </DIV>
<DIV>def path2frac(p, left =3D F(0,1), result =3D F(1,1), right =3D=20
F(1,0)):<BR> if not=20
p:<BR> return=20
result<BR> if trace: print =
result<BR> if=20
p[0]=3D=3D"L":<BR> return =
path2frac(p[1:],=20
left, median(left,result), result)<BR> =20
else:<BR> return =
path2frac(p[1:],=20
result, median(result,right), right)<BR> <BR>### =
Kirby's=20
fraction-class, slightly enhanced</DIV>
<DIV> </DIV>
<DIV>class F:</DIV>
<DIV> </DIV>
<DIV> def=20
__init__(self,numer,denom):<BR> =
#=20
reduce inputs to lowest =
terms<BR> =20
numer =3D long(numer) # =
NEW: for=20
'big fractions'<BR> denom =3D=20
long(denom)<BR> gcd =3D=20
self.gcd(numer,denom)<BR> =
self.num =3D=20
numer//gcd<BR> self.den =3D=20
denom//gcd</DIV>
<DIV> </DIV>
<DIV> def=20
__add__(self,other):<BR> # =
find lowest=20
common multiple<BR> a,b =3D =
self.num,=20
other.num<BR> comden =3D=20
self.lcm(self.den, =
other.den)<BR> if=20
comden !=3D=20
self.den:<BR> =
a *=3D=20
comden//self.den<BR> if comden =
!=3D=20
other.den:<BR>  =
; b *=3D=20
comden//other.den<BR> return=20
F(a+b,comden)</DIV>
<DIV> </DIV>
<DIV> def=20
__sub__(self,other):<BR> =
return self +=20
(-other)</DIV>
<DIV> </DIV>
<DIV> def=20
__neg__(self):<BR> return=20
F(-self.num,self.den)</DIV>
<DIV> </DIV>
<DIV> def=20
__lt__(self,other): # NEW: for =
comparison:=20
m<n<BR> return =
(self.num*other.den)=20
< (other.num*self.den)</DIV>
<DIV> </DIV>
<DIV> def=20
__eq__(self,other): # NEW: for =
comparison:=20
m=3D=3Dn<BR> return =
(self.num*other.den)=20
=3D=3D (other.num*self.den)</DIV>
<DIV> </DIV>
<DIV> def=20
gcd(self,a,b):<BR> # find =
greatest=20
common divisor of a,b<BR> if =
b=3D=3D0:=20
return a<BR> else: return=20
self.gcd(b,a%b)</DIV>
<DIV> </DIV>
<DIV> def=20
lcm(self,a,b):<BR> # find =
lowest=20
common multiple of a,b<BR> =
return=20
a*b//self.gcd(a,b)</DIV>
<DIV> </DIV>
<DIV> def=20
__repr__(self):<BR> # =
represent as=20
(a/b)<BR> return "(%s/%s)" %=20
(self.num, self.den)</DIV>
<DIV> </DIV>
<DIV>### And now a test - run:</DIV>
<DIV> </DIV>
<DIV>>>> frac2path(F(173,100))<BR>['R', 'L', 'R', 'R', 'L', =
'R', 'R',=20
'L', 'L', 'R', 'L']<BR>>>> path2frac(['R', 'L', 'R', 'R', 'L', =
'R',=20
'R', 'L', 'L', 'R', 'L'])<BR>(173/100)<BR>>>> trace =3D =
1<BR>>>>=20
frac2path(F(173,100))<BR>(1/1)<BR>(2/1)<BR>(3/2)<BR>(5/3)<BR>(7/4)<BR>(12=
/7)<BR>(19/11)<BR>(26/15)<BR>(45/26)<BR>(64/37)<BR>(109/63)<BR>(173/100)<=
BR>['R',=20
'L', 'R', 'R', 'L', 'R', 'R', 'L', 'L', 'R', 'L']<BR>>>>=20
path2frac(['R', 'L', 'R', 'R', 'L', 'R', 'R', 'L', 'L', 'R',=20
'L'])<BR>(1/1)<BR>(2/1)<BR>(3/2)<BR>(5/3)<BR>(7/4)<BR>(12/7)<BR>(19/11)<B=
R>(26/15)<BR>(45/26)<BR>(64/37)<BR>(109/63)<BR>(173/100)<BR>>>> =
</DIV>
<DIV>...</DIV>
<DIV>>>> trace =3D 0</DIV>
<DIV>>>> path2frac(root_list) # the one of=20
PV<BR>(17083879020/9863382151)<BR>>>> <BR></DIV>
<DIV>Hope, you found this interesting</DIV>
<DIV>Gregor</DIV>
<DIV> </DIV>
<DIV>--------------------------------------------------------------------=
------</DIV>
<DIV>P.S.: In my eyes the lack of class-methods in Python is still =
</DIV>
<DIV>a little bit annoying.</DIV>
<DIV><FONT face=3DArial></FONT> </DIV></FONT></DIV></BODY></HTML>
------=_NextPart_000_0088_01C198BC.DC399780--