Fast Greatest Common Divisor and Least Common Multiple Algorithms
.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].
//============================================================================ // 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