Thursday, August 1, 2013

Greatest common divisor & Co-primeness

Below are three different methods for finding the greatest common divisor of a number. I provide a method using modulus, one using Euclid's method, and one that uses the Stein method.

Believe it or not, the modulus method has the best performance. I would have guessed the Stein method. Credit goes to blackwasp for the stein method.

``````
public static uint FindGCDModulus(uint value1, uint value2)
{
while(value1 != 0 && value2 != 0)
{
if (value1 > value2)
{
value1 %= value2;
}
else
{
value2 %= value1;
}
}
return Math.Max(value1, value2);
}

public static uint FindGCDEuclid(uint value1, uint value2)
{
while(value1 != 0 && value2 != 0)
{
if (value1 > value2)
{
value1 -= value2;
}
else
{
value2 -= value1;
}
}
return Math.Max(value1, value2);
}

public static uint FindGCDStein(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 FindGCDStein(value1 >> 1, value2 >> 1) << 1;
}
else if (value1IsEven && !value2IsEven)
{
return FindGCDStein(value1 >> 1, value2);
}
else if (value2IsEven)
{
return FindGCDStein(value1, value2 >> 1);
}
else if (value1 > value2)
{
return FindGCDStein((value1 - value2) >> 1, value2);
}
else
{
return FindGCDStein(value1, (value2 - value1) >> 1);
}
}
``````

Here are the results of my benchmark tests:

Stein: 36.4657 milliseconds.
Euclid: 31.2369 milliseconds.
Modulus: 7.5199 milliseconds.

Yeah, I couldn't believe it either, the modulus approach is the fastest!

Here is the benchmark code that I created:
``````
public class CodeStopwatch
{
//int m_pointer;
Stopwatch m_elapsed;

public CodeStopwatch()
{
Reset();
}

public double Stop()
{
m_elapsed.Stop();
return m_elapsed.Elapsed.TotalMilliseconds;
}

public void Reset()
{
GC.Collect(GC.MaxGeneration);
m_elapsed = new Stopwatch();
m_elapsed.Start();
}
}

public class CoprimeBenchmark
{
public delegate bool IsCoprimeDelegate(uint value1, uint value2);
public List<uint> FindCoprimesDelegate(uint quantity,IsCoprimeDelegate isCoprime)
{
List<uint> results = new List<uint>();
if(quantity<2) {
return results;
}

for (uint count = 2; count < quantity; count++)
{
if(isCoprime(count,quantity))
{
}
}
return results;
}

public static bool IsCoprimeModulus(uint value1, uint value2)
{
return FindGCDModulus(value1, value2) == 1;
}

public static bool IsCoprimeEuclid(uint value1, uint value2)
{
return FindGCDEuclid(value1, value2) == 1;
}

public static bool IsCoprimeStein(uint value1, uint value2)
{
return FindGCDStein(value1, value2) == 1;
}

// [ Please refer to methods above. Ommited for brevity. ]
public static uint FindGCDModulus(uint value1, uint value2) { ... }
public static uint FindGCDEuclid(uint value1, uint value2) { ... }
public static uint FindGCDStein(uint value1, uint value2) { ... }
}
``````

Usage of above classes:
``````
// Button OnClick event
void ButtonBenchmarkClick(object sender, EventArgs e)
{
uint number = 50000;
List<uint> resultsStein = new List<uint>();
List<uint> resultsEuclid = new List<uint>();
List<uint> resultsModulus = new List<uint>();

CoprimeBenchmark cop = new CoprimeBenchmark();

CodeStopwatch time = new CodeStopwatch();
resultsStein = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeStein);
string stein = time.Stop().ToString();

time = new CodeStopwatch();
resultsEuclid = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeEuclid);
string euclid = time.Stop().ToString();

time = new CodeStopwatch();
resultsModulus = cop.FindCoprimesDelegate(number,CoprimeBenchmark.IsCoprimeModulus);
string modulus = time.Stop().ToString();

textBoxOutput.Text = "Stein:\t" + stein + " milliseconds." + Environment.NewLine;
textBoxOutput.Text += "Euclid:\t" + euclid + " milliseconds." + Environment.NewLine;
textBoxOutput.Text += "Modulus:\t" + modulus + " milliseconds." + Environment.NewLine;

textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
foreach(uint a in resultsStein)
{
textBoxOutput.Text += a.ToString() + Environment.NewLine;
}

textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
foreach(uint b in resultsEuclid)
{
textBoxOutput.Text += b.ToString() + Environment.NewLine;
}

textBoxOutput.Text += Environment.NewLine + Environment.NewLine;
foreach(uint c in resultsModulus)
{
textBoxOutput.Text += c.ToString() + Environment.NewLine;
}
}``````

--

Now, I will take the fastest algorithm and show you the code for finding co-primness and a list of co-primes for a given number.

Finding co-primness is simple; Two numbers are relatively prime to each other if their greatest common divisor is equal to one.

My function FindCoprimes returns a List<uint> of co-primes given a number and a range
``````
public static class Coprimes
{
public static List<uint> FindCoprimes(uint number,uint min,uint max)
{
if(max<2 || min<2 || max<=min || number<1) {    return null;    }

List<uint> results = new List<uint>();
for(uint counter = min; counter<max; counter++) {
if(IsCoprime(number,counter)) {
}
}
return results;
}

public static bool IsCoprime(uint value1, uint value2)
{
return ``````FindGCDModulus(value1, value2) == 1;
}
}
``````

Pretty easy!

What is so special about co-primes? Well, one thing I use co-primes for is for making an evenly distributed table. For an explanation and the code, see my post on Evenly Distributed Tables.