Getting GCD (based on division by 2 algorithm)

        /// <summary>
        /// Getting greatest common divisor by using next his properties:
        /// GCD(2a, 2b) = 2 x GCD(a,b) and GCD(2a, b) = GCD(a, b), if b is odd digit.
        /// </summary>
        private static int GetGCD(int a, int b)
        {
            int m = a;
            int n = b;
            int d = 1;
            while( ! ((m == 0) || (n ==0)) )
            {
                if ( (m % 2 == 0) && (n % 2 == 0) )
                {
                    m/=  2;
                    n/= 2;
                    d *= 2;
                }
                else if (m % 2 == 0)
                {
                    m/= 2;
                }
                else if (n % 2 == 0)
                {
                    n/= 2;
                }
                else
                {
                    if (m >= n)
                        m = m – n;
                    else
                        n = n – m;
                }
            }
            if (m != 0)
                return m * d;
            else return n * d;
        }

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