Extended Euclidean algorithm

        static void Main(string[] args)
        {
            //Solving ax + by = gcd(a, b);
            int[] result = SolveByIterativeExtendedEuclideanAlgorithm(21, 9);
            Console.WriteLine("Iterative result: x:{0}, y:{1}", result[0], result[1]);
            result = SolveByRecursiveExtendedEuclideanAlgorithm(21, 9);
            Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
            result = SolveByIterativeExtendedEuclideanAlgorithm2(21, 9);
            Console.WriteLine("Recursive result: x:{0}, y:{1}", result[0], result[1]);
            Console.ReadKey();
        }
 
        /// <summary>
        /// Extended Euclidean algorithm
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
        /// <returns></returns>
        private static int[] SolveByIterativeExtendedEuclideanAlgorithm(int a, int b)
        {
            //Initialize x0, x1 as 1, 0, and y0, y1 as 0,1 respectively.
            int lastX = 1, x = 0;
            int lastY = 0, y = 1;
            int temp = 0;
            int quotient = 0;
            while(b != 0)
            {
                temp = b;
                quotient = a / b;
                b = a % b;
                a = temp;
                //Compute xi+1= xi-1- qixi
                temp = x;
                x = lastX – quotient * x;
                lastX = temp;
                //Compute yi+1= yi-1- qiyi
                temp = y;
                y = lastY – quotient * y;
                lastY = temp;
            }
            //The answers are the second-to-last of xn and yn.
            return new int[] { lastX, lastY };
        }
 
        /// <summary>
        /// Extended Euclidean algorithm
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <seealso cref="http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"/>
        /// <returns></returns>
        private static int[] SolveByRecursiveExtendedEuclideanAlgorithm(int a, int b)
        {
            // If a is divisible by b, the algorithm ends and return the trivial solution x = 0, y = 1.
            if ((a % b) == 0)
                return new int[] { 0, 1 };
            //Otherwise, repeat the algorithm with b and a modulus b, storing the solution as x’ and y’.
            int[] result = SolveByRecursiveExtendedEuclideanAlgorithm(b, a % b);
            //Then, the solution to the current equation is x = y’, and y = x’ minus y’ times quotient of a divided by b
            return new int[] {result[1], result[0] – a / b * result[1] };
        }
 
        private static int[] SolveByIterativeExtendedEuclideanAlgorithm2(int a, int b)
        {
            int m = a;
            int n = b;
            int p = 1;
            int q = 0;
            int r = 0;           
            int s = 1;
            while (! ((m == 0) || (n == 0)) )
            {
                if (m >= n)
                {
                    m = m – n;
                    p = p – r;
                    q = q – s;
                }
                else
                {
                    n = n – m;
                    r = r – p;
                    s = s – q;
                }
            }
            if (m == 0)
            {
                return new int[] { r, s};
            }
            else
            {
                return new int[] { p, q};
            }
        }
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s