Created
January 8, 2012 01:15
-
-
Save luis-fss/1576706 to your computer and use it in GitHub Desktop.
greatest common divisor (GCD) for a pair of integers using the Stein's algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static uint Stein(uint value1, uint value2) | |
{ | |
if (value1 == 0) return value2; | |
if (value2 == 0) return value1; | |
if (value1 == value2) return value1; | |
bool value1IsEven = (value1 & 1u) == 0; | |
bool value2IsEven = (value2 & 1u) == 0; | |
if (value1IsEven && value2IsEven) | |
return Stein(value1 >> 1, value2 >> 1) << 1; | |
else if (value1IsEven && !value2IsEven) | |
return Stein(value1 >> 1, value2); | |
else if (value2IsEven) | |
return Stein(value1, value2 >> 1); | |
else if (value1 > value2) | |
return Stein((value1 - value2) >> 1, value2); | |
else | |
return Stein(value1, (value2 - value1) >> 1); | |
} | |
// usage: | |
int gcd = Stein(116150, 232704); // should return: 202 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
See the blog post here for the description: http://www.blackwasp.co.uk/SteinsAlgorithm.aspx
Feel free to use and/or modify the code.