BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 1.1+

Rational Number Arithmetic

Standard arithmetic uses integers or floating-point values for operands and results. Rational numbers, or fractions, are not amongst the standard data types. In this article, we will create a structure for fractions and add arithmetic functionality.

Finding the Greatest Common Divisor

The GCD of two values can be determined using the Euclidean Algorithm. This algorithm follows an iterative process. The first value is divided by the second value and the remainder determined. If the remainder is zero, the GCD is the first value. If the remainder is non-zero, the process is repeated using the second term and the remainder from the calculation. The algorithm and its proof are explained in the above link.

To implement the algorithm, add the following GetGCD method. The method calls itself iteratively until the greatest common divisor is determined. As it uses to instance fields it can be declared as static:

private static int GetGCD(int term1, int term2)
{
    if (term2 == 0)
        return term1;
    else
        return GetGCD(term2, term1 % term2);
}

When creating a new rational number, the constructor reduces it to its lowest terms using the two added methods. This can now be tested using the following code in the Main method of the Program class:

RationalNumber rn = new RationalNumber(5, 10);
Console.WriteLine("{0}/{1}", rn.Numerator, rn.Denominator);     // Outputs "1/2"

Creating the Addition Operator

Now that the rational number structure is able to hold a fraction in its lowest terms, we can add the arithmetic functions. To achieve this, we will overload the operators for +, -, * and / with new versions that supply the correct functionality for addition, subtraction, multiplication and division of fractions. The first to be created is the addition operator. To add two rational numbers together, the following formula is used:

Rational Number Addition

This formula can be added to the structure by adding the following overloaded operator, which simply creates a new rational number using the equation shown above. The act of creating the new fraction will also reduce it to its lowest terms automatically.

public static RationalNumber operator +(RationalNumber r1, RationalNumber r2)
{
    return new RationalNumber((r1.Numerator * r2.Denominator)
        + (r2.Numerator * r1.Denominator), r1.Denominator * r2.Denominator);
}

Adding the Subtraction Operator

Subtraction of rational numbers uses a similar formula to addition. It is:

Rational Number Subtraction

To create the overloaded subtraction operator, add the following code to the structure.

public static RationalNumber operator -(RationalNumber r1, RationalNumber r2)
{
    return new RationalNumber((r1.Numerator * r2.Denominator)
        - (r2.Numerator * r1.Denominator), r1.Denominator * r2.Denominator);
}

Adding the Multiplication and Division Operators

Finally we can add the operators for multiplication and division. To multiply, the numerators of the fraction are multiplied together, as are the denominators. For division, the fraction being divided by is inverted before performing a multiplication. The formulae for these operations are as follows:

Rational Number Multiplication

Rational Number Division

To create the two operators, add the following code to the structure:

public static RationalNumber operator *(RationalNumber r1, RationalNumber r2)
{
    return new RationalNumber(r1.Numerator * r2.Numerator, r1.Denominator * r2.Denominator);
}

public static RationalNumber operator /(RationalNumber r1, RationalNumber r2)
{
    return new RationalNumber(r1.Numerator * r2.Denominator, r1.Denominator * r2.Numerator);
}

Testing the Rational Number Arithmetic

The completed structure can now be tested using the Main method of the program class. Try the following calculations:

RationalNumber r1 = new RationalNumber(3, 4);
RationalNumber r2 = new RationalNumber(2, 3);

RationalNumber add = r1 + r2;   // add = 17/12
RationalNumber sub = r1 - r2;   // sub = 1/12
RationalNumber mul = r1 * r2;   // mul = 1/2
RationalNumber div = r1 / r2;   // div = 9/8

NB: For further testing, download the source code and an interactive Windows-based demonstration, using the link at the start of this article. The structure in the example also includes an additional property that returns the fraction as a decimal value.

31 May 2008