TDD Beyond Basics : Greatest Common Divisor

Objective


Learn how to apply the reduction process to solve problems.

Problem Statement


Given two positive non-zero integers n and m, find their greatest common divisor (gcd). The gcd of two integers is the largest integer that will divide exactly into the two integers with no remainder.

Example 1


Here is a worked out example of GCD of 8 and 12.

alt text

In the second division, we can divide both numbers without any remainder. So GCD of 8 and 12 is 4.

Example 2


Let's consider the GCD of 54 and 24. The number 54 can be expressed as a product of two other integers in several different ways.

54 x 1 = 27 x 2 = 18 x 3 = 9 x 6

Thus the divisors of 54 are

1,2,3,6,9,18,27,54

Similarly the divisors of 24 are:

1,2,3,4,6,8,12,24

The number that these two lists share in common are the common divisors of 54 & 24. In this case, they are : 1,2,3,6. The greatest of these is 6. That is the GCD of 54 & 24.

Steps to Solve the Problem


Basic strategy for computing the gcd of two numbers:

  1. Divide the larger of the two numbers by the smaller number.

  2. If the smaller number exactly divides into the larger number then the smaller number is the GCD else : remove from the larger number the part common to the smaller number and repeat the whole procedure with the new pair of numbers.

Let's apply the above steps to calcaulate gcd(18,30):

alt text

The above diagram shows the reduction process. Reduction is process where the original problem is reduced to a smaller problem in each iteration until the given problem is solved.

alt text

Iterative Construct


With each reduction in the problem size the smaller integer assumes the role of the larger integer and the remainder assumes the role of the smaller integer. The reduction in problem size and role changing steps change the divisor, dividend and the remainder. The exact division will correspond to a 0 remainder.

while non-zero remainder do
  continue search for gcd
end

Initial Conditions


Before entering the loop we need remainder for terminating condition check, So:

  1. Compute remainder for original pair of integers
  2. Search for gcd until 0 remainder
while non-zero remainder
  continue search for gcd
end

Euclidean Algorithm


  1. Take the two positive non-zero integers smaller and larger.
  2. Repeat
  3. Get the remainder from dividing the larger integer by the smaller integer.
  4. Let the smaller integer assume the role of the divisor until a 0 remainder is obtained.
  5. Return the GCD

alt text

These three steps is illustrated in a 2 minutes video of Euclidean Algorithm on YouTube.

Steps


Step 1

Create gcd_spec.rb and add the first test as follows:

describe 'Gcd' do
  it 'should find the bigger number' do
    gcd = Gcd.new(12,30)
    result = gcd.bigger_number

    expect(result).to eq(30)    
  end
end

Step 2

Here is the minimal implementation that will make the test pass.

class Gcd
  def initialize(x, y)
    @x = y
    @y = y
  end

  def bigger_number
    if @x > @y
      @x
    else
      @y
    end
  end
end

Step 3

Add the second test as follows:

it 'should return 4 for 8 and 12' do
  gcd = Gcd.new(8,12)
  result = gcd.calculate

  expect(result).to eq(4)    
end

Step 4

Look at the algorithm we developed earlier. Here is the quick and dirty implementation based on that algorithm that passes.

class Gcd
  def initialize(x, y)
    @x = x
    @y = y
  end

  def bigger_number
    if @x > @y 
      @bigger_number = @x
      @smaller_number = @y
    else
      @bigger_number = @y
      @smaller_number = @x      
    end
    @bigger_number
  end

  def reduce
    bigger_number
    remainder = 1
    divident = @bigger_number
    divisor = @smaller_number  
    while remainder != 0
      remainder = divident % divisor
      divident = divisor
      divisor = remainder
    end
    divident
  end

  def calculate
    reduce
  end
end

Step 5

Let's change the while to until to make it idiomatic. In this case we keep looping as long as the remainder is not zero.

while remainder != 0

becomes

until remainder == 0

which says, keep looping and exit loop when the remainder becomes zero.

Step 6

Let's add another example:

it 'should return 6 for 54 and 24' do
  gcd = Gcd.new(24,54)
  result = gcd.calculate

  expect(result).to eq(6)    
end

It passes.

Step 7

Let's add another example:

it 'should return 6 for 12,30' do
  gcd = Gcd.new(12,30)
  result = gcd.calculate

  expect(result).to eq(6)
end

It passes. Our solution is generic to handle any cases.

Step 8

Here is the final version after cleanup, gcd_spec.rb:

class Gcd
  def initialize(x, y)
    @x = x
    @y = y
    initialize_numbers
  end

  def initialize_numbers
    if @x > @y 
      @bigger_number = @x
      @smaller_number = @y
    else
      @bigger_number = @y
      @smaller_number = @x      
    end
  end

  def calculate
    remainder = 1
    divident = @bigger_number
    divisor = @smaller_number  
    until remainder == 0
      remainder = divident % divisor
      divident = divisor
      divisor = remainder
    end
    divident
  end

end


describe 'Gcd' do  
  it 'should return 4 for 8 and 12' do
    gcd = Gcd.new(8,12)
    result = gcd.calculate

    expect(result).to eq(4)    
  end

  it 'should return 6 for 54 and 24' do
    gcd = Gcd.new(24,54)
    result = gcd.calculate

    expect(result).to eq(6)    
  end

  it 'should return 6 for 12,30' do
    gcd = Gcd.new(12,30)
    result = gcd.calculate

    expect(result).to eq(6)
  end

end

We have deleted the test that was coupled to the implementation. It is now in the constructor. The reduce method is deleted.

Exercise


Add the following test:

it 'should return 6 for 12,30' do
  gcd = Gcd.new(12,30)
  result = gcd.calculate

  expect(result).to eq(6)
end

Does it pass? Do you want to retain or delete this new test? Why?


Related Articles


Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.