The following example solves a classic elementary problem: "Reduce a given fraction to its lowest terms", e.g. we want to write 2/3, not 4/6. We solve this problem by finding the greatest common divisor (gcd) of the numerator and the denominator by using the famous approach called Euclid's algorithm.
1 function euclid (a, b: in positive) return positive 2 is 3 t : integer; 4 r : integer := a; 5 begin 6 discrete s := b in reverse 1..b 7 new s := r mod s 8 loop 9 t := r mod s; 10 r := s; 11 s := t; 12 end loop; 13 return r; 14 end euclid;
[ Sourcefile ]
After the two positive non-zero integers whose gcd is being sought are established, the remainder from dividing the larger integer by the smaller integer is calculated. Then the smaller integer assumes the role of the larger one and the remainder assumes the role of the divisor. This is repeated until a zero remainder is obtained.
A worst case situation occurs when a and b are two adjacent Fibonacci numbers, because in this case the remainders follow the Fibonacci sequence until zero is obtained. Then the number of iterations is bounded by the number of terms in the Fibonacci sequence up to the point that includes the original integers a and b. It can be shown that in this case there will be log(sqrt(5N))-2 iterations where N is the smallest Fibonacci number greater than the larger of a and b, and the logarithm has the base 0.5*(1+sqrt(5)).
[AHU74, p. 300] [BB93, p. 35] [BKR91, p. 10] [Dro82, p. 98] [Sed88, p. 8]
[ Samples Overview | Bibliography | WOOP Project ]