Control Structures

Control statements provide the facility to switch the flow of control in a program. Python provides a few control statements like if-else, while and for.

• if-else is for conditional switching of the control.

• for and while for doing something repeatedly.

Almost all programs utilize these control statements to accomplish the task at hand or to solve the given problem.

Problem and Solution.

Let's demonstrate a while loop using Euclid's algorithm for finding the greatest common divisor.

The greatest common divisor (GCD) of two numbers, is the largest number that divides both of them without leaving a remainder. As given in this example from Math is Fun the greatest common divisor of 12 and 16 is 4.

gcd

An efficient way to formulate GCD was given by Euclid.

To find the GCD of A, B, given A > B.

1. If A divided by B is 0, then GCD is B.

2. Otherwise, calculate Reminder R of A divided by B. (R = A mod B).

3. Find out GCD(B, R), that is subsitute B for A, R and R for B, go to step 1 which calculates GCD.

The explanation of this euclid algorithm explained well by Alexander Bogomolny in his cut the knot

Problem Credits: Think Python Exercise, SICP, and Euclid's Algorithm.

Write tests first.

We will skip past the undefined NameError and for an undefined gcd function and write a gcd function that returns a 0.

def gcd(A :int, B : int) -> int:
    return 0


def test_gcd():
    gcd(12, 16) == 4, "GCD was incorrect."

Exercise tests.

Exercising this test, we get the AssertionError.

Traceback (most recent call last):
  File "gcd/gcd_test1.py", line 10, in <module>
    test_gcd()
  File "gcd/gcd_test1.py", line 6, in test_gcd
    assert gcd(12, 16) == 4, "GCD was incorrect."
AssertionError: GCD was incorrect.

Fix tests.

Let's follow the Euclid's algorithm to fix the tests.

def gcd(A :int, B : int) -> int:
    if A % B == 0:
        return B

    R = A % B

    while R != 0:
        A = B
        B = R
        R = A % B
        if R == 0:
            return B

The program follows our understanding of the Euclid's algorithm.

And exercising the test showed that the program worked properly.

$ python gcd/gcd_test2.py  -v
$

Refactor

There are a few avenues for refactor in the above code. The first one is, return statement.

if R == 0:
   return B

If the variable R is 0, then our while loop will exit and we could utilize that fact to return our result.

def gcd(A : int, B : int) -> int:
    if A % B == 0:
        return B

    R = A % B

    while R != 0:
        A = B
        B = R
        R = A % B

    return B

And then, if we observe carefully, the first statement can be removed. Because we are calculating A % B and comparing it with 0.

def gcd(A :int, B : int) -> int:
    R = A % B
    while R != 0:
        A = B
        B = R
        R = A % B

    return B

Could we refactor this further? Yes, our verification for for step 1 can be made in the while statement itself.

def gcd(A :int, B : int) -> int:
    while (A % B) != 0:
        A = B
        B = R
        R = A % B

    return B


def test_gcd():
    assert gcd(12, 16) == 4, "GCD was incorrect."
    assert gcd(4, 2) == 2, "GCD was incorrect"

Exercising this will result in an Error.

/home/senthil/anaconda3/envs/xtoinfinity/bin/python /home/senthil/github/learn-python-with-tests/gcd/gcd_test6.py
Traceback (most recent call last):
  File "/home/senthil/github/learn-python-with-tests/gcd/gcd_test6.py", line 17, in <module>
    test_gcd()
  File "/home/senthil/github/learn-python-with-tests/gcd/gcd_test6.py", line 12, in test_gcd
    assert gcd(12, 16) == 4, "GCD was incorrect."
  File "/home/senthil/github/learn-python-with-tests/gcd/gcd_test6.py", line 5, in gcd
    B = R
UnboundLocalError: local variable 'R' referenced before assignment

The error indicates that we use the variable R ahead of its assignment. Our logical usage is incorrect as well. We can correct the code as per the algorithm above.

def gcd(A :int, B : int) -> int:
    while (A % B) != 0:
        R = A % B
        A = B
        B = R

    return B

And exercise this code results in a success.

At this moment, I decided to stop because any further refactoring, like calculating A % B only once will lead to edge cases, which can be confusing.

The code follows our algorithm to the dot, and easy to remember.

Final Code

The final solution looks like this. And this works for number in any order.

def gcd(A :int, B : int) -> int:
    while (A % B) != 0:
        R = A % B
        A = B
        B = R

    return B


def test_gcd():
    assert gcd(16, 12) == 4, "GCD was incorrect"
    assert gcd(12, 16) == 4, "GCD was incorrect."
    assert gcd(4, 2) == 2, "GCD was incorrect"
    assert gcd(2, 4) == 2, "GCD was incorrect"


if __name__ == '__main__':
    test_gcd()