Fast GCD and LCM algorithms
The following code snippets demonstrate the programmatic solution to the fundamental integer-math problems of finding:
- Greatest Common Divisor, or GCD
- Least Common Multiple, or LCM
The solution is implemented as managed .NET code written in C# 4, applicable to the previous versions as well. It is portable to other languages, most notably, to the VB family (VB/VBA/VB.NET), Java and JavaScript as well, provided that the syntax differences are properly addressed. Another Prime Factoring and corresponding Primality test algorithm has been described in the previous post on CodeProject [1].
using System;
namespace Infosoft.Fractions
{
public static partial class Integers
{
#region GCD of two integers
public static Int64 GCD( Int64 Value1, Int64 Value2)
{
Int64 a;
Int64 b;
Int64 _gcd = 1;
try
{
if(Value1==0 || Value2==0) {
throw new ArgumentOutOfRangeException();
}
a = Math.Abs(Value1);
b = Math.Abs(Value2);
if (a==b) {return a;}
else if (a>b && a % b==0) {return b;}
else if (b>a && b % a==0) {return a;}
while (b != 0) {
_gcd = b;
b = a % b;
a = _gcd;
}
return _gcd;
}
catch { throw; }
}
#endregion
#region LCM of two integers
public static Int64 LCM(Int64 Value1, Int64 Value2)
{
try
{
Int64 a = Math.Abs(Value1);
Int64 b = Math.Abs(Value2);
a = checked((Int64)(a / GCD(a, b)));
return checked ((Int64)(a * b));
}
catch { throw; }
}
#endregion
}
}
Notice that checked
keyword ensures that the algorithm properly raises the exception in case of overflow, so preventing the potentially erroneous results being unchecked and returned by function.
References
1. Fast Prime Factoring Algorithm[^]