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

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

view raw binary_gcd.py hosted with ❤ by GitHub

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)

1.  u and v are the same. For this condition, the GCD is the same as any of the two numbers.
2. Value of u is 0. Then the GCD is v.
3. Value of v is 0. GCD will be u.
4. 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.
5. 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.
6. u is odd v is even. GCD will be gcd(u, v/2)(Similar to the above case).
7. 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.
8. 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:

	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

view raw binary_gcd_nr.py hosted with ❤ by GitHub

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.

	# import the function
	from fractions import gcd
	# use it directly
	print gcd(500, 5) #5

view raw fractions_gcd.py hosted with ❤ by GitHub

 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.