Subj : Re: ratio approximation algorithm
To   : comp.programming
From : Roger Willcocks
Date : Thu Aug 18 2005 11:35 pm

"Mark Maglana" <mmaglana@gmail.com> wrote in message 
news:1124332718.467776.176060@g14g2000cwa.googlegroups.com...
> Roger Willcocks wrote:
>> The trick is to notice that the numerator (a.c) and the
>> denominator (b.d) can only take on a small number of distinct values (for
>> instance c >= a), so one can precompute a 6105-entry list of products, 
>> and
>> find the minimum err = bdx - ac in 6105^2 comparisons
>
> That one suggestion alone improved my search times by leaps and bounds.
> Why the heck didn't I think of that earlier??? :-)
>
> Anyway, my search now goes as follows
>
> For bd_list = MIN To MAX
>     lowerBound = (X - t) * b * d
>     upperBound = (X + t) * b * d
>     For ac_list = MIN To MAX
>          If a * c >= lowerBound And a * c <= upperBound Then
>             '***save found combination
>          End If
>     Next
> Next
>
> What I'm actually trying to do here is find as many combinations within
> a given deadline (usually 15 seconds). With the above method, what used
> to be a search result of 2 or 3 items has jumped to 200+!
>
> Anyway, I guess the above method still makes 11,325^2 comparisons. I'm
> thinking about using binary search for the innermost loop to further
> improve the time. But I'm still trying to figure out how to modify it
> such that it looks for a range rather than a particular number. Am I
> making any sense or do I sound like a raving idiot at the moment?
>

You only need to check the pairs where a >=c and b >= d. That should speed 
things up a bit.

For what it's worth, here's the (C) program I wrote. It only outputs the 
'best' combination but it wouldn't be hard to make it retain a list of the 
near misses. (Hint: use heapsort).

<<<snip>>>

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

struct product {
    int i, j, p;
} list[7000];

int main(int argc, char* argv[])
{
    int listlen = 0;
    int i, j;

    for (i = 10; i < 120; i++) {
        for (j = i; j < 120; j++) {
            list[listlen].p = i * j;
            list[listlen].i = i;
            list[listlen].j = j;
            listlen++;
        }
    }

    printf("%d\n", listlen);

    double target = atof(argv[1]);

    double besterr = 100000.0;
    int ibest = 0, jbest = 0;

    for (i = 0; i < listlen; i++) {
        for (j = 0; j < listlen; j++) {
            double err = list[i].p * target - list[j].p;

            if (err < 0)
                err = -err;

            if (err < besterr) {
                besterr = err;
                ibest = i;
                jbest = j;
            }
        }
    }

    printf("%d . %d x %f = %d . %d\n", list[ibest].i, list[ibest].j, target, 
list[jbest].i, list[jbest].j);
    return 0;
}

<<<snip>>>

--
Roger

.