[Edu-sig] Brute force solutions
David Handy
david at handysoftware.com
Wed Sep 21 20:39:05 CEST 2005
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/
More information about the Edu-sig
mailing list