Subj : Re: ratio approximation algorithm
To   : comp.programming
From : googmeister
Date : Mon Aug 15 2005 02:40 am

Mark  Maglana wrote:
> 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.

Here's a related problem that might be useful: Given a real number x,
find the best rational approximation A/B, say where A, B are less than
N. The problem has a fast and elegant solution - Google for something
like "Stern Brocot tree" and "best rational approximation".
One way to use this idea is to enumerate all possible values of C, D,
and then try to find the best rational approximation to DX/C for
each pair of C and D. It almost solves your problem, except that
you are putting lower limits on A and B.

Another (not quite brute force) solution is to enumerate all legal
values of A, B, and C. Then estimate what D = floor or ceiling
of AC/BX (or boundary value if outside boundary). This turns a
(pure brute force) quadruple loop into a triple loop.

.