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.

Extension Methods for Delegate Types Part II - Passing anonymous type to generic function

How can you create function which its parameter or return type is anonymous type? You can't assign lambda expression to implicit local variable declaration.

//Compile error
var func = () => new { x = 1, y = 2 };

The c# compiler also does not accept type inference on instantiation, such as

//Compile error
var func = new Func(() => new { x = 1, y = 2 });

To create generic function, which accepts anonymous type, we must create method. Because for method, type inference is allowed.

Here is the code.

public static Func<TResult> CreateFunction<TResult>(Func<TResult> tResult) {
    return tResult;
}
public static Func<T, TResult> CreateFunction<T, TResult>(T t, Func<T, TResult> tResult) {
    return tResult;
}
public static Func<T1, T2, TResult> CreateFunction<T1, T2, TResult>(T1 t1, T2 t2, Func<T1, T2, TResult> tResult) {
    return tResult;
}
public static Func<T1, T2, T3, TResult> CreateFunction<T1, T2, T3, TResult>(T1 t1, T2 t2, T3 t3, Func<T1, T2, T3, TResult> tResult) {
    return tResult;
}
public static Func<T1, T2, T3, T4, TResult> CreateFunction<T1, T2, T3, T4, TResult>(T1 t1, T2 t2, T3 t3, T4 t4, Func<T1, T2, T3, T4, TResult> tResult) {
    return tResult;
}

To create the method just pass lambda expression to the argument.

var func = Function2.CreateFunction(() => new { x = 1, y = 2 });

You can also create function which its arguments and return type are anonymous type

var func = Function2.CreateFunction(
    new { Name = default(string), Age = default(int) },
    default(decimal),
    (person, salary) =>
        new {
            Name = person.Name,
            Age = person.Age,
            Salary = salary
        });
var p = func(new { Name = "Lisa", Age = 20 }, 1000000);
//p = { Name = Lisa, Age = 20, Salary = 1000000 }

Just pass the empty class to specify type of arguments. Above code is to create function which accept an anonymous type (Name: string, Age: int) and a decimal, the function returns another anonymous type (Name: string, Age: int, Salary: decimal).

As a bonus here are some more extension methods.

public static Func<T2, T3, TResult> Partial<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func, T1 arg1) {
    return (arg2, arg3) => func(arg1, arg2, arg3);
}
public static Func<T2, T3, T4, TResult> Partial<T1, T2, T3, T4, TResult>(this Func<T1, T2, T3, T4, TResult> func, T1 arg1) {
    return (arg2, arg3, arg4) => func(arg1, arg2, arg3, arg4);
}

public static Func<T1, T2, T3, TResult> Memoize<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func) {
    var dict = new Dictionary<T1, Func<T2, T3, TResult>>();
    return (arg1, arg2, arg3) => {
        Func<T2, T3, TResult> value;
        if (!dict.TryGetValue(arg1, out value)) {
            value = func.Partial(arg1).Memoize();
            dict.Add(arg1, value);
        }
        return value(arg2, arg3);
    };
}
public static Func<T1, T2, T3, T4, TResult> Memoize<T1, T2, T3, T4, TResult>(this Func<T1, T2, T3, T4, TResult> func) {
    var dict = new Dictionary<T1, Func<T2, T3, T4, TResult>>();
    return (arg1, arg2, arg3, arg4) => {
        Func<T2, T3, T4, TResult> value;
        if (!dict.TryGetValue(arg1, out value)) {
            value = func.Partial(arg1).Memoize();
            dict.Add(arg1, value);
        }
        return value(arg2, arg3, arg4);
    };
}

public static Func<T1, T2, T3, TResult> When<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func, Func<T1, T2, T3, bool> predicate, Func<T1, T2, T3, TResult> alternative) {
    return (arg1, arg2, arg3) => predicate(arg1, arg2, arg3) ? alternative(arg1, arg2, arg3) : func(arg1, arg2, arg3);
}
public static Func<T1, T2, T3, T4, TResult> When<T1, T2, T3, T4, TResult>(this Func<T1, T2, T3, T4, TResult> func, Func<T1, T2, T3, T4, bool> predicate, Func<T1, T2, T3, T4, TResult> alternative) {
    return (arg1, arg2, arg3, arg4) => predicate(arg1, arg2, arg3, arg4) ? alternative(arg1, arg2, arg3, arg4) : func(arg1, arg2, arg3, arg4);
}

These are Parial, Memoize, and When functions, which are the same as previous post. You can find detail of functions in previous post. The only difference of these functions and functions in previous post is, these functions accept 3 and 4 arguments.

Next post, extension methods for math.