15,350,244 members
Articles / General Programming / Algorithms
Tip/Trick
Posted 24 Feb 2011

47.8K views
14 bookmarked

# Fast Integer Algorithms: Greatest Common Divisor and Least Common Multiple, .NET solution

Rate me:
.NET/C# managed code implementation of 2 core algorithms of integer arithmetic: GCD and LCM (used in "3 Fraction Calculator", best on Google)

### 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].
C#
//============================================================================
// Author           :   Alexander Bell
// Copyright        :   2007-2011 Infosoft International Inc
// Date Created     :   01/15/2007
// Description      :   Find Greatest Common Divisor (GCD) and
//                  :   Least Common Multiple (LCM)
//                  :   of two Int64 using Euclid algorithm
//============================================================================
// DISCLAIMER: This Application is provide on AS IS basis without any warranty
//****************************************************************************

//****************************************************************************
//                  :   You can use it at your sole risk provided that you keep
//                  :   the original copyright note.
//******************************************************************************
using System;

namespace Infosoft.Fractions
{
public static partial class Integers
{
#region GCD of two integers
/// <summary>
/// find Greatest Common Divisor (GCD) of 2 integers
/// using Euclid algorithm; ignore sign
/// </summary>
/// <param name="Value1">Int64</param>
/// <param name="Value2">Int64</param>
/// <returns>Int64: GCD, positive</returns>
public static Int64 GCD( Int64 Value1, Int64 Value2)
{
Int64 a;            // local var1
Int64 b;            // local var2
Int64 _gcd = 1;     // Greates Common Divisor

try
{
// throw exception if any value=0
if(Value1==0 || Value2==0)   {
throw new ArgumentOutOfRangeException();
}

// assign absolute values to local vars
a = Math.Abs(Value1);
b = Math.Abs(Value2);

// if numbers are equal return the first
if (a==b) {return a;}
// if var "b" is GCD return "b"
else if (a>b && a % b==0) {return b;}
// if var "a" is GCD return "a"
else if (b>a && b % a==0) {return a;}

// Euclid algorithm to find GCD (a,b):
// estimated maximum iterations:
// 5* (number of dec digits in smallest number)
while (b != 0) {
_gcd = b;
b = a % b;
a = _gcd;
}
return _gcd;
}
catch { throw; }
}
#endregion

#region LCM of two integers
/// <summary>
/// Find Least common Multiply of 2 integers
/// using math formula: LCM(a,b)= a*(b/GCD(a,b));
/// </summary>
/// <param name="Value1">Int64</param>
/// <param name="Value2">Int64</param>
/// <returns>Int64</returns>
public static Int64 LCM(Int64 Value1, Int64 Value2)
{
try
{
Int64 a = Math.Abs(Value1);
Int64 b = Math.Abs(Value2);

// perform division first to avoid potential overflow
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. 3 Fraction Calculator (best on Google)[^]
2. Prime Factoring Calculator[^]
3. Fast Prime Factoring Algorithm[^]
4. Fraction Calculator, Mobile version[^]

## Share

 Software Developer (Senior) United States
Dr. Alexander Bell is a seasoned full-stack Software Engineer (Win/Web/Mobile). He holds PhD in Electrical and Computer Engineering, authored 37 inventions and published 300+ technical articles. Currently focused on multiple Android/Mobile development projects and Big Data' Machine Learning, AI, IoT. Alex participated in App Innovation Contests (AIC 2102/2013) with multiple winning submissions. Sample portfolio apps and publications:

 First Prev Next
 My vote of 2 carga16-Dec-13 4:09 carga 16-Dec-13 4:09
 any of two = 0... Andrei Zakharevich1-Nov-13 6:40 Andrei Zakharevich 1-Nov-13 6:40