program Kevin;Output:
procedure Stern_Brocot(teller,noemer : integer); { Walk through Stern-Brocot tree until fraction = teller/noemer (English: numerator/denominator) } var m1,m2,n1,n2 : integer; begin { Initialize tree } m1 := 0; n1 := 1; m2 := 1; n2 := 0; while true do begin { if teller/noemer < (m1+m2)/(n1+n2) then } if (n1+n2)\*teller < (m1+m2)\*noemer then { Tightening } begin { Upper Bound } m2 := m1+m2; n2 := n1+n2; end else begin { Lower Bound } m1 := m1+m2; n1 := n1+n2; end; Writeln(m1,'/',n1,' < ',teller,'/',noemer,' < ',m2,'/',n2); if (teller/noemer = m1/n1) or (teller/noemer = m2/n2) then Break; end; end;
begin Stern_Brocot(5,7); end.
0/1 < 5/7 < 1/1 1/2 < 5/7 < 1/1 2/3 < 5/7 < 1/1 2/3 < 5/7 < 3/4 5/7 < 5/7 < 3/4From this output we derive the required sequence by hand (oh well, the whole thing could have been done by hand in this simple case, but it's useful to have such a computer program for e.g. approximating irrational numbers).
1/1 < 7/5 < 1/0 1/1 < 7/5 < 2/1 1/1 < 7/5 < 3/2 4/3 < 7/5 < 3/2 4/3 < 7/5 < 7/5Note that the closest smaller and larger ancestors are in the tree just before the algorithm halts.
EDIT. My favorite reference is this:
More impressive examples are obtained by calculating for irrational numbers, such as $1/\sqrt{2}$:if (n1+n2)\*(n1+n2) < (m1+m2)\*(m1+m2)\*2 thenGiving, after e.g. 45 iterations: $$ \frac{318281039}{225058681} < \sqrt{2} < \frac{768398401}{543339720} $$