Re: ratio approximation algorithm

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

Relevant Pages

  • Re: Set Repeatability
    ... It's possible for points in the same run to be less than the proximity ... The closest two points in the same run could be would ... be 5um, with a standard proximity tolerance being 10um, but anywhere ... Quantizing to a fixed grid introduces the problem where points may be ...
    (sci.stat.math)
  • access form seach: how to set tolerances to guide results given?
    ... I want a form to give results from a database that are closest to the values ... entered (within a tolerance that I would like to be able to set). ... Prev by Date: ...
    (microsoft.public.access.forms)
  • Re: Re: Re: [9fans] release -1 of smacme
    ... On 7/7/06, Brantley Coile wrote: ... People have different levels of tolerance for the signal to noise ... ratio that is often upredictable on any given mailing list. ...
    (comp.os.plan9)