Bisection method perhaps?!
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
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.
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.
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.