Skip to content

Instantly share code, notes, and snippets.

@luis-fss
Created January 8, 2012 01:15
Show Gist options
  • Save luis-fss/1576706 to your computer and use it in GitHub Desktop.
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
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
@luis-fss
Copy link
Author

luis-fss commented Jan 8, 2012

See the blog post here for the description: http://www.blackwasp.co.uk/SteinsAlgorithm.aspx
Feel free to use and/or modify the code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment