posts - 19 , comments - 8 , trackbacks - 0

Evaluating the Greatest Common Divisor function in C#

Available Routines

There are a number of basic routines. Two that are attributable to Euclid are the subtraction and modulus method. There is another routine be Stein which uses binary arithmatic. Lastly there is the "trial and error" version which is useful as a check on validity.

The algorithms

The algorithms are provided in the code below.

using System;

namespace JetBlack.Common
{
    public static class GreatestCommonDivisor
    {
        public enum Algorithm
        {
            TrialAndError,
            EuclidModulus,
            EuclidModulusShort,
            EuclidSubtract,
            EuclidSubtract2,
            EuclidRecursive,
            SteinRecursive,
            SteinIterative
        }

        public static int Gcd(int a, int b, Algorithm algorithm)
        {
            bool aneg = a < 0, bneg = b < 0;
            if (aneg) a = -a;
            if (bneg) b = -b;

            var gcd = Gcd((uint) a, (uint) b, algorithm);
            return aneg == bneg ? (int) gcd : -((int) gcd);
        }

        public static uint Gcd(uint a, uint b, Algorithm algorithm)
        {
            switch (algorithm)
            {
                case Algorithm.TrialAndError:
                    return TrialAndError.Gcd(a, b);
                case Algorithm.EuclidModulus:
                    return EuclidModulus.Gcd(a, b);
                case Algorithm.EuclidModulusShort:
                    return EuclidModulusShort.Gcd(a, b);
                case Algorithm.EuclidSubtract:
                    return EuclidSubtract.Gcd(a, b);
                case Algorithm.EuclidSubtract2:
                    return EuclidSubtract2.Gcd(a, b);
                case Algorithm.EuclidRecursive:
                    return EuclidRecursive.Gcd(a, b);
                case Algorithm.SteinRecursive:
                    return SteinRecursive.Gcd(a, b);
                case Algorithm.SteinIterative:
                    return SteinIterative.Gcd(a, b);
                default:
                    throw new ArgumentOutOfRangeException("algorithm");
            }
        }

        internal static class EuclidModulus
        {
            public static uint Gcd(uint a, uint b)
            {
                while (a != 0 && b != 0)
                {
                    if (a > b)
                        a %= b;
                    else
                        b %= a;
                }

                return a == 0 ? b : a;
            }
        }

        internal static class EuclidModulusShort
        {
            public static uint Gcd(uint a, uint b)
            {
                while (b != 0)
                {
                    var r = a % b;
                    a = b;
                    b = r;
                }
                return a;
            }
        }

        internal static class EuclidRecursive
        {
            public static uint Gcd(uint a, uint b)
            {
                return b == 0 ? a : Gcd(b, a % b);
            }
        }

        internal static class TrialAndError
        {
            public static uint Gcd(uint a, uint b)
            {
                uint n = a <= b ? a : b;
                uint gcd = 1, i = 1;

                while (i <= n)
                {
                    if (a % i == 0 && b % i == 0)
                        gcd = i;
                    ++i;
                }
                return gcd;
            }
        }

        internal static class EuclidSubtract
        {
            public static uint Gcd(uint a, uint b)
            {
                while (a != 0 && b != 0)
                {
                    if (a > b)
                        a -= b;
                    else
                        b -= a;
                }

                return a == 0 ? b : a;
            }
        }

        internal static class EuclidSubtract2
        {
            public static uint Gcd(uint a, uint b)
            {
                while (a != b)
                {
                    while (a > b)
                    {
                        var c = a - b;
                        a = c;
                    }
                    while (b > a)
                    {
                        var c = b - a;
                        b = c;
                    }
                }
                return a;
            }
        }

        internal static class SteinRecursive
        {
            public static uint Gcd(uint a, uint b)
            {
                if (a == 0) return b;
                if (b == 0) return a;
                if (a == b) return a;


                if ((a & 1u) == 0)
                {
                    return
                        (b & 1u) == 0
                            ? Gcd(a >> 1, b >> 1) << 1
                            : Gcd(a >> 1, b);
                }

                if ((b & 1u) == 0)
                    return Gcd(a, b >> 1);

                return
                    a > b
                        ? Gcd((a - b) >> 1, b)
                        : Gcd(a, (b - a) >> 1);
            }
        }

        internal static class SteinIterative
        {
            public static uint Gcd(uint a, uint b)
            {
                int shift;

                if (a == 0) return b;
                if (b == 0) return a;

                for (shift = 0; ((a | b) & 1) == 0; ++shift)
                {
                    a >>= 1;
                    b >>= 1;
                }

                while ((a & 1) == 0)
                    a >>= 1;

                do
                {
                    while ((b & 1) == 0) /* Loop X */
                        b >>= 1;

                    if (a > b)
                    {
                        var t = b;
                        b = a;
                        a = t;
                    }
                    b = b - a;
                } while (b != 0);

                return a << shift;
            }
        }
    }
}

The test

The following code tests each algorithm to ensure that they produce the same result. A second routine evaluates the speed.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using NUnit.Framework;

namespace JetBlack.Common.Test
{
    [TestFixture]
    public class GreatestCommonDivisorFixture
    {
        [Test]
        public void TestEuclidModulus()
        {
            var gcd = GreatestCommonDivisor.Gcd(1, 1, GreatestCommonDivisor.Algorithm.EuclidModulus);
            Assert.AreEqual(1, gcd);
        }

        [Test]
        public void TestEquivalence()
        {
            for (var a = 1; a < 1000; ++a)
            {
                for (var b = 1; b < 1000; ++b)
                {
                    var results1 = new Dictionary<GreatestCommonDivisor.Algorithm, int>();
                    var results2 = new Dictionary<GreatestCommonDivisor.Algorithm, int>();
                    foreach (var algorithm in Enum.GetValues(typeof (GreatestCommonDivisor.Algorithm)).Cast<GreatestCommonDivisor.Algorithm>())
                    {
                        results1.Add(algorithm, GreatestCommonDivisor.Gcd(a, b, algorithm));
                        results2.Add(algorithm, GreatestCommonDivisor.Gcd(b, a, algorithm));
                    }

                    var isFirst = true;
                    var gcd = 0;
                    foreach (var result in results1)
                    {
                        if (!isFirst)
                            Assert.AreEqual(gcd, result.Value, string.Format("a = {0}, b = {1}, algorithm={2}", a, b, result.Key));
                        else
                        {
                            isFirst = false;
                            gcd = result.Value;
                        }
                    }
                }
            }
        }

        [Test]
        public void TestSpeed()
        {
            var stopWatch = new Stopwatch();
            var results = new Dictionary<GreatestCommonDivisor.Algorithm, long>();
            foreach (var algorithm in Enum.GetValues(typeof (GreatestCommonDivisor.Algorithm)).Cast<GreatestCommonDivisor.Algorithm>())
            {
                stopWatch.Restart();
                for (var a = 1; a < 1000; ++a)
                {
                    for (var b = 1; b < 1000; ++b)
                    {
                        GreatestCommonDivisor.Gcd(a, b, algorithm);
                        GreatestCommonDivisor.Gcd(b, a, algorithm);
                    }
                }
                results.Add(algorithm, stopWatch.ElapsedMilliseconds);
            }

            foreach (var result in results.OrderBy(x => x.Value))
                Debug.Print("Algorithm: {0}, time={1}ms", result.Key, result.Value);
        }
    }
}

The results

This is what I found

  1. Algorithm: EuclidModulus, time=207ms
  2. Algorithm: EuclidModulusShort, time=217ms
  3. Algorithm: EuclidRecursive, time=322ms
  4. Algorithm: SteinIterative, time=339ms
  5. Algorithm: EuclidSubtract2, time=417ms
  6. Algorithm: EuclidSubtract, time=442ms
  7. Algorithm: SteinRecursive, time=784ms
  8. Algorithm: TrialAndError, time=2614ms

The winner is Eculid Modulus!

Print | posted on Friday, November 14, 2014 10:56 AM | Filed Under [ C# GCD greatest common divisor ]

Feedback

No comments posted yet.
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by: