Results 1 to 5 of 5

Math Help - Determining the closest quotient using integer numerator and denominator

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    UK
    Posts
    3

    Determining the closest quotient using integer numerator and denominator

    The problem is to detemine both an integer numerator and integer denominator (both in the range 0 through 1023) for a quotient that matches a target value as closely as possible.

    For a simple example the target value may be 0.595. In this case a denominator of 595 and numerator of 1000 would provide and exact to 0.595 when the quotient is calculated.

    A harder example might be 0.595452. In this case a numerator of 596 and a denominator of 1001 provides a fairly close match, but is there a closer one?

    I have thought this through and think there may be a way to do this using an itterative method. What would be neat is if there was a method that could be used to calculate the numerator and denominator values directly that matches any target value (within a range) as closely as possible.

    Any ideas would be appreciated.
    Regards
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13

    Re: Determining the closest quotient using integer numerator and denominator

    Bisection method perhaps?!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Determining the closest quotient using integer numerator and denominator

    From a software point of view, there's an approach that's lightning fast, but (there's always a but) consumes (wastes?) a ridiculous amount of memory to win you that speed. Because the numerator and denominator both in the range 0 to 1023, you could prepare a table of ratios ahead of time, with their decimal expansions, and then order it. When you examine a decimal number, you'd zip right to the nearest such ratio. It's a table with about a million entries (half that if only looking at numbers 0 to 1), each entry having an integer numerator, integer denominator, and a float that's its the quotient. That's actually not too serious a memory burden for a typical PC.

    I also found this: Best rational approximation — The Endeavour

    Surely there's more out on the web, about how to best code this task.
    Last edited by johnsomeone; September 29th 2012 at 03:01 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2012
    From
    UK
    Posts
    3

    Re: Determining the closest quotient using integer numerator and denominator

    Hi,

    yes that thought did occur to me but the problem is that it is for an embedded system and this amount of memory does not exist. Another method would be to use two loops that calculated the quotient for each numerator and denominator pair. This would require no extra memory but would need a million calculations and comparisons. The link that you provided, many thanks, I discovered last night or early this morning I should say, and the method there I did code and test which worked but did not always produce the best approximation (but did most of the time). Many thanks for your thoughts, at least we are thinking on similar lines.

    I have discovered continued fractions (CF) which allow both rational and irrational numbers to be represented using a sequence of recursive reciprocals (sounds painful but quite simple to understand). One applicaiton of CFs is to find the best rational approximation to irrational numbers. Just what I am looking for.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Determining the closest quotient using integer numerator and denominator

    Other than knowing what they are, I've never fooled with continued fractions. So that's a useful "CF's are relevant to this kind of problem" fact for me to file away too.
    I'm glad you found what you needed.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Numerator and denominator
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 17th 2011, 09:38 AM
  2. Replies: 0
    Last Post: May 8th 2011, 09:23 AM
  3. Replies: 1
    Last Post: October 18th 2010, 02:30 AM
  4. Replies: 4
    Last Post: March 4th 2010, 08:08 PM
  5. variable in the numerator and denominator
    Posted in the Math Topics Forum
    Replies: 8
    Last Post: October 18th 2006, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum