Subj : Re: ratio approximation algorithm
To   : comp.programming
From : CTips
Date : Mon Aug 15 2005 03:43 pm

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.
> 
> 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.

I'm changing notation to use a,b,c,d instead of A,B,C,D.
I'm assuming that '/' in a/b is real, not truncating integer divison.
I'm assuming that a,b,c,d cannot take on all values in a particular 
range, but must be selected from a set A,B,C,D respectively.
I'm assuming that the tolerance is an absolute number, as opposed to a 
ratio.

Please let me know if my assumptions are wrong.

The problem is find a in A, b in B, c in C, d in D that solve
	| x - a/b . c/d | < t
where t is the tolerance.

This is equivalent to solving
	-t < b.d.x - a.c < t

One method would be for all b.d.x, compute x.b.d, find closest a.c, and 
then check to see if they satisfy the tolerances. One would:
compute all a.c's O(|A|.|C|)
sort O(|A|.|C| log(|A|.|C|))
for each b,c pair do a binary search to find closest value to x.b.d 
O(|B|.|D| log(|A|.|C|))

so, yeielding an algorithm of O(max(|B|.|D|, |A|.|C|) log(|A|.|C|))

If the set sizes are small, say 100-1000 elements each, I wouldn't 
bother trying to optimize much more than this. I think, even if the sets 
were 10,000 elements each, you'd still be under 1sec response times.

.