Subj : Re: ratio approximation algorithm
To   : comp.programming
From : CBFalconer
Date : Mon Aug 15 2005 04:31 pm

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?

This solves a different problem, but the technique may be helpful.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>

int main(int argc, char **argv)
{
   int           num, approx, bestnum, bestdenom;
   int           lastnum = 500;
   double        error, leasterr, pi, criterion;

   pi = 4 * atan(1.0);
   criterion = 2 * pi * DBL_EPSILON;
   if (argc > 1) lastnum = strtol(argv[1], NULL, 10);
   if (lastnum <= 0) lastnum = 500;
   printf("Usage: ratpi [maxnumerator]\n"
          "Rational approximation to PI = %.*f\n", DBL_DIG, pi);
   for (leasterr = pi, num = 3; num < lastnum; num++) {
      approx = (int)(num / pi + 0.5);
      error  = fabs((double)num / approx - pi);
      if (error < leasterr) {
         bestnum = num;
         bestdenom = approx;
         leasterr = error;
         printf("%8d / %-8d = %.*f with error %.*f\n",
                 bestnum, bestdenom,
                 DBL_DIG, (double)bestnum / bestdenom,
                 DBL_DIG, leasterr);
         if (leasterr <= criterion) break;
      }
   }
   return 0;
} /* main */

-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson

.