Subj : Re: ratio approximation algorithm
To   : comp.programming
From : Tim Rentsch
Date : Thu Aug 18 2005 12:08 am

"Mark  Maglana" <mmaglana@gmail.com> writes:

> Hello,
> 
> I'm trying to find the most effective algorithm for solving a certain
> problem in our shop. The case is this: there are times when we are
> supposed to find a combinationof 4 tools that approximates a certain
> ratio. The computation is as follows:
> 
> (A/B)x(C/D) = X
> 
> The possible values for tools A, B, C, and D ranges from 10 to 120.
> Sometimes, however, this range changes.
> 
> What happens here is that we are given a value for X, a ratio which may
> or may not be a whole number. We're supposed to find the combination
> for A, B, C, and D that produces X or a value that closely approximates
> it. Most of the time, we are given a tolerance which varies. Sometimes
> that tolerance is 0.0005, sometimes it's 0.000001.
> 
> [snip]
> 
> So right now, I'm looking for an algorithm other than brute force that
> will speed up the searching process. Anyone know of one?

Glossing over just a few minor details...

    calculate a/b for all pairs of a and b .. call the result ab[]
    calculate c/d for all pairs of c and d .. call the result cd[]
    sort ab[] from low to high
    sort cd[] from high to low 

    high = infinity,  low = 0,  i = 0,  j = 0
    while  i < index_limit(ab[])  &&  j < index_limit(cd[])
      product = ab[i] * cd[j] 
      if  product < X
        i += 1
        if  product > low
          low = product
          remember which a,b,c,d are the best lower bound
        endif
      else
        j += 1
        if  product < high
          high = product
          remember which a,b,c,d are the best upper bound
        endif
      endif
    end

    choose either the best upper bound or best lower bound,
        as appropriate

This approach has the nice property that if the sets A, B, C, D
rarely change, the sorted lists ab[] and cd[] can be precomputed
and then a run for any particular X will take O( AB + CD ), where
AB = index_limit(ab[]) and CD = index_limit(cd[]).

Even with the sorting included, a set of 1000 common values (that
is, ~500,000 pairs) can easily be processed in under a second.

Some obvious improvements if some or all of the sets are equal
are left as an exercise to the reader.

.