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....)