Subj : Re: ratio approximation algorithm
To   : comp.programming
From : Alex Fraser
Date : Thu Aug 18 2005 10:29 am

"Mark Maglana" <mmaglana@gmail.com> wrote in message
news:1124332718.467776.176060@g14g2000cwa.googlegroups.com...
> Roger Willcocks wrote:
> > The trick is to notice that the numerator (a.c) and the
> > denominator (b.d) can only take on a small number of distinct values
> > (for instance c >= a), so one can precompute a 6105-entry list of
> > products, and find the minimum err = bdx - ac in 6105^2 comparisons

There may be less than (n^2 + n) / 2 entries, because eg 15*40 and 20*30 are
the same. But I am not sure it is worth worrying about this.

[snip]
> Anyway, I guess the above method still makes 11,325^2 comparisons. I'm
> thinking about using binary search for the innermost loop to further
> improve the time. But I'm still trying to figure out how to modify it
> such that it looks for a range rather than a particular number. Am I
> making any sense or do I sound like a raving idiot at the moment?

I assume that you have an array of products sorted in ascending order. Given
lowerBound and upperBound, you should be able to do a binary search on the
array to find the index of *a* solution, if there is one. Then search
linearly (backwards) to find the smallest product >= lowerBound. Stepping
(forwards) through the array from that point, all products <= upperBound are
solutions.

Alex

.