Subj : Re: ratio approximation algorithm
To   : comp.programming
From : websnarf
Date : Fri Aug 19 2005 11:28 am

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.
>
> Now, I have a bit of programming background and tried producing a
> program that will speed up this searching process. However, I could
> only muster a brute force method of searching which is hardly an
> elegant solution. Furthermore, there are certain ratios where brute
> force will take forever to solve. My workaround was to  provide an
> option to the user that specifies the search's starting point (example,
> start at 50, instead of 10) as well as the direction (search up or
> down). Still there are times when the search takes a while and it
> becomes more of a trial and error practice.
>
> So right now, I'm looking for an algorithm other than brute force that
> will speed up the searching process. Anyone know of one?

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 might like to look into Farey
sequences (http://mathworld.wolfram.com/FareySequence.html) to see if
there is anything you can do with the straight mathematics to help you.

-- 
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

.