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.
GCD and
LCM calculations are essential for fractions arithmetic: corresponding algorithms are implemented in the free online "
3 Fractions Calculator" (topping Google/Yahoo search list), available at:
http://webinfocentral.com/MATH/Fractions.aspx[
^].
Mobile version of the Fractions Calculator optimized for smart phones is available at [4]: you could see the image of Mobile Fraction Calculator running in iPad 2 (the picture has been taken at iPad 2 weekend in NY Apple store).
Another core Prime Factoring and corresponding Primality test algorithm has been described in the previous post on CodeProject [3]: corresponding demo is available at [2].
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.
Mobile Fraction Calculator on iPad 2
References
1.
3 Fraction Calculator (best on Google)[
^]
2.
Prime Factoring Calculator[
^]
3.
Fast Prime Factoring Algorithm[
^]
4.
Fraction Calculator, Mobile version[
^]