78 

    79 Let us put all these in a file and call this file **gcd.py**::

    80 

    81   def gcd(a, b):

    82       pass

    83 

    84   if __name__ == '__main__':

    85       tc1 = gcd(48, 64)

    86       if tc1 != 16:

    87           print "Test failed for the case a=48 and b=64. Expected 16. Obtained %d instead." % tc1

    88           exit(1)

    89 

    90       tc2 = gcd(44, 19)

    91       if tc2 != 1:

    92           print "Test failed for the case a=44 and b=19. Expected 1. Obtained %d instead." % tc2

    93           exit(1)

    94 

    95       print "All tests passed!"

    96 

    97 Note that we have introduced a new semantic which uses two new magic names

    98 in Python *__name__* and *__main__*. This is a very common idiom used in

    99 Python. Every Python code in a file can be run in two ways: Either as an

   100 independent stand-alone script or as a Python module which can be imported

   101 by other Python scripts or modules. When the idiom::

   102 

   103   if __name__ == '__main__':

   104 

   105 is used, the code within this if block is executed first when we run the

   106 Python file as a stand-alone script. In other words, when we run this

   107 python file as a stand-alone script the control of the program first starts

   108 from the code that is within this if block from which the control is

   109 transferred to other parts of the program or to other modules from

   110 here. This comes as an extremely handy feature especially when we want to

   111 test our modules individually. Now let us run our code as a stand-alone

   112 script.::

   113 

   114   madhu@madhu:~/Desktop$ python gcd.py

   115   Traceback (most recent call last):

   116     File "gcd.py", line 7, in <module> print "Test failed for the case a=48 and b=64. Expected 16. Obtained %d instead." % tc1

   117   TypeError: %d format: a number is required, not NoneType

   118 

   119 Now we have our tests, the test cases and the code unit stub at

   120 hand. We also have the failing test. So we know for sure that we have

   121 cleared the first check point of TDD where the tests have failed. The

   122 failing tests also give a green signal for us to go ahead to our next

   123 check point i.e. to write the actual code in our code unit and make

   124 the test pass. So let us write the code for the gcd function by

   125 removing the **pass** control statement which had just created a gcd

   126 function stub for us.

   127 

   128 Most of us have learnt in high school math classes that the best and

   129 the easiest known algorithm to compute the gcd of two numbers was

   130 given to us 2300 years ago by a greek mathematician named Euclid. So

   131 let us use the Euclid's algorithm to compute the gcd of two numbers a

   132 and b::

   133 

   134   def gcd(a, b):

   135       if a == 0:

   136           return b

   137       while b != 0:

   138           if a > b:

   139               a = a - b

   140           else:

   141               b = b - a

   142       return a

   143 

   144 **Note**: If you are unaware of Euclidean algorithm to compute the gcd

   145 of two numbers please refer to it on wikipedia. It has a very detailed

   146 explanation of the algorithm and its proof of validity among other

   147 things.

   148 

   149 Now let us run our script which already has the tests written in it

   150 and see what happens::

   151 

   152   madhu@madhu:/media/python/sttp/tdd$ python gcd.py

   153   All tests passed!

   154 

   155 Success! We managed to pass all the tests. But wasn't that code simple

   156 enough? Indeed it was. If you take a closer look at the code you will

   157 soon realize that the chain of subtraction operations can be replaced

   158 by a modulo operation i.e. taking remainders of the division between

   159 the two numbers since they are equivalent operations. Also modulo

   160 operation is far better than chain of subtractions because you will

   161 reduce much faster using modulo operation than the subtraction. For

   162 example if let us take 25, 5 as a and b in our example. If we write

   163 down the steps of the algorithm written above we have the following:

   164 

   165 Step 1: a = 25 b = 5: Since both a and b are not 0 and b is greater

   166 than a: b = 25 - 5 = 20

   167 Step 2: Since b is still not 0 and b is greater than a: b = 20 - 5 =

   168 15

   169 Step 3: Since b is still not 0 and b is greater than a: b = 15 - 5 =

   170 10

   171 Step 4: Since b is still not 0 and b is greater than a: b = 10 - 5 = 5

   172 Step 5: Since b is still not 0 and b is equal to a: b = 5 - 5 = 0

   173 Step 6: Since b is 0 the gcd is a = 5 which is returned

   174 

   175 If we adopt the modulo operation instead of subtraction and follow the

   176 steps:

   177 

   178 Step 1: a = 25 b = 5: Since both a and b are not 0 and b is greater

   179 than a: b = 25 % 5 = 0

   180 Step 2: Since b is 0 the gcd is a = 5 which is returned

   181 

   182 Wow! That was overwhelmingly lesser number of steps! So now we are

   183 convinced that if we replace the subtraction operation with the modulo

   184 operation our code performs much better. But if we think carefully we

   185 know that the modulo of a and b is less than b irrespective of how

   186 large the value of a is, including the case where a is already less

   187 than b. So we can eliminate that extra conditional **if** statement by

   188 just swapping the result of the modulo operation to the position of b

   189 and b to the position of a. This ensures that a is always greater than

   190 b and if not the swapping combined with modulo operation takes care of

   191 it. To exemplify it, if a = 5 and b = 25 then by swapping and

   192 performing modulo we have a = b = 25 and b = a % b = 5 % 25 = 5 and

   193 hence we proceed. So let us replace our original code with this new

   194 improved code we have come up with simple observations::

   195 

   196   def gcd(a, b):

   197       while b != 0:

   198           a, b = b, a % b

   199       return a

   200 

   201 Executing our script again we will see that all the tests pass. One

   202 final improvement we can think of which is not necessary in terms of

   203 efficiency but is certainly good to do keeping in mind the readability

   204 is that we can use the concept of recursion for the same

   205 algorithm. Without going into much detail this is how the code looks

   206 if we use a recursive approach::

   207 

   208   def gcd(a, b):

   209       if b == 0:

   210           return a

   211       return gcd(b, a%b)

   212 

   213 Much shorter and sweeter! And it passes all the tests!

   214