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))
{
results.Add(count);
}
}
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)) { results.Add(counter); } } return results; } public static bool IsCoprime(uint value1, uint value2) { returnFindGCDModulus(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.
