C# - XMath

By , 9/17/2012
(1 ratings)
Greatest Common Devisor,
Least Common Multiple,
Extended Euclidean Algorithm,
Simple Modulo,
Pow,
Modulo Pow
namespace XMath
{
    public struct EEAResultL { public long Rest, AFactor, BFactor; }
    public struct EEAResultI { public int Rest, AFactor, BFactor; }

    public static class Utils
    {
        public static long GCD(long a, long b)
        {
            while (b != 0)
                b = a % (a = b);
            return a;
        }

        public static int GCD(int a, int b)
        {
            while (b != 0)
                b = a % (a = b);
            return a;
        }

        public static long LCM(long a, long b)
        {
            return (a * b) / GCD(a, b);
        }

        public static int LCM(int a, int b)
        {
            return (a * b) / GCD(a, b);
        }

        public static EEAResultL EGCD(long a, long b)
        {
            long d = 0, e = 1, lastd = 1, laste = 0, q;
            while (b != 0)
            {
                q = a / b; //q = floor(a / b)
                b = a - q * (a = b); //gcd(a, b) = gcd(b, a % b)
                d = lastd - q * (lastd = d); //d[i] = d[i-2] - q * d[i-1]
                e = laste - q * (laste = e); //e[i] = e[i-2] - q * e[i-1]
            }
            return new EEAResultL { Rest = a, AFactor = lastd, BFactor = laste };
        }

        public static EEAResultI EGCD(int a, int b)
        {
            int d = 0, e = 1, lastd = 1, laste = 0, q;
            while (b != 0)
            {
                q = a / b; //q = floor(a / b)
                b = a - q * (a = b); //gcd(a, b) = gcd(b, a % b)
                d = lastd - q * (lastd = d); //d[i] = d[i-2] - q * d[i-1]
                e = laste - q * (laste = e); //e[i] = e[i-2] - q * e[i-1]
            }
            return new EEAResultI { Rest = a, AFactor = lastd, BFactor = laste };
        }

        public static long SimpleMod(this long a, long mod)
        {
            if (a >= mod)
                return a - mod;
            if (a < 0)
                return a + mod;
            return a;
        }

        public static int SimpleMod(this int a, int mod)
        {
            if (a >= mod)
                return a - mod;
            if (a < 0)
                return a + mod;
            return a;
        }

        public static double Pow(this double a, uint b)
        {
            double result = 1;
            for (sbyte i = 0x20 - 1; i >= 0; i--)
            {
                if (result != 1)
                    result *= result;
                if ((b & ((uint)1 << i)) != 0)
                    result *= a;
            }
            return result;
        }

        public static int Pow(this int a, uint b)
        {
            int result = 1;
            for (sbyte i = 0x20 - 1; i >= 0; i--)
            {
                if(result != 1)
                    result *= result;
                if ((b & ((uint)1 << i)) != 0)
                    result *= a;
            }
            return result;
        }

        public static uint ModPow(this uint a, uint b, uint mod)
        {
            uint result = 1;
            for (sbyte i = 0x20 - 1; i >= 0; i--)
            {
                if (result != 1)
                {
                    result *= result;
                    result %= mod;
                }
                if ((b & ((uint)1 << i)) != 0)
                {
                    result *= a;
                    result %= mod;
                }
            }
            return result;
        }
    }
}

Comments

 

Log in, to comment!