15,559,122 members
Articles / High Performance Computing / Parallel Processing
Tip/Trick
Posted 24 Feb 2011

49.3K views
14 bookmarked

# Fast Greatest Common Divisor and Least Common Multiple Algorithms

Rate me:
4.71/5 (10 votes)
19 Apr 2011CPOL
.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. Another Prime Factoring and corresponding Primality test algorithm has been described in the previous post on CodeProject [1].

C#
```//============================================================================
// Author           :   Alexander Bell
// Copyright        :   2007-2011 Infosoft International Inc
// Date Created     :   01/15/2007
// Last Modified    :   01/11/2011
// 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
//****************************************************************************

//****************************************************************************
// TERMS OF USE     :   This module is copyrighted.
//                  :   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

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By
Engineer
United States
Dr. Alexander Bell (aka DrABell) is a seasoned full-stack Software (Win/Web/Mobile) and Data Engineer. He holds PhD in Electrical and Computer Engineering, authored 37 inventions and published 100+ technical articles; currently focused on Microsoft Azure Cloud and Android Mobile development projects. Alex participated in App Innovation Contests (AIC 2102/2013) w/multiple winning submissions. Sample apps/publications:

## Comments and Discussions

 First Prev Next
 My vote of 2 carga16-Dec-13 5:09 carga 16-Dec-13 5:09
 any of two = 0... Andrei Zakharevich1-Nov-13 7:40 Andrei Zakharevich 1-Nov-13 7:40
 My vote of 5 JBoada7-Aug-13 9:59 JBoada 7-Aug-13 9:59
 Re: My vote of 5 DrABELL7-Aug-13 11:09 DrABELL 7-Aug-13 11:09
 Thanks, Hayk! Best rgds, Alex DrABELL3-Mar-11 4:35 DrABELL 3-Mar-11 4:35
 Reason for my vote of 2 This is the known algorithm of Eucli... Hayk Aleksanyan28-Feb-11 19:25 Hayk Aleksanyan 28-Feb-11 19:25
 Re: Hayk, The solution clearly states that it is using a Euclid ... DrABELL1-Mar-11 3:05 DrABELL 1-Mar-11 3:05
 Re: Hayk, I would appreciate if you could re-consider your vote ... DrABELL2-Mar-11 4:45 DrABELL 2-Mar-11 4:45
 may want to fix your formatting though :) jfriedman25-Feb-11 9:41 jfriedman 25-Feb-11 9:41
 Reason for my vote of 3 Cleaner than last time... jfriedman25-Feb-11 3:32 jfriedman 25-Feb-11 3:32
 Re: You should seriously re-consider your voting practice DrABELL8-Mar-11 2:06 DrABELL 8-Mar-11 2:06
 Last Visit: 31-Dec-99 19:00     Last Update: 28-Jan-23 3:17 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.