Rational for C#

Rational is ratio of 2 integers. It represents fractions of an integer. Most of the time if you deal with rational number, you can use real number (float) instead. But real number has an drawback. It cannot maintain proportion of 2 integers for number with repeating decimal. For example,

(1/20)² + (1/15)² - (1/12)²
= (1/400) + (1/225) - (1/144)
= (9/3600) + (16/3600) - (25/3600)
= 0

Now testing with real number:

double x = Math.Pow(1.0 / 20.0, 2.0);
double y = Math.Pow(1.0 / 15.0, 2.0);
double z = Math.Pow(1.0 / 12.0, 2.0);
Console.WriteLine(x + y - z);
//8.67361737988404E-19

Result is not zero as expected. To use rational, you can download from here. Rational class is required BigInteger in SilverLight package. You can construct rational several ways.

Rational a = new Rational(1, 20);
Rational b = (Rational)1 / 15;
Rational c = 1m / 12m;
Console.WriteLine(a.Power(2) + b.Power(2) - c.Power(2));
//0

You can construct rational using new keyword, first argument is numerator, and second argument is denominator. Second method is to cast from integer. Last method is to guess from decimal. Please noted that guessing rational from decimal may lose accuracy, such as:

Rational r = 1000001m / 600001m;
Console.WriteLine(r.ToString());
//5/3

You can see that it keeps 5/3 instead of 1000001/600001. If you need accuracy, construct rational or casting from integer are better solutions.

The Rational class always keep rational in reduced form, such as:

Rational r = (Rational)5 / 10;
Console.WriteLine(r.ToString());
//1/2

It keeps 1/2 instead of 5/10. This will make all same proportions such as 1/2, 3/6, 5/10 are all equivalent.

This Rational class supports infinity, negative zero, and not a number (NaN). This will make all arithmetic operations are equal to real number, such as:

//1/0 makes infinity
Rational inf = (Rational)1 / 0;
Console.WriteLine(inf);
//Infinity

//Invert of negative zero makes negative infinity
Rational nzero = (Rational)0 / -1;
Console.WriteLine(1 / nzero);
//-Infinity

//infinity - infinity = nan
Rational nan = inf - inf;
Console.WriteLine(nan);
//NaN

Let's test rational with an easy question from projecteuler.net.
Find numerator of the fraction immediately to left of 3/7 with denominator <= 1000000

Rational r = (Rational)3 / 7;
r -= (Rational)1 / 999999;
Console.WriteLine(r.Numerator);
//428570

Next topic is to create continued fractions from square root and generate sequence of rational.

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.

Infinite Sequence Part III - Fibonacci

Last post, I had described about how to create based class for infinite sequence, and create a simple generic sequence. This post, we will move on to Fibonacci sequence.

Each Fibonacci number is the sum of 2 preceding number. First and second Fibonacci numbers are 0 and 1. Third Fibonacci number is the sum of First and Second (0+1) equal to 1. And forth Fibonacci number is the sum of Second and Third number (1+1) equal to 2. First 20 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181.

Now let's start coding Fibonacci.

public class Fibonacci : BaseSequence<BigInteger> {
    protected override IEnumerable<BigInteger> Enumerate() {
        BigInteger value = BigInteger.Zero;
        BigInteger value2 = BigInteger.One;

        yield return value;
        yield return value2;
        while (true) {
            value += value2;
            yield return value;
            value2 += value;
            yield return value2;
        }
    }
}

Just few lines of code, Fibonacci sequence is finished! Value and value2 return value alternately. Value variable return value in odd position. And value2 return value in even position.

Test Fibonacci sequence with projecteuler.net questions.
Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x < 1000000).Where(x => x % 2 == 0).Sum()
);
//1089154

What is the first term in the Fibonacci sequence to contain 1000 digits?

Console.WriteLine(
    new Fibonacci().TakeWhile(x => x.ToString(10).Length < 1000).Count()
);
//4782

Next post, we will go to much harder sequence, which is Prime sequence.

BigInteger, an integer with unbounded length

Usaully, when you think of number, Int32 almost covers all requirements. Its maximum value is 2,147,483,647. It almost never overflow. Int32 is not enough? That's very rare case. But you can using Int64 which its maximum value is 9,223,372,036,854,775,807 which considers an extreamly large number. Is it possible that an operation will make Int64 be overflown? It is possible. In mathematics and cryptography, large precision calculation is needed, and data length of an integer can be extended indefinitely.

Which type shall we use next to Int64? If your answer is Int128, the answer is wrong. Next class we gonna use has no length limitation. It is an integer with unbounded length. This type is called BigInteger.

BigInteger is not included in current C# package. But now you can find BigInteger in Silverlight package. Once you install Silverlight, BigInteger can be found in [drive]:\Program Files\Microsoft Silverlight\Microsoft.Scripting.dll under the namespace Microsoft.Scripting.Math.

Let's play around BigInteger (question from projecteuler.net) :)
Find the sum of digits in 100!

BigInteger bigInt = 1;
100.DownTo(2).ForEach(x => bigInt *= x);    //Factorial 100!
Console.WriteLine(bigInt.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//648

More question :)
What is the sum of the digits of the number 2¹⁰⁰⁰?

BigInteger bi = 1;
1000.Times(x => bi *= 2);    //2¹⁰⁰⁰
Console.WriteLine(bi.ToString(10).Sum(c => (int)(c - '0')));    //Sum of Digit
//1366

Factorial of 100 and 2 power by 1000, Int64 is generally unable to handle above questions. But BigInteger can handle it easily and fast.

As a bonus, I had written some Extensions for BigInteger. First method is for getting sum of a list of BigInteger.

public static BigInteger Sum(this IEnumerable<BigInteger> source) {
    BigInteger num = BigInteger.Zero;
    foreach (BigInteger num2 in source)
        num += num2;
    return num;
}
public static BigInteger Sum<T>(this IEnumerable<T> source, Func<T,BigInteger> selector) {
    return source.Select(selector).Sum();
}

Usage:

var list = new BigInteger[] { 1, 2, 3 };
Console.WriteLine(list.Sum());
//6

Next method is for parsing string into BigInteger:

public static BigInteger Parse(string s) {
    using (System.IO.StringReader reader = new System.IO.StringReader(s)) {
        char[] buffer = new char[10];
        int startIndex = 0;
        uint[] multiplier = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

        int count = reader.ReadBlock(buffer, 0, 9);
        BigInteger ret = int.Parse(new string(buffer, 0, count));
        if (ret.IsNegative())
            startIndex = 1;

        while (count == 9) {
            count = reader.ReadBlock(buffer, startIndex, 9);
            ret *= multiplier[count];
            ret += int.Parse(new string(buffer, 0, count + startIndex));
        }
        return ret;
    }
}
public static bool TryParse(string s, out BigInteger result) {
    try {
        result = Parse(s);
        return true;
    } catch {
        result = null;
        return false;
    }
}

Usage

BigInteger i = BigIntegerExtension.Parse("1234567890");
Console.WriteLine(i);
//1234567890

Next post, I will show you somethings bigger than BigInteger :)