Subj : Re: ratio approximation algorithm
To   : comp.programming
From : Mark  Maglana
Date : Wed Aug 17 2005 08:38 pm

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

That one suggestion alone improved my search times by leaps and bounds.
Why the heck didn't I think of that earlier??? :-)

Anyway, my search now goes as follows

For bd_list = MIN To MAX
     lowerBound = (X - t) * b * d
     upperBound = (X + t) * b * d
     For ac_list = MIN To MAX
          If a * c >= lowerBound And a * c <= upperBound Then
             '***save found combination
          End If
     Next
Next

What I'm actually trying to do here is find as many combinations within
a given deadline (usually 15 seconds). With the above method, what used
to be a search result of 2 or 3 items has jumped to 200+!

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?

.