THINK FIRST·CODE LATER

← All labs

Euclid's algorithm: how many steps?

Problem

Write EuclidSteps, which reads pairs of positive integers until the end of the input and computes their greatest common divisor twice:

  1. counting down: start from the smaller number and decrease the candidate until it divides both — count the decrements;
  2. 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?

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d7-9-data-1.txt

48 36
1071 462
832040 514229
1000000 999999
17 17
What your program must print for d7-9-data-1.txt
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)

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d7-9-data-1.txt

Windows PowerShell does not understand <:

Get-Content d7-9-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.