# 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.

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:

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

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):

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.

# 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:

- Compute remainder for original pair of integers
- Search for gcd until 0 remainder

```
while non-zero remainder
continue search for gcd
end
```

# Euclidean Algorithm

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

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