Extension Methods for Math

Math class provided by core library of .NET is very good. But most methods are for double type. Today we will create math methods for integer types which include int, long, and BigInteger.

Start with GCD (Greatest Common Divisor), which I used once in Pythagorean article.

public static int Gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
public static long Gcd(long a, long b) {
    while (b != 0L) {
        long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

And next one goes to LCM (Least Common Multiple).

public static int Lcm(int a, int b) {
    return (b / Gcd(a, b)) * a;
}
public static long Lcm(long a, long b) {
    return (b / Gcd(a, b)) * a;
}

Usage of these methods are easy, to find GCD and LCM of number 1 to 20.

Console.WriteLine(1.To(20).Aggregate(Math2.Gcd));
//1
Console.WriteLine(1.To(20).Aggregate(Math2.Lcm));
//232792560

Next is Integer Square Root. This method uses Newton's method to solve square root.

public static int Sqrt(this int num) {
    if (num < 0)
        throw new ArgumentOutOfRangeException("num", "num cannot be negative");

    int x = num;
    int y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / 2;
    }
    return x;
}
public static long Sqrt(this long num) {
    if (num < 0L)
        throw new ArgumentOutOfRangeException("num", "num cannot be negative");

    long x = num;
    long y = (x + 1L) / 2L;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / 2L;
    }
    return x;
}

Usage is simple, to find square root of 2,000,000,000,000,000,000

Console.WriteLine(2000000000000000000.Sqrt());
//1414213562

Next is to find the Exponentiation

public static int Power(this int num, int pow) {
    if (pow < 0)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    int result = 1;
    while (pow != 0) {
        if ((pow & 1) == 1) {
            result *= num;
            if (pow == 1)
                return result;
        }
        num *= num;
        pow >>= 1;
    }
    return result;
}
public static long Power(this long num, long pow) {
    if (pow < 0L)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    long result = 1L;
    while (pow != 0L) {
        if ((pow & 1L) == 1L) {
            result *= num;
            if (pow == 1L)
                return result;
        }
        num *= num;
        pow >>= 1;
    }
    return result;
}

Usage is as simple as square root, to find 2nd power of 1,414,213,562.

Console.WriteLine(1414213562L.Power(2));
//1999999998944727844

When you use integer square root and power to a number, if result is not the same as that number, the number is not perfect square. In the example above, 2,000,000,000,000,000,000 is not perfect square.

Last one, Modular Exponentiation, is to perform power over a modulus.

public static int ModPow(this int num, int pow, int mod) {
    if (pow < 0)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    int result = 1;
    while (pow != 0) {
        if ((pow & 1) == 1) {
            result = (result * num) % mod;
            if (pow == 1L)
                return result;
        }
        num = (num * num) % mod;
        pow >>= 1;
    }
    return result;
}
public static long ModPow(this long num, long pow, long mod) {
    if (pow < 0L)
        throw new ArgumentOutOfRangeException("pow", "pow cannot be negative");

    long result = 1L;
    while (pow != 0L) {
        if ((pow & 1L) == 1L) {
            result = (result * num) % mod;
            if (pow == 1L)
                return result;
        }
        num = (num * num) % mod;
        pow >>= 1;
    }
    return result;
}

Example of modular exponentiation, to find last 5 digits of 10th power of 1,414,213,562.

Console.WriteLine(1414213562L.ModPow(10L, 100000L));
//60224

And below is the code for BigInteger

public static BigInteger Gcd(BigInteger a, BigInteger b) {
    while (!b.IsZero()) {
        BigInteger r = a % b;
        a = b;
        b = r;
    }
    return a;
}
public static BigInteger Lcm(BigInteger a, BigInteger b) {
    return (b / Gcd(a, b)) * a;
}
static readonly BigInteger two = 2;
public static BigInteger Sqrt(this BigInteger num) {
    if (num.IsNegative())
        throw new ArgumentException("num cannot be negative", "num");
    if (num.IsZero())
        return BigInteger.Zero;

    BigInteger x = num;
    BigInteger y = (x + BigInteger.One) / two;
    while (y < x) {
        x = y;
        y = (x + (num / x)) / two;
    }
    return x;
}

There is not Power and ModPow for BigInteger, because BigInteger already contains those methods.

Next article, is to find the ways to inject index into various enumerable methods.