program Kevin;
Uses SysUtils, Breuken;
function tiende(n : integer) : integer;
{
10^n
}
var
uit,k : integer;
begin
uit := 1;
for k := 0 to n-1 do
begin
uit := uit*10;
end;
tiende := uit;
end;
procedure Stern_Brocot(number : double);
{
Walk through Stern-Brocot tree
until fraction = (small) float
}
var
m1,m2,n1,n2 : integer;
L,tel : integer;
s : string;
B : breuk;
OK : boolean;
begin
OK := (0 < number) and (number < 1);
if not OK then
begin
Writeln('0 < ',number,' < 1 : not done');
Exit;
end;
s := floattostr(number);
L := Length(s);
s := Copy(s,3,L);
{ Writeln(number,' = ',s,'/',tiende(L-2)); }
B := maak(strtoint(s),tiende(L-2));
{ Initialize tree }
m1 := 0; n1 := 1;
m2 := 1; n2 := 1;
tel := 0;
while true do
begin
if (n1+n2)*B.teller = (m1+m2)*B.noemer then Break;
if (n1+n2)*B.teller < (m1+m2)*B.noemer then
{ Tightening }
begin
{ Upper Bound }
m2 := m1+m2;
n2 := n1+n2;
end else begin
{ Lower Bound }
m1 := m1+m2;
n1 := n1+n2;
end;
tel := tel + 1;
Writeln(m1,'/',n1,' < ',number,' < ',m2,'/',n2);
end;
Writeln(m1+m2,'/',n1+n2,' < ',number,' < ',m2+m1,'/',n2+n1);
Writeln('Iterations = ',tel);
end;
begin
Stern_Brocot(0.1989);
end.
Output:
0/1 < 1.98900000000000E-0001 < 1/2
0/1 < 1.98900000000000E-0001 < 1/3
0/1 < 1.98900000000000E-0001 < 1/4
0/1 < 1.98900000000000E-0001 < 1/5
1/6 < 1.98900000000000E-0001 < 1/5
2/11 < 1.98900000000000E-0001 < 1/5
3/16 < 1.98900000000000E-0001 < 1/5
4/21 < 1.98900000000000E-0001 < 1/5
5/26 < 1.98900000000000E-0001 < 1/5
6/31 < 1.98900000000000E-0001 < 1/5
7/36 < 1.98900000000000E-0001 < 1/5
8/41 < 1.98900000000000E-0001 < 1/5
9/46 < 1.98900000000000E-0001 < 1/5
10/51 < 1.98900000000000E-0001 < 1/5
11/56 < 1.98900000000000E-0001 < 1/5
12/61 < 1.98900000000000E-0001 < 1/5
13/66 < 1.98900000000000E-0001 < 1/5
14/71 < 1.98900000000000E-0001 < 1/5
15/76 < 1.98900000000000E-0001 < 1/5
16/81 < 1.98900000000000E-0001 < 1/5
17/86 < 1.98900000000000E-0001 < 1/5
18/91 < 1.98900000000000E-0001 < 1/5
19/96 < 1.98900000000000E-0001 < 1/5
20/101 < 1.98900000000000E-0001 < 1/5
21/106 < 1.98900000000000E-0001 < 1/5
22/111 < 1.98900000000000E-0001 < 1/5
23/116 < 1.98900000000000E-0001 < 1/5
24/121 < 1.98900000000000E-0001 < 1/5
25/126 < 1.98900000000000E-0001 < 1/5
26/131 < 1.98900000000000E-0001 < 1/5
27/136 < 1.98900000000000E-0001 < 1/5
28/141 < 1.98900000000000E-0001 < 1/5
29/146 < 1.98900000000000E-0001 < 1/5
30/151 < 1.98900000000000E-0001 < 1/5
31/156 < 1.98900000000000E-0001 < 1/5
32/161 < 1.98900000000000E-0001 < 1/5
33/166 < 1.98900000000000E-0001 < 1/5
34/171 < 1.98900000000000E-0001 < 1/5
35/176 < 1.98900000000000E-0001 < 1/5
36/181 < 1.98900000000000E-0001 < 1/5
36/181 < 1.98900000000000E-0001 < 37/186
36/181 < 1.98900000000000E-0001 < 73/367
36/181 < 1.98900000000000E-0001 < 109/548
36/181 < 1.98900000000000E-0001 < 145/729
36/181 < 1.98900000000000E-0001 < 181/910
36/181 < 1.98900000000000E-0001 < 217/1091
253/1272 < 1.98900000000000E-0001 < 217/1091
470/2363 < 1.98900000000000E-0001 < 217/1091
687/3454 < 1.98900000000000E-0001 < 217/1091
904/4545 < 1.98900000000000E-0001 < 217/1091
1121/5636 < 1.98900000000000E-0001 < 217/1091
1338/6727 < 1.98900000000000E-0001 < 217/1091
1555/7818 < 1.98900000000000E-0001 < 217/1091
1772/8909 < 1.98900000000000E-0001 < 217/1091
1989/10000 < 1.98900000000000E-0001 < 1989/10000
Iterations = 54