Click here to Skip to main content
12,394,788 members (63,132 online)
Click here to Skip to main content
Add your own
alternative version

Stats

29.5K views
13 bookmarked
Posted

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

, 19 Apr 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
.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].
//============================================================================
// 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.

Mobile Fraction Calculator on iPad 2
Mobile
References
1. 3 Fraction Calculator (best on Google)[^]
2. Prime Factoring Calculator[^]
3. Fast Prime Factoring Algorithm[^]
4. Fraction Calculator, Mobile version[^]

License

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

Share

About the Author

DrABELL
President Infosoft International Inc
United States United States
Dr. A. Bell is a full-stack software developer (Win/Web/Mobile). He holds PhD in EE/IT, published 300+ articles, authored 37 inventions and is credited for 10+ Enterprise level projects; currently focused on HTML5/CSS3, Javascript/jQuery, .NET/WPF/C#, Android/Angular.js, 'Big Data', AI, IoT. Alex participated in App Innovation Contests (AIC 2102/2013) with multiple winning submissions. Sample projects/pubs:
  1. Real-time NY Bus monitoring app (IoT)
  2. Semaphon™ semantic phone num-to-text converter
  3. Educational Web Portal
  4. Free Online NY Payroll Tax Calculator
  5. WebTV powered by Embedded YouTube Player (Goog #1 YouTube API for ASP.NET)
  6. Top-50 Digital Cameras (powered by iMark-DCAM rating engine)
  7. Pure CSS3 Slide Show
  8. Inflation Calculator
  9. CSS3 Modal Pop-up Dialog
  10. Multilingual Geocoder with Interactive Map
  11. Online Semantic Analyzer (Concordance Calculator)
  12. NY City Job Market and Agency Ratings
  13. Advanced CSS3 Table Formatting

You may also be interested in...

Comments and Discussions

 
GeneralMy vote of 2 Pin
carga16-Dec-13 4:09
membercarga16-Dec-13 4:09 
Questionany of two = 0... Pin
Andrei Zakharevich1-Nov-13 6:40
memberAndrei Zakharevich1-Nov-13 6:40 
GeneralMy vote of 5 Pin
JBoada7-Aug-13 8:59
memberJBoada7-Aug-13 8:59 
GeneralRe: My vote of 5 Pin
DrABELL7-Aug-13 10:09
professionalDrABELL7-Aug-13 10:09 
GeneralThanks, Hayk! Best rgds, Alex Pin
DrABELL3-Mar-11 3:35
memberDrABELL3-Mar-11 3:35 
GeneralReason for my vote of 2 This is the known algorithm of Eucli... Pin
Hayk Aleksanyan28-Feb-11 18:25
memberHayk Aleksanyan28-Feb-11 18:25 
GeneralRe: Hayk, The solution clearly states that it is using a Euclid ... Pin
DrABELL1-Mar-11 2:05
memberDrABELL1-Mar-11 2:05 
GeneralRe: Hayk, I would appreciate if you could re-consider your vote ... Pin
DrABELL2-Mar-11 3:45
memberDrABELL2-Mar-11 3:45 
Generalmay want to fix your formatting though :) Pin
jfriedman25-Feb-11 8:41
memberjfriedman25-Feb-11 8:41 
GeneralReason for my vote of 3 Cleaner than last time... Pin
jfriedman25-Feb-11 2:32
memberjfriedman25-Feb-11 2:32 
GeneralRe: You should seriously re-consider your voting practice Pin
DrABELL8-Mar-11 1:06
memberDrABELL8-Mar-11 1:06 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160721.1 | Last Updated 19 Apr 2011
Article Copyright 2011 by DrABELL
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid