Results 1 to 2 of 2

Math Help - Rational calculation performance

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    1

    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....)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Geetarman View Post
    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
    Last edited by CaptainBlack; March 10th 2010 at 06:10 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sales and Performance
    Posted in the Business Math Forum
    Replies: 2
    Last Post: June 21st 2011, 02:45 PM
  2. Combining Performance Metrics
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 5th 2010, 04:14 AM
  3. System Performance - Big Oh and Big Omega
    Posted in the Statistics Forum
    Replies: 3
    Last Post: July 6th 2010, 01:55 PM
  4. Car performance calculations
    Posted in the Statistics Forum
    Replies: 0
    Last Post: June 23rd 2010, 02:33 AM
  5. Help on Improving performance for MATLAB function
    Posted in the Math Software Forum
    Replies: 3
    Last Post: March 4th 2009, 10:20 AM

Search Tags


/mathhelpforum @mathhelpforum