Subj : Re: ratio approximation algorithm To : comp.programming From : Roger Willcocks Date : Wed Aug 17 2005 12:59 am "Richard Heathfield" wrote in message news:ddpf4a$2bo$1@nwrdmz01.dmz.ncs.ea.ibs-infra.bt.com... > 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. Hmm, a pure brute force approach took 0.37 seconds on my laptop (1.8GHz Pentium). 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, which incidentally occurs at: 47 * 93 * 1.2345001144 = 71 * 76 yielding four potential solutions for a,b,c,d. This could be made faster still by breaking out of the inner loop when the error changes sign. -- Roger .