[Edu-sig] Brute force solutions

[David Handy]

On Wed, Sep 21, 2005 at 06:44:01PM +0100, Peter Bowyer wrote:
> At 14:33 21/09/2005, you wrote:
> >At the cost of roughly doubling the complexity of the code (19 lines instead
> >of ten lines in the function body), I was able to improve the performance by
> >a factor of more than 6500, while basically still using the same
> >"brute-force" approach of guessing a number, adjusting the guess by a delta,
> >and noticing which number gets the lowest error.
> 
> Psyco also makes a very noticeable difference:
> 
> Without:
> Slow method -- result: 1.61803406588 time: 1.40232660855 seconds
> Faster method -- result: 1.6180333003 time: 0.000200135212716 seconds
> 2 digits more precision -- result: 1.61803398295 time: 
> 0.000242882824493 seconds
> 
> With psyco.full()
> Slow method -- result: 1.61803406588 time: 0.256314531595 seconds
> Faster method -- result: 1.6180333003 time: 3.65800681372e-005 seconds
> 2 digits more precision -- result: 1.61803398295 time: 
> 4.53755994128e-005 second

Thanks for bringing up Psyco. This is an example of something Psyco can
speed up, with about a 5.5x improvement for both my algorithm and Kirby's.

However, it doesn't change the fact that original agorithm doesn't scale
well.  Try 12 digits of precision instead of 6:

Slow method -- result: 1.61803406588 time: 0.753984212875 seconds
Faster method -- result: 1.6180333003 time: 0.000110749006271 seconds
2 digits more precision -- result: 1.61803398295 time: 0.000144357919693
seconds
6 digits more precision -- result: 1.61803398875 time: 0.000229076862335
seconds

6 more digits of precision takes the optimized algorithm only 2x more time.

With the original algorithm, 6 digits more precision takes 1000000x more
time. Even with Psyco, it would take about three days to calculate phi to
12 decimal places on your machine.

-- 
David Handy
Computer Programming is Fun!
Beginning Computer Programming with Python
http://www.handysoftware.com/cpif/