Binary GCD algorithm implementation with python

Binary GCD algorithm also known as Stein's algorithm is an improved version of Euclidean Algorithm.It takes two integer inputs and finds the Greatest Common Divisor(GCD) of the two numbers. The algorithm uses recursive techniques to find the GCD of the two numbers.

Program

File: binary_gcd.py ------------------------- def gcd(u, v): """ This function will calcluate GCD of given two numbers. If the input is negative, both the numbers are converted to positive before the calculation """ u = abs(u) v = abs(v) if u == v: return u elif u == 0: return v elif v == 0: return u # u is even elif u & 1 == 0: # v is even if v & 1 == 0: return 2*gcd(u >> 1, v >> 1) # v is odd else: return gcd(u >> 1, v) # u is odd elif u & 1 != 0: # v is even if v & 1 == 0: return gcd(u, v >> 1) # v is odd and u is greater than v elif u > v and v & 1 != 0: return gcd((u-v) >> 1, v) # v is odd and u is smaller than v else: return gcd((v-u) >> 1, u)

This program doesn't accept negative numbers at all. If you give a negative number as input then you will get an error during runtime. This program doesn't accept negative numbers as input. If the user gives one or both the negative numbers then a runtime error is raised.

We could have added u = abs(u) and v = abs(v), but this will have an effect on the performance of the program. As we are using recursive program, for each and every function call the above two statements gets executed which is not at all necessary.

To find the GCD of two numbers, there are 8 cases. They are as follows:(Assume that the input is two integers u and v, gcd is the name of our function)

u and v are the same. For this condition, the GCD is the same as any of the two numbers.
Value of u is 0. Then the GCD is v.
Value of v is 0. GCD will be u.
u is even v is even. Then the GCD of the two numbers will be 2*gcd(u/2, v/2)(Because 2 is the common factor). So here we are using the recursive function call.
u is even v is odd. In this case GCD will be gcd(u/2, v)(Because 2 is never gonna make into the value of GCD). Again a recursive functional call.
u is odd v is even. GCD will be gcd(u, v/2)(Similar to the above case).
u is odd v is odd and u > v. Then the GCD will be gcd((u-v)/2, v). This case is to ensure that the input given to the gcd function will not be a negative integer.
u is odd v is odd and u < v. GCD will be gcd((v-u)/2, u). This case is similar to the above one.

The same has been written in the program but we have used a lot fo binary arithmetic. This is to ensure that the execution time is minimized as much as possible. Some of the binary arithmetic used in the program are as follows:

variable & 1 gives 0 when the number is even and 1 when the number is odd.
variable >> 1 divides the number by 2.
variable << 1 multiplies the number by 2

You can learn more about these Bitwise operators on Python wiki

These three operations execute their respective arithmetic in an efficient manner.

Non recursive version

Till now we have seen the recursive program which uses the same function again and again to return the final value. But the following program will only use loops to find the value. The program is as follows:

File: binary_gcd_nr.py ------------------------- def gcd(u, v): """ A non recursive function while takes two integers as input and returns the GCD of the numbers """ # if u is 0, return v if u == 0: return v # if v is 0, return u if v == 0: return u # make sure u is positive u = abs(u) # make sure v is positive v = abs(v) # temporary varible to store # the common factors of 2 k = 1 # run this loop until u or v becomes odd while u & 1 == 0 and v & 1 == 0: k <<= 1 u >>= 1 v >>= 1 # remove all the remaining powers of 2 while u & 1 == 0: u >>= 1 # remove all the remaining powers of 2 while v & 1 == 0: v >>= 1 # run the while loop while v != 0: # check if u > v if u > v: # swap the values u, v = v, u v = v - u # return value return u*k

The program is very much self explanatory, but I will give a brief description about what actually is happening in the background.

We will take u and v and find the highest power of 2 common between them. For example if 4 and 32 are taken then the highest power of 2 common between them is 2².

After that we will remove all the excess powers of 2's in u and v which will however not contribute to the final answer.

Now we only have two odd numbers and you can see the code implementation of cases 6 and 7 in the program.

From python 2.6, there is an inbuilt gcd function which will calculate the GCD of two numbers. You can import the function and use it directly.
As always you can download the file from here: Github Gist binary_gcd.py, Github Gist binary_gcd_nr.py and Github Gist fractions_gcd.py.

If you want to learn more about the GCD algorithm, then you can visit the following websites:
GCD algorithm Wiki
binary GCD
Binary GCD mathematical Garden
GCD - Rosetta Code

If you have any doubt or haven't understood anything feel free to comment in the comment box and I will be glad to help you.

If you have any suggestions or have a different implementation of the program then please comment in the comment box below and I will be very happy to see your comment.

Please comment if you have found any typo or execution errors if any.

You can also contact me

Thank you. Have a nice day.

RADIUS OF CIRCLE

Search This Blog