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.

Infinity, Negative Zero, and Not a Number

Mathematics always go beyond its own current dimension. Natural numbers was created, but it does not satisfy existence of zero and negative numbers. Integer was then created, but what happened if we scale integer into smaller numbers. Rational was then create, but it cannot represents number liked root of 2. Real numbers was then created, but some create Complex numbers to satisfy root of -1, and some create Extended real, to satisfy division of zero.

Extended real is very interesting, it doesn't comply with number system as following:

Infinity + 1 = Infinity
1 = Infinity - Infinity
1 = 0 ???

Therefore, infinity is not existed and division by zero is undefined. But extended real try to create its own rules by introducing non-number liked Infinity, Negative Infinity, Negative Zero, and Not a number.

Infinity can be created by 1/0. Some basic properties of infinity are:

1.0 / 0.0 = Inf
1.0 / Inf = 0.0
1.0 + Inf = Inf
Inf - Inf = NaN
Inf * 0.0 = NaN
Inf * -1.0 = -Inf

Infinity in extended real has its own sign. It can be positive or negative. Negative infinity can be created by -1/0. Some basic properties of negative infinity are:

-1.0 / 0.0 = -Inf
1.0 / -Inf = -0.0
1.0 / -0.0 = -Inf
1.0 + -Inf = -Inf
-Inf * -1.0 = Inf

Zero in extended real also has its own sign. It can be negative. Negative zero can be create by -0. Some basic properties of negative zero are:

-(0.0) = -0.0
-0.0 * -1.0 = 0.0
-0.0 * -0.0 = 0.0
-0.0 * 0.0 = -0.0
-0.0 + -0.0 = -0.0
-0.0 + 0.0 = 0.0
-1.0 % 1.0 = -0.0

All undefined numbers are Not a Number (NaN). All arithmatic operation with NaN result to NaN, therefore extended real has no arithmatic error. NaN can be created from:

0.0 / 0.0 = NaN
Inf - Inf = NaN
Inf * 0.0 = NaN
1.0 % 0.0 = NaN
Inf % 1.0 = NaN
Sqrt(-1.0) = NaN

Arithmatic comparisons for extended real are as follows:

Inf > 1.0
1.0 > 0.0
0.0 == -0.0
0.0 > -1.0
-1.0 > -Inf
-Inf > NaN
NaN != NaN

NaN doesn't equal to itself, to check NaN use double.Equals(x, NaN) instead. Extended real is IEEE standard and it is called "floating point". In C#, 2 types for floating point are provided, float and double. Float is single precision, its maximum precision is around 1.4E-45. Double is much precise, its maximum precision is up to around 4.94E-324.

Next post, I will introduce type with unbounded precision.

Dynamic Programming Part III - Partition Function

Partition Function is function to find distinct ways to sum natural numbers to a target number. Such as 4 can be partitioned to 5 distinct ways:

4
3+1
2+2
2+1+1
1+1+1+1

Consider above summation and find overlapping function, we can notice that we can deduct 1 to 4 from target number. If the result is 0, it is the solution. If result is greater than 0, we must do further deduction. And this is the formula of partition function:



Where m is maximum number to deduct, n is the remaining. Whenever n is 0, means it is a solutions. But if n is less than 0, there is no solution for remaining less than 0. We can write above function into following code:

Func<int, int, int> p = null;
p = (m, n) => 1.To(m).Sum(i => p(i, n - i));
p = p.When((m, n) => n == 0, (m, n) => 1);
p = p.When((m, n) => n < 0, (m, n) => 0);
p = p.Memoize();

We can find the partition function of 100 by using following code:

Console.WriteLine(p(100, 100));
//190569292

We can adapt above function to find partition function using a specific set of number. Such as changing £2 to any number of coins (1p, 2p, 5p, 10p, 20p, 50p, 1£, and 2£). Following is the formula.



Where s(i) is the value of a specific item in the set. And now m is the upper bound of the set. We can solve number of solutions of changing for £2 with following code:

int[] s = null;
Func<int, int, int> p = null;
p = (m, n) => 0.To(m).Sum(i => p(i, n - s[i]));
p = p.When((m, n) => n == 0, (m, n) => 1);
p = p.When((m, n) => n < 0, (m, n) => 0);
p = p.Memoize();

s = new[] { 1, 2, 5, 10, 20, 50, 100, 200 };
Console.WriteLine(p(s.Length - 1, 200));
//73682

Next, we can also find the first target number, partitioned by prime numbers, and has over 5000 solutions.

s = new Prime().TakeWhile(x => x <= 100).Cast<int>().ToArray();
Console.WriteLine(1.To(100).First(i => p(s.Length - 1, i) >= 5000));
//71

This post is the end of dynamic programming series. The challenging part of dynamic programming is to find overlapping substructure. Once you find the substructure, your computation of the functions will be extremely fast. Next post is about number which is real number.