Write EuclidSteps, which reads pairs of positive integers until the end of the input and computes their greatest common divisor twice:
- counting down: start from the smaller number and decrease the candidate until it divides both — count the decrements;
- Euclid, recursively: gcd(a, 0) = a and gcd(a, b) = gcd(b, a mod b) — count the divisions.
For each pair, print the gcd, the two counts and Lamé's bound: Euclid never needs more than 5 × (number of decimal digits of the smaller number) divisions. For the input
48 36
1071 462
832040 514229
1000000 999999
17 17
the program prints
gcd(48, 36) = 12
counting down: 24 steps; Euclid: 2 divisions (never more than 5 x 2 digits = 10)
gcd(1071, 462) = 21
counting down: 441 steps; Euclid: 3 divisions (never more than 5 x 3 digits = 15)
gcd(832040, 514229) = 1
counting down: 514228 steps; Euclid: 28 divisions (never more than 5 x 6 digits = 30)
gcd(1000000, 999999) = 1
counting down: 999998 steps; Euclid: 2 divisions (never more than 5 x 6 digits = 30)
gcd(17, 17) = 17
counting down: 0 steps; Euclid: 1 divisions (never more than 5 x 2 digits = 10)
The pair 832040, 514229 consists of two consecutive Fibonacci numbers. What do you notice?