Subj : Re: ratio approximation algorithm
To   : comp.programming
From : Richard Heathfield
Date : Mon Aug 15 2005 08:10 am

Mark  Maglana wrote:

> So right now, I'm looking for an algorithm other than brute force that
> will speed up the searching process. Anyone know of one?

(I presume A, B, C and D are integers.)

It depends whether you need an optimal solution. If you are happy with any 
solution that falls within the given tolerance, then the obvious answer is 
Monte Carlo: keep generating random solutions and checking each for 
fitness. As soon as you find one that is within spec, print it out and 
you're done.

If you are a bit fussier, it might (or might not!) be worth playing with 
genetic algorithms. (Generate a population of "solutions", rank them 
according to fitness - i.e. how close they are to being perfect solutions - 
kill off the most unfit, and use genetic techniques - crossover and 
mutation - to generate new solutions.) Or perhaps you could simply find a 
good-ish solution randomly and then try searching the 80 solutions that 
immediately surround the random one.

Frankly, I'd be surprised if Monte Carlo failed to suit your needs.

I wrote up a Monte Carlo solution generator, and gave it some numbers to 
play with. For not-too-difficult(!) ratios, it wasn't too desperately slow. 
For example, on a 1.4GHz Pentium, it solved 1.2345 to a tolerance of 
0.000001 in an average of seven or eight seconds:

(109 / 97) * (78 / 71) = 1.234500, error -0.000000
after about 18,000,000 trials, taking 0m12.431s

(78 / 71) * (109 / 97) = 1.234500, error -0.000000
after about 12,000,000 trials, taking 0m8.735s

(107 / 66) * (83 / 109) = 1.234501, error 0.000001
after about 8,000,000 trials, taking 0m5.422s

(109 / 97) * (78 / 71) = 1.234500, error -0.000000
after about 4,000,000 trials, taking 0m3.077s

(76 / 93) * (71 / 47) = 1.234500, error 0.000000
after about 12,000,000 trials taking 0m8.295s

Four different solutions in five goes. Not too shoddy. Not exactly 
blitzingly fast, either, but I'm not quite sure what your performance 
criteria are.

-- 
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain

.