# Rational calculation performance

• Mar 10th 2010, 03:28 AM
Geetarman
Rational calculation performance
I have this method which calculates a new Rational (this is simply a class that holds a numerator and denominator) given an input Rational.

public static Rational RightBound(Rational left)
{
long lNum = (long)left.Numerator;
long lDen = (long)left.Denominator;
for (long i = 1; i <= lDen; i++)
{
if ((lNum * i + 1) % lDen == 0)
{
return new Rational((int)((lNum * i + 1) / lDen), (int)i);
}
}
}

It calculates the value of i based on the equation (lNum * i + 1) % lDen
(% is a modulus operator).
This is fine and works (although to be honest I dont really understand what it is doing). The problem is that when the input denominator becomes large the performance is not good - it can sit in the loop several million times and we call this method millions of times!

Does anyone recognize what this is doing and can suggest an alternative way to calculate i?

Or alternatively a condition to reduce the loop size eg i is always less than the input numerator (I know it is not but....)
• Mar 10th 2010, 05:31 AM
CaptainBlack
Quote:

Originally Posted by Geetarman
I have this method which calculates a new Rational (this is simply a class that holds a numerator and denominator) given an input Rational.

Code:

```public static Rational RightBound(Rational left) {             long lNum = (long)left.Numerator;             long lDen = (long)left.Denominator;             for (long i = 1; i <= lDen; i++)             {                 if ((lNum * i + 1) % lDen == 0)                 {                     return new Rational((int)((lNum * i + 1) / lDen), (int)i);                 }             }   }```
It calculates the value of i based on the equation (lNum * i + 1) % lDen
(% is a modulus operator).
This is fine and works (although to be honest I dont really understand what it is doing). The problem is that when the input denominator becomes large the performance is not good - it can sit in the loop several million times and we call this method millions of times!

Does anyone recognize what this is doing and can suggest an alternative way to calculate i?

Or alternatively a condition to reduce the loop size eg i is always less than the input numerator (I know it is not but....)

At a guess this is trying to rewrite the rational in lowest terms (but that is a guess, it is not easy to see what this is trying to do). In effect you want to find the greatest common divisor (gcd) of the numerator and denominator then divide both numerator and denominator by this. We usually use the Euclidean Algorithm for this.

Having animated this in another package I can say it is not reducing the rational to lowest terms - sorry

It appears to be finding the smallest positive i <= left.Denominator such that left.Numerator*i+1 is divisible by left.Denominator and returning a rational with numerator (left.Numerator*i+1)/left.Denominator and denominator i.

CB