Binary GCD implementation in php. Recursive version.

binaryGCDrecursive.php

function gcd_recursive($a, $b){
	/* computes and returns the greatest common divisor between a and b */
	
	/*
	 *	Binary GCD Algorithm, according to Wikipedia "binary GCD can be about 60% 
	 *	more efficient (in terms of the number of bit operations) on average than the Euclidean algorithm".

	 *	More about the Binary GCD Algorithm: http://en.wikipedia.org/wiki/Binary_GCD_algorithm
	 *	Java Implementation: http://introcs.cs.princeton.edu/java/23recursion/BinaryGCD.java.html
	 *  C++ Implementation: https://gist.github.com/cslarsen/1635213

	 */

	/* NOTE:
		This is a recursive version of the binary GCD algorithm, however, the iteratibe version will be used instad,
		since this creates a very deeps recursion for large numbers, which may cause it not work without altering php's 
		default settings.
	*/
	if ($a==0)
		return $p;
	if ($b == 0)
		return $a;

	// if both a and b are even
	if(($a & 1) == 0 && ($b & 1) == 0)
		return gcd($a >> 1, $b >> 1) << 1;

	// if a is even and b is odd
	else if (($a & 1) == 0)
		return gcd($a >> 1, $b);

	// if a is odd and b is even
	else if (($b & 1) == 0 )
		return gcd($a, $b >> 1);

	// if both a and b are odd and a >= b
	else if($a >= $b)
		return gcd(($a - $b) >> 1, $b);

	// if both a and b are odd and a < b
	else
		return gcd($a, (1-$a) >> 1);


	/*
	 *	NOTE: Doing (inetger & 1) check if it's even.
	 *		  Example: 1 --> 0001
	 *		  		   6 --> 0110
	 *		  		   0001 & 0110 ---> 0000 (which is 0)
	 *
	 *		  		   1 --> 0001
	 *		  		   7 --> 0111
	 *		  		   0001 & 0111 ---> 0001 (which is 1)
	*/
}