Subj : Re: ratio approximation algorithm
To   : comp.programming
From : Mark  Maglana
Date : Sat Aug 20 2005 12:10 pm

UPDATES!

Thank you all for your inputs. I've finally finished modifying the code
using most of the suggestions given here. I must say, the results have
been phenomenal! For example, in my old code, searching for matches for
a ratio of 2.5423422 with a tolerance of 0.000005 yielded only 4
matches in 15 seconds. In the new code, it took only 1 second to find
22 matches. Here's a run-down of what I did:

1. I had a sorted list of the possible products (usable for both A*C
and B*D). Each value in this list is unique. That is, the product 20,
for example, only appears once even if it can be produced by either 4*5
or 10*2. The advantage may seem nominal at first, but then considering
that I had two loops, one nested in the other with the outer loop using
this list, I would save at least about 4000 cycles in the inner loop.
All in all this implementation saved me at least 2500*2500 cycles!

2. I had two other lists, actually recordsets, that were identical to
each other. One served as the complete B*D list, the other the complete
A*C list. I know they're similar, but I need them to be two distinct
objects in the inner loop. Each item in either list had 3 fields: the
multiplier, the multiplicand, and the corresponding product.

My code basically ran like this:

1: load products_list
2: load bd_list
3: load ac_list

4: For i=0 to products_list_upperbound
5:   Compute for (X-t)*b*d and (X+t)*b*d
6:   Binary search for index of the item in the products_list closest
to (X-t)*b*d
7:   If the index is found then
8:      j = index
9:      Do while j < upperbound and _
10:             products(j) <= (X+t)*b*d
11:         If (X-t)*b*d <= products(j) <= (X+t)*b*d then
12:            filter bd_list to show only items with
product=products(i)
13:            filter ac_list to show only items with
product=products(j)
14:            loop through filtered bd_list
15:               loop through filtered ac_list
16:                   add the combination to search result
17:               end loop
18:            end loop
19:         End If
20:         j++
21:      Loop
22:   End If
23:Next

Line 4 is the outer loop, Line 9 the inner loop (which runs
conditionally)

Line 6: The binary search used was slightly modified to return the
index below and closest to (X-t)*b*d if there is any.

Lines 12-18: Since my product list removed any redundancies, once I
found the product that satisfied the equation X*b*d = a*c (give or take
the allowed tolerance), I had to re-expand the list, showing only those
list items having that product, loop through it, and save all the found
combinations.

Again, thank you all for the inputs. This has been a very enlightening
endeavor for me.

Mark S. Maglana
Davao City
Philippines

.