Subj : Re: ratio approximation algorithm
To   : comp.programming
From : Alex Fraser
Date : Sat Aug 20 2005 12:49 am

<websnarf@gmail.com> wrote in message
news:1124472515.341956.110120@g14g2000cwa.googlegroups.com...
> Mark  Maglana wrote:
> > 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]
> Nice problem.  Here is my proposal.
>
> Compute the list of all possible (A/B)'s and sort them in order indexed
> by value.  I.e., you have a sorted mapping T:(A/B) -> (A , B).  Ok, now
> create a sorted reciprocal mapping for (D/C) (not C/D) S:(D/C) -> (C ,
> D).
>
> Ok, now for each (D/C), just multiply it by your target x, to get the
> result z = (D/C)*x.  Now for each z, perform a *binary search* in your
> (A/B) list to find the closest A, B.  Remember you *sorted* your A/B,
> so that you can perform a real binary search.  Then just do a typical
> optimizing comparison of tolerance = abs((A/B)*(C/D) - x) to find the
> best one.
>
> This has a running time less than O(|C|*|D|*ln(|B|*|A|)).  Its less
> because the set of fractions C/D is fewer than the pairs (C, D),
> because there are many redundant fractions (remember 1/2 = 2/4.)
>
> I don't know if you can do better.

You can avoid division completely by using A*C and B*D, as has been
suggested already (compute each B*D*X and search for suitable values of
A*C). I don't know about floating point implementation, but if division is
as expensive compared to multiplication as for typical integer
implementation, this could be a worthwhile improvement. There's redundancy
here too: 1*4 = 4*1 = 2*2; I'm not sure if this is any extra advantage.

Alex

.