Re: ratio approximation algorithm


"Richard Heathfield" <invalid@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:ddpf4a$2bo$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> 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


.

Quantcast