Introduction
This article presents a structure for representing Rational numbers in C# 4.0. Before the current version of the .NET Framework, making a reasonably useful representation of Rational numbers would have been a significant piece of work. The addition of the BigInteger made it possible to construct a Rational number of effectively infinite precision, which is a potentially very useful thing. It has been packaged along with the unit tests used in its production, and code coverage is 100%. The code compiles to both a standard .NET assembly and a Silverlight assembly. Making a useful Rational number class, while no longer what it was, still requires a fair amount of diligence to make it fit properly into the framework. It is not particularly complicated, so I have written this article as if it was for beginners, but hopefully it will still be a pleasant diversion for the more experienced. Also, if you intend to make any value or numeric types, this should serve as a useful catalog of all the elements you need to add.
Roadmap
This is the first article in a series on computing with Rational numbers. The other articles in the series are:
- Rational Numbers -.NET 4.0 version (this article)
- MaNet: A matrix library for .NET
- Rational Matrices (with relative performance analysis) ... coming next
- Rational Derivatives ... coming soon
- Rational Transcendentals ... coming soon
As can be seen, there is a lot of work to do, enough to dominate my free time for quite a while. If anyone is inspired, I would be delighted to work with them on the advancement of rational computing on the .NET platform.
Why should one care about Rational numbers
The .NET Framework already has quite a number of numeric types (sbyte, byte, char, short, ushort, int, uint, long, ulong, float, double, decimal, BigInteger, Complex) so why should one be excited by a Rational numeric type? Consider the following example. I have a function f(x) = 4x4 - 3x3 + 12x2 + 3x + 1 and I want to evaluate its derivative at x = 10. Now for a function this simple, there is no need to use the computer. A small amount of calculation will yield 15343. Let's assume that we really need the numerical approximation. The definition of the derivative of a function f is the limit as h --> 0 of (f(x + h) - f(x))/h. The following is what we get when this is tried for a number of values of h.
| h |
Derivative at x=10 |
Error |
| 1.0E-001 |
15576.7740000000 |
-2.3E+002 |
| 1.0E-002 |
15366.2357039997 |
-2.3E+001 |
| 1.0E-003 |
15345.3221569944 |
-2.3E+000 |
| 1.0E-004 |
15343.2322015578 |
-2.3E-001 |
| 1.0E-005 |
15343.0232196115 |
-2.3E-002 |
| 1.0E-006 |
15343.0023128749 |
-2.3E-003 |
| 1.0E-007 |
15343.0001228116 |
-1.2E-004 |
| 1.0E-008 |
15343.0002683308 |
-2.7E-004 |
| 1.0E-009 |
15342.9937199689 |
+6.3E-003 |
| 1.0E-010 |
15342.9573401809 |
+4.3E-002 |
| 1.0E-011 |
15341.3566295057 |
+1.6E+000 |
| 1.0E-012 |
15337.7186506987 |
+5.3E+000 |
| 1.0E-013 |
15279.5109897852 |
+6.3E+001 |
| 1.0E-014 |
16007.1067512035 |
-6.6E+002 |
| 1.0E-015 |
29103.8304567337 |
-1.4E+004 |
| 1.0E-016 |
0.0000000000 |
+1.5E+004 |
It starts off behaving as we would hope. As h gets smaller, the approximation gets better and better. However, once we reach h equals 10-8, we see the error increasing as we make h smaller. If that was not disconcerting enough, when h goes to 10-16 and below, the approximation is always 0. It might be tempting to ascribe the problem to the function or the point chosen, but they are in no way exceptional. We could try a better method of approximating the derivative, and there definitely are better methods such as higher order approximations for the derivative and Richardson extrapolation. Unfortunately, these follow the same pattern: errors decrease for a while, then increase, and finally the whole process fails. There is a fundamental problem with working with double values and no amount of cleverness can make it completely go away. Before we let ourselves get too discouraged, we could do the same evaluation with the Rational struct included in this article.
| h |
Derivative at x=10 |
Error |
| 1/10 |
7788387/500 |
-116887/500 |
| 1/100 |
1920779463/125000 |
-2904463/125000 |
| 1/1000 |
3836330539251/250000000 |
-580539251/250000000 |
To be honest, looking at the results in their native format is not very illuminating, so let's look at the results converted back to doubles.
| h |
Derivative at x=10 |
Error |
| 1.0E-001 |
15576.7740000000 |
-2.3E+002 |
| 1.0E-002 |
15366.2357040000 |
-2.3E+001 |
| 1.0E-003 |
15345.3221570040 |
-2.3E+000 |
| 1.0E-004 |
15343.2322015700 |
-2.3E-001 |
| 1.0E-005 |
15343.0232200157 |
-2.3E-002 |
| 1.0E-006 |
15343.0023220002 |
-2.3E-003 |
| 1.0E-007 |
15343.0002322000 |
-2.3E-004 |
| 1.0E-008 |
15343.0000232200 |
-2.3E-005 |
| 1.0E-009 |
15343.0000023220 |
-2.3E-006 |
| 1.0E-010 |
15343.0000002322 |
-2.3E-007 |
| 1.0E-011 |
15343.0000000232 |
-2.3E-008 |
| 1.0E-012 |
15343.0000000023 |
-2.3E-009 |
| 1.0E-013 |
15343.0000000002 |
-2.3E-010 |
And we can keep going for a long, long time.
| h |
Derivative at x=10 |
Error |
| 1.0E-203 |
15343.0000000000 |
-2.3E-200 |
| 1.0E-204 |
15343.0000000000 |
-2.3E-201 |
Rationals are not the same kind of numbers as any of the built-in types. They are almost unlimited in precision. I would say unlimited but you are limited due to the amount of RAM on your machine available for the .NET Framework. This allows them to be used in calculations like the one above where the single, double, and decimal types will be inadequate. This gives Rational numbers the following special properties.
Rationals have no round off error
Rationals do not round off, so how could they have any round off error? (That is close enough to true that you should believe it.) With fixed precision types (single, double, and decimal ), virtually every numeric operation generates a bit more error. Certain actions like adding and subtracting numbers of vastly different sizes or dividing by very small numbers are particularly prone to round off error. That is not to say that Rational numbers are completely free from error. Irrational values such as pi or the square root of 2 can only be expressed approximately, but all in all, the situation is much improved.
Rationals do not experience Catastrophic Cancellation
Catastrophic Cancellation occurs when two numbers that are almost equal are subtracted and the result is rounded to zero. In general, this is a rather unfavorable event, hence the adjective catastrophic. This is what occurred at h=10-16 when we were using doubles. f(x +h) and f(x) became close enough to each other that they were interpreted as zero. Once that happened, it no longer mattered how small h was, it could not balance out the small numerator. As an aside, we might imagine that using f(x+h)/h - f(x)/h instead of (f(x+h)-f(x))/h would help, but alas it does not. This never occurs with Rational numbers. For example, (a + b) - a = b always, unlike with fixed precision types where it is possible for (a + b) - a = 0.
Rationals act as though the machine epsilon were zero
This is something that you probably only care about if you are working with matrices. Here is an almost absurdly simplified explanation. Every matrix has a property called a condition number that describes how invertible (able to be solved) it is. Big values are bad and called ill conditioned. Incurably reprobate seems more apt as this is often an abandon all hope ye who compute here type of situation. Put simply, the number of meaningful (significant) digits that you can use in your answer is determined by the condition number of the matrix multiplied by a mysterious number referred to as the machine epsilon that is dependent on the numerical precision of the type used for calculation. For a double, that should be 1.11E-16. (Please note that the ill named Double.Epsilon constant is something completely different.) Matrices composed of Rational numbers are, in terms of accuracy, far superior from a computational linear algebra perspective.
How to use
There is not much to say. Just add the assembly and then put:
using Mathematics.RationalNumbers;
at the top of your file and you are good to go. They behave as you would expect numbers to behave. There are a few tips worth noting though. Also, in the spirit of full disclosure, at present, there is a limitation in that sin(), cos(), exp(), and the rest of the transcendental functions are not yet implemented.
Using is your friend
The first thing you might want to do with a Rational number is create one. For example, to create 1/3, you could use:
Rational r = new Rational(1,3) ;
but this does not scan well. We could improve it by using casting:
Rational r = (Rational)1/3 ;
but the word "Rational" is long enough to cause distraction. However, this can be improved via aliasing:
using Q = Mathematics.RationalNumbers.Rational;
Then we are free to use the following, which seems most natural as Q is the standard symbol for Rational numbers:
Rational r = (Q)1/3 ;
Regrettably, omitting the (Q) will still allow the expression to compile, but the value will be 0 rather than 1/3 as the explicit cast, the (Q), comes before the division while the implicit cast from integer to Rational would come after the division.
There is another place that using can be of use. Some of the framework's math functions are not in the types themselves, but rather the System.Math type. In particular, the following of them are included in Rational: Abs, Ceiling, Floor , Max, Min, Pow, Round, and Sign. By appropriating "Math":
using Math = Mathematics.RationalNumbers.Rational;
we can write code that looks considerably more familiar:
Rational r = -(Q)1/3 ;
Rational rMag = Math.Abs(-(Q)1/3 );
One of the goals for this library was to allow libraries using doubles to be converted to ones using Rationals via search and replace.
You can code in a semi-Rational manner
It is worth remembering that Rational numbers are a super-set of all the exiting numeric types. For example, the following code works:
Double d = (Double)(Rational)d;
thus one can easily switch back and forth as necessary.
How it works
At its heart, this type is about as simple as they get. It is composed of two BigInteger values, one for the numerator and one for the denominator. It follows the rules for fractions, the ones we all learned in elementary school. Given such simplicity, we might be surprised that the type is close to 800 lines in length without XML comments. How can something so simple need so much code?
The first thing to note is that this is not your ordinary every day class. It is a value type (struct). These are not things we create often. If we look at Microsoft's guidelines, we can see why as they state. (The comments in italics are mine.)
It is recommended that you use a struct for types that meet any of the following criteria:
- Act like primitive types. Simple types you would never want to share across threads.
- Have an instance size under 16 bytes. This is very restrictive, 96 bits or the size of three
Int32s; also BigInteger, Complex, and Decimal don't follow this one.
- Are immutable. Values are only set in the constructor.
- Value semantics are desirable. All fields should be other value types, not reference types.
What kinds of types fit such a description? The vast majority of them (sbyte, byte, char, short, ushort, int, uint, long, ulong, float, double, decimal, BigInteger, Complex) are perhaps better described by the word number rather than ValueType. Most of the rest of the value types are enums. There are just a few exceptions like the Point or DateTime structs.
The heart of the class is as follows.
namespace Mathematics.RationalNumbers
{
[Serializable, StructLayout(LayoutKind.Sequential)]
public struct Rational : IComparable, IEquatable<Rational>, IComparable<Rational>
{
private readonly BigInteger mNumerator; private readonly BigInteger mDenominator;
public BigInteger Numerator
{
get { return mNumerator; }
}
public BigInteger Denominator
{
get { return mDenominator; }
}
...lots of other stuff
}
}
The first thing to note is the declaration and attributes. It is chosen to match the other numeric types, which all implement the same interfaces.
[Serializable, StructLayout(LayoutKind.Sequential)]
public struct BigInteger : IFormattable, IComparable,
IComparable<biginteger>, IEquatable<biginteger>
[Serializable, StructLayout(LayoutKind.Sequential), ComVisible(true)]
public struct Double : IComparable, IFormattable, IConvertible,
IComparable<double>, IEquatable<double>
For consistency with the existing types, all the interfaces except IFormattable were implemented. Rationals are different enough to justify their own formatting, and if we want to use format strings, we can pull off the numerator and denominator separately to format them. The interfaces will all be covered in detail later.
There are only two fields and they are both read only. Setting the fields to readonly is a good practice as it protects us from unintentionally writing methods that have the effect of changing field values.
Constructors
The basic constructor is as follows:
private Rational(BigInteger numerator, BigInteger denominator, bool safe)
{
if (numerator == 0)
{
mNumerator = 0;
mDenominator = 0;
return;
}
else if (denominator == 0)
{
throw new DivideByZeroException();
}
int sign = ((numerator > 0 && denominator > 0) ||
(numerator < 0 && denominator < 0)) ?1 : -1;
if (safe)
{
mNumerator = sign * BigInteger.Abs(numerator);
mDenominator = BigInteger.Abs(denominator);
}
else
{
BigInteger gcd =
BigInteger.GreatestCommonDivisor (numerator, denominator);
mNumerator = BigInteger.Abs(numerator / gcd);
mDenominator = BigInteger.Abs(denominator / gcd);
}
}
First notice that the constructor is private. The public constructor calls the private one through constructor chaining.
public Rational(BigInteger numerator, BigInteger denominator):
this(numerator , denominator, false ) {}
The reason for this is that BigInteger.GreatestCommonDivisor is a potentially expensive operation and we sometimes already know that the numerator and denominator are in lowest terms. For example, the inverse of any rational number is already in lowest terms. Since we know 2/3 is in lowest terms, we also know that 3/2 is in lowest terms. For numbers like this, the computation is negligible, but if the numerator and denominator were 10s of thousands of digits each, the story would be different. The safe mode where the GreatestCommonDivisor is not evaluated is purposely not exposed to the public to reduce the possibility of errors.
All of the other integer types are implicitly cast to BigInteger so that there is no need for other constructors to cover other integral data types such as int or long. Rationals are also supertypes for all of the existing numeric types, save Complex. There is a Rational number that corresponds to each instance of a numeric type and so there should be appropriate constructors.
There is also one more constructor. All value types have an implicitly defined parameter-less constructor. This one sets all the fields to the value of 0. It also cannot be overridden. We also cannot put values in the declarations for the fields. For the Rational type, that means that having the numerator and the denominator both being 0 needs to be a valid state.
public Rational(BigInteger numerator):this(numerator , 1, true ) {}
public Rational(double value)
{
this = Rational.Parse(value.ToString("R"));
}
public Rational(Decimal value)
{
this = Rational.Parse(value.ToString());
}
It turned out to be significantly easier to handle the floating point types via converting them to strings and then parsing the result. This will be detailed in the "ToString and Parse" section.
Basic operations
The following operations are basic to the type and are used in many of the other methods.
IntegerPart/BigIntegerPart and FractionalPart
One of the ways that we are likely to want to express a Rational number is in terms of its integer and fractional parts. For example, 7/4 could be expressed as 1 + 3/4. These very simple methods are quite useful for tasks such as pulling digits for decimal representations. BigIntegerpart and IntegerPart are effectively equivalent, differing only in their return types.
public BigInteger BigIntegerPart
{
get
{
if (Numerator == 0)
{
return 0;
}
return Numerator / Denominator;
}
}
public Rational FractionalPart
{
get
{
return this - BigIntegerPart;
}
}
Inverse
Taking the inverse of a fraction is another common task. The only oddity is that in order to avoid infinity, the inverse of the rational number 0 is 0.
public Rational Inverse
{
get
{
if (Numerator == 0)
{
return this;
}
BigInteger numerator = (Denominator != 0) ? Denominator : 1;
BigInteger denominator = Numerator;
return new Rational(numerator, denominator, true);
}
}
Magnitude
The Magnitude is defined as the exponent that would appear if the Rational were being approximately expressed in scientific notation. For example, 100 or 123 would have a magnitude of 2 while .2 would have one of -1. This is a very useful number to have on hand, so much so that I added an extension method to the BigInteger class to generate it.
public static int Magnitude(this BigInteger value)
{
return (value !=0)?(int)Math.Floor(BigInteger.Log10(BigInteger.Abs(value))):0;
}
The C# code may be obscuring it a bit, but this is just using the definition of the base 10 logarithm. Consider a concrete example.
log(3.2*10<sup>4</sup>) = log(3.2) + log(10<sup>4</sup>)=log(3.2) + 4* log(10) =log(3.2) + 4
log(10) = 1 and log(1) = 0 so log(3.2) is zeroed if we use the Floor method. The if is required as log(0) is minus infinity, which is undesirable.
The Rational case is only slightly different.
public int Magnitude
{
get
{
Rational NumeratorSig =
(Rational)Numerator / BigInteger.Pow(10, Numerator.Magnitude());
Rational DenominatorSig =
(Rational)Denominator / BigInteger.Pow(10, Denominator.Magnitude());
Rational Significand =
NumeratorSig / DenominatorSig; if (Rational.Abs(Significand) < 1)
{
return Numerator.Magnitude() - Denominator.Magnitude() -1 ;
}
return Numerator.Magnitude() - Denominator.Magnitude() +
Significand.BigIntegerPart.Magnitude() ;
}
}
It seems plain that the magnitude of the denominator should be subtracted from the magnitude of the numerator. The thing to note is that the Rational of the two significands (parts with the decimal place) is bound on the top by 9.99999... and on the bottom by .1. This means we might have to shift things over by one to make sure that we are following the rules for scientific notation (first digit is 1-9, not 0).
Structure overrides
Equals
Value types represent values. They are not objects in the sense that we usually use. It makes little sense to differentiate between this 7 or that 7. There is only the value 7. We believe that 7 should equal 7. However, all value types inherit from the object type, which has a very clear definition of equals. Two objects are equal if they reside at the same location in memory. Since this definition is not what we want for a value type in general, or for Rational in particular, equals needs to be overridden.
public override bool Equals(object obj)
{
if (!(obj is Rational))
{
return false;
}
return Equals((Rational)obj);
}
public bool Equals(Rational other) {
if (Numerator == 0)
{
return other.Numerator == 0;
}
return Numerator == other.Numerator && Denominator == other.Denominator;
}
GetHashCode
One of the design considerations for the .NET Framework was that every object should be able to be used as a key for a Hashtable or Dictionary. I'm not sure that I would endorse using Rationals as dictionary keys, but that is irrelevant. If you override Equals, you need to override GetHashCode.
public override int GetHashCode()
{
return Numerator.GetHashCode() * Denominator.GetHashCode();
}
Designing good hashing functions is, to put it mildly, a very complex and advanced topic, far beyond the scope of this article. The one supplied should function adequately, and if it is not being used as a Hashtable or Dictionary key, it really does not matter.
ToString and Parse
It is expected that the ToString method should produce a human readable representation of the number. To accomplish this rather than returning the type name, ToString must be overridden.
public override string ToString()
{
if (mNumerator == 0)
{
return "0";
}
if (mDenominator == 1)
{
return mNumerator.ToString();
}
return mNumerator.ToString() + "/" + mDenominator.ToString();
}
It is expected that there will be a Parse function that can take the results of ToString and return the number. This method will be additionally complicated as it needs to be able to parse all reasonable string representations of the number.
public static Rational Parse(String s)
{
int periodIndex = s.IndexOf(".");
int eIndeix = s.IndexOf("E");
int slashIndex = s.IndexOf("/");
if (periodIndex == -1 && eIndeix ==-1 && slashIndex == -1)
{
return new Rational( BigInteger.Parse (s));
}
if (periodIndex == -1 && eIndeix == -1 && slashIndex != -1)
{
return new Rational(BigInteger.Parse(s.Substring(0, slashIndex)),
BigInteger.Parse(s.Substring(slashIndex +1)));
}
if (eIndeix == -1) {
BigInteger n = BigInteger.Parse(s.Replace(".", ""));
BigInteger d = (BigInteger)Math.Pow(10, s.Length - periodIndex-1);
return new Rational(n, d);
}
else {
int characteristic = int.Parse(s.Substring(eIndeix + 1));
BigInteger ten = 10;
BigInteger numerator =
BigInteger.Parse(s.Substring(0, eIndeix).Replace(".", ""));
BigInteger denominator =
new BigInteger(Math.Pow(10, eIndeix - periodIndex - 1));
BigInteger charPower =BigInteger.Pow( ten,Math.Abs(characteristic));
if (characteristic > 0)
{
numerator = numerator * charPower;
}
else
{
denominator = denominator * charPower;
}
return new Rational(numerator, denominator);
}
}
Extended ToString
The basic ToString will serve as a form of string serialization, but we often want a string representation of a Rational valid to a certain number of decimal places. There are two such functions.
public string ToString(EApproxmationType approximation,int places,bool padWithZeroes){...}
public string ToScientific(int places, bool padwithZeroes){...}
These correspond to formatting in either standard or scientific notation. They are also the most complex routines in the type. Both of the methods use the Digits method which returns a string of digits.
internal static List<string> Digits(Rational r, int n)
{
List<string> digits = new List<string>();
BigInteger IntPart = Rational.Abs(r).BigIntegerPart;
Rational fracPart = Rational.Abs(r).FractionalPart;
int intplaces = IntPart.Magnitude() + 1;
char[] chars = IntPart.ToString().ToCharArray();
for (int i = 0; i < Math.Min(intplaces , n); i++)
{
if (digits.Count > 0 || chars[i] != '0') {
digits.Add(chars[i].ToString());
}
}
while (digits.Count() < n) {
if (fracPart == 0)
{
break;
}
fracPart *=10;
if (digits.Count > 0 || fracPart.IntegerPart != 0)
{
digits.Add(fracPart.IntegerPart.ToString());
}
fracPart = fracPart.FractionalPart;
}
return digits;
}
The routine selects at most n digits from the decimal representation of the number. The Rational is first split into its Integral and Fractional parts. 4/3 would be split into 1 and 1/3. Digits are taken from the IntegerPart and then the FractionalPart until enough digits have been acquired till the fractional part terminates.
The extended ToString takes care of determining how many digits need to be requested from the Digits method and where to place the decimal point. After the digits are retrieved, they are put together in a string and padded if necessary.
public string ToString(EApproxmationType approximation,int places,bool padWithZeroes)
{
StringBuilder sb = new StringBuilder();
if (this.Numerator < 0)
{
sb.Append("-");
}
int pointIndex =this.BigIntegerPart.Magnitude() + 1;
if (this.BigIntegerPart == 0)
{
sb.Append("0.");
pointIndex = -1;
}
Rational working = this;
while (working.BigIntegerPart == 0)
{
working *= 10;
if (working.BigIntegerPart == 0)
{
sb.Append("0");
}
}
bool sf = approximation == EApproxmationType.SignificantFigures;
int digitsNeeded = (sf) ? Math.Max(this.BigIntegerPart.Places(), places) :
this.BigIntegerPart.Places() + places;
int digitsToExtract = (sf) ? places : places + this.BigIntegerPart.Places();
List<string> digits = Digits(working, digitsToExtract);
if (digits.Count < digitsToExtract && !padWithZeroes)
{
digitsNeeded -= (digitsToExtract - digits.Count);
}
for (int i = 0; i < digits.Count; i++)
{
if (i ==pointIndex)
{
sb.Append(".");
}
sb.Append(digits[i]);
}
for (int i = digits.Count(); i < digitsNeeded; i++)
{
if (i == pointIndex)
{
sb.Append(".");
}
sb.Append("0");
}
return sb.ToString();
}
ToScientific is similar except that it puts the number into scientific notation. The placement of the decimal point is easier as it is always after the first digit. Also, there is no distinction between converting the rational to a certain number of decimal places or to a certain number of significant figures. There is the additional complexity of determining the correct exponent. That is done via the very useful Magnitude property which will be covered later.
public string ToScientific(int places, bool padwithZeroes)
{
StringBuilder sb = new StringBuilder();
if (this.Numerator < 0)
{
sb.Append("-");
}
List<string> digits = Digits(this,places);
BigInteger b = this.BigIntegerPart;
Rational fractional = Rational.Abs(this.FractionalPart);
sb.Append(digits[0]);
if (digits.Count > 1 || (places > 1 && padwithZeroes))
{
sb.Append(".");
}
for (int i = 1; i < digits.Count; i++)
{
sb.Append(digits[i]);
}
if (padwithZeroes)
{
for (int i = digits.Count; i < places; i++)
{
sb.Append("0");
}
}
sb.Append("E");
if (this.BigIntegerPart != 0)
{
sb.Append("+");
sb.Append(this.Magnitude);
}
else
{
sb.Append(this.Magnitude);
}
return sb.ToString();
}
I hesitated about placing this code in the text of the article. It is not particularly easy to follow or even that illuminating. It is however typical of the kind of code you create when going back and forth with unit tests. Also, it illustrates that the most difficult task with respect to these semi-primitive data types is conversion and formatting rather than the actual operations that the data type was created for.
Operator overrides
Numeric types often use operators instead of methods. We do not use a plus method to add numbers but rather a plus operator. It should not be surprising that a large number of operators need to be overridden as part of the Rational type.
Equals and not Equals: ==, !=
If we override the Equals method, we should also override the == and != operators. Everyone expects == and Equals to mean the same thing.
public static bool operator ==(Rational r1, Rational r2)
{
return r1.Equals(r2);
}
public static bool operator !=(Rational r1, Rational r2)
{
return ! r1.Equals(r2);
}
Ordering operators: <, <=, >, >=
We also expect to be able to use the ordering operators, both between Rationals and between other numeric types that have been cast to Rationals. As a sample of this type of operator, we have the < operator.
public static bool operator <(Rational r1, Rational r2)
{
return r1.CompareTo(r2)< 0
}
Math operators: +, -, *, /, %
The math operators follow the rules that we learned for fractions in elementary school. Plus and minus are very similar to each other. It should be noticed that zero testing is necessary as all fields zero needs to be a valid state of our struct.
public static Rational operator +(Rational r1, Rational r2)
{
if (r1 == 0){ return r2;}
if (r2 == 0){ return r1;}
if (r1.Denominator == r2.Denominator)
{
return new Rational(r1.Numerator + r2.Numerator, r1.Denominator, false);
}
return new Rational(r1.Numerator * r2.Denominator +
r2.Numerator * r1.Denominator,
r1.Denominator * r2.Denominator, false);
}
We are not limited to the type in question when defining operators. For example, I might want to add an operator for the adding of an int and a Rational.
public static Rational operator +(Rational r1, int i)
{
if (r1 == 0) { return i; }
if (i == 0) { return r1; }
return new Rational(r1.Numerator + i*r1.Denominator,
r1.Denominator, true);
}
public static Rational operator +(int i, Rational r1)
{
if (r1 == 0) { return i; }
if (i == 0) { return r1; }
return new Rational(r1.Numerator + i * r1.Denominator,
r1.Denominator, true);
}
At first glance, it might seem that this is redundant as we will be making integers implicitly cast to Rationals. The reason for this version of the operator is that adding integers will not get my fraction out of least terms. Thus we can save time by not checking. Also, it is advisable that both operators be defined. There is no Abelian (commutative) Attribute we can use to make one definition work for both directions.
The operators for multiplication and division are very similar. The only thing that needs even a little care is handling the zero cases.
public static Rational operator *(Rational r1, Rational r2)
{
if (r1 == 0 || r2 == 0)
{
return 0;
}
return new Rational(r1.Numerator * r2.Numerator,
r1.Denominator * r2.Denominator, false);
}
public static Rational operator /(Rational r1, Rational r2)
{
if (r1 == 0)
{
return 0;
}else if (r2 == 0)
{
throw new DivideByZeroException();
}
return new Rational(r1.Numerator * r2.Denominator,
r1.Denominator * r2.Numerator, false);
}
Casting operators: (Rational), (Double)...
There are two kinds of casting operators that need to be considered, casting to Rationals and casting from Rationals. Casting to Rationals is very easy to deal with as we already have constructors that accept all of the appropriate types. They are all the same in that they just call one of the type's many constructors. As there is a Rational equivalent to each of the other numeric types, the cast to Rational is implicit.
static public implicit operator Rational(int value)
{
return new Rational(value);
}
Casting from Rationals to the other types is only slightly more involved. There are two cases, the integer based types and the floating point types. In the case of integer based types, BigIntegerPart is taken and cast to the appropriate type.
static public explicit operator long (Rational value)
{
return (long)value.BigIntegerPart;
}
The conversion to floating point types is accomplished by generating a string approximation of the Rational and then using the Type's Parse method.
static public explicit operator Single(Rational value)
{
return Single.Parse(value.ToScientific(8, false));
}
static public explicit operator double(Rational value)
{
return Double.Parse(value.ToScientific(17, false));
}
static public explicit operator decimal(Rational value)
{
return decimal.Parse(value.ToString(
EApproxmationType.DecimalPlaces, 29,false));
}
Interfaces
All of the built-in numeric types except Complex follow certain interfaces. These are IFormattable, IComparable, IComparable<T>, and IEquatable<T>. Most also implement IConvertible. The Rational type implements IComparable, IComparable<Rational>, and IEquatable<Rational>.
IEquatable<Rational>
Implementing IEquatable<T> is the last of the three tasks that should be completed in order to manage equality for value types. The other two are overriding the Equals method and the operators == and !=. Implementing this interface is necessary for proper behavior in generic collections such as Dictionaries. The IEquatable<T> interface contains the single method Equals<T>.
public bool Equals(Rational other)
{
if (Numerator == 0)
{
return other.Numerator == 0;
}
return Numerator == other.Numerator && Denominator == other.Denominator;
}
IComparer and IComparer<Rational>
These two interfaces are essential for any numeric type, in that they govern sorting. List.Sort and other generic collections use IComparer<T> while the non-generic ones use IComparer. These two interfaces plus the operators >, <, >=, <= should all be modified together for consistency. The IComparer interface contains CompareTo(object obj) while IComparer<Rational> contains CompareTo(Rational other).
public int CompareTo(object obj)
{
if (!(obj is Rational))
{
throw new ArgumentException();
}
return this.CompareTo( (Rational)obj);
}
public int CompareTo(Rational other)
{
if (this == other)
{
return 0;
}
if (Sign(this) < Sign(other))
{
return -1;
}
if (Sign(this) > Sign(other))
{
return 1;
}
if (Numerator >= other.Numerator && Denominator <= other.Denominator )
{
return 1;
}
if (Numerator <= other.Numerator && Denominator >= other.Denominator )
{
return -1;
}
return Sign(Numerator * other.Denominator - other.Numerator *Denominator );
}
System.MathFunctions
In order to perform some of the common mathematical operations on most numeric types, we need to use a bunch of methods that are found in the System.Math type. As this is a static type, it is not possible to extend it with extension methods. Therefore, the Rational type follows the precedent set by the Decimal and BigInteger types, that static methods are included in the class that match these methods. This is done for consistency, even though some of them, such as Sign, might be more naturally expressed as a property.
Measuring methods: Abs, Sign
public static Rational Abs(Rational value)
{
return new Rational(BigInteger.Abs(value.Numerator),
BigInteger.Abs( value.Denominator), true);
}
public static int Sign(Rational value)
{
return value.Numerator.Sign ;
}
Comparison methods: Min, Max
public static Rational Min(Rational val1, Rational val2)
{
return val1 <= val2 ? val1 : val2;
}
public static Rational Max(Rational val1, Rational val2)
{
return val2 >= val1 ? val2 : val1;
}
Rounding methods: Ceiling, Floor, Round
Ceiling, Floor, and Round are all used to coerce values to the nearest integer. All three are very similar to each other.
public static Rational Floor(Rational value)
{
BigInteger bi = value.BigIntegerPart;
if (value == (Rational)bi)
{
return value;
}
else if (value >= 0)
{
return (Rational)bi ;
}
return (Rational)bi - 1;
}
With Rationals, we might also want to coerce values to other Rational values. For example, we might want the Floor evaluated with respect to thirds.
public static Rational Floor(Rational value, BigInteger denominator)
{
return Floor(value * denominator) / denominator;
}
public static Rational Floor(Rational value, Rational denominator)
{
return Floor(value / denominator) * denominator;
}
Conclusion
I hope this new type will serve you well. Even though I suspect it will appear in the next service pack or framework version, I would bet that the interface will be very similar to the one presented here. The original reason for this project was for use in a Rational valued slider control, but as oft happens, projects outgrow their original bounds. Some of the preliminary methods for that project are contained in the static RationalCollectionHelpers class. This class has considerable potential so stay tuned for more exciting numerics.
Updates
- 7/3/2010: Updates were made to the
GetHashCode and CompareTo methods. There were also other minor code improvements.
- 7/22/2010: The source code now compiles for both .NET and Silverlight. Note that this required some minor changes due to the Silverlight version of the
BigInteger not having a Parse method. Go figure. Also, a correction was made in the CompareTo method.
