Re: [Edu-sig] Brute force solutions
I'm sorry, but I couldn't help taking Kirby's findphi() function as a personal challenge. 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. Why bother optimizing, when phi is a constant? Because using my approach, you can add two digits more precision to the answer with less than 30% more time, whereas the original approach would cost 100x (10000% as much) time for 2 more digits of precision. This refines Kirby's statement that "you get greater accuracy for more cycles" - it doesn't have to be a linear trade-off. (Yes, I know the original version wasn't claimed to be optimized, but it was crying to be optimized...) # phi.py def findphi(step = 0.01): """ step -> -----|---------- (a+b)=1 a b Lengthen a stepwise, while testing how closely b/a approaches 1/b, and return b/a for the least difference. """ diff = b = 1.0 a = phi = 0 while a < b: a += step b = 1 - a e = abs(b/a - 1/b) if e < diff: phi = b/a diff = e return phi def findphi2(tolerance=0.01): a = tolerance N = 8.0 step = (0.5 - a) / N last_e = INFINITY = 1e+30 while True: b = 1.0 - a e = abs(b/a - 1/b) if e < tolerance: break if e > last_e: a -= 2.0 * step # tricky! must go back 2 steps if a < tolerance: a = tolerance step /= N last_e = INFINITY else: a = a + step last_e = e return b / a def test(): import timeit print "Slow method -- result:", findphi(0.000001), n = 10 timer1 = timeit.Timer(stmt='findphi(0.000001)', setup='from phi import findphi') t1 = timer1.timeit(number=n) print "time:", t1/n, "seconds" print "Faster method -- result:", findphi2(0.000001), timer2 = timeit.Timer(stmt='findphi2(0.000001)', setup='from phi import findphi2') n = 1000 t2 = timer2.timeit(number=n) print "time:", t2/n, "seconds" print "2 digits more precision -- result:", findphi2(0.00000001), timer2 = timeit.Timer(stmt='findphi2(0.00000001)', setup='from phi import findphi2') n = 1000 t2 = timer2.timeit(number=n) print "time:", t2/n, "seconds" if __name__ == '__main__': test() # end-of-file david@arno2:~$ python phi.py Slow method -- result: 1.61803406588 time: 0.755390405655 seconds Faster method -- result: 1.6180333003 time: 0.000112377882004 seconds 2 digits more precision -- result: 1.61803398295 time: 0.000145354032516 seconds david@arno2:~$ python -c "print 0.755390405655/0.000112377882004" 6721.87793705 On Tue, Sep 20, 2005 at 04:58:32PM -0700, Kirby Urner wrote:
Per my 'Pentagon math' thread, I think the golden ratio (phi) is an important one to explore in K-12.[1] It's one of those key nodes in our curriculum network.
Given a regular pentagon, the ratio of a diagonal to an edge is phi. In other words, that famous pentacle pattern is phi-edged, vis-?-vis a containing pentagon of edges 1.[2]
Although we have many closed form algebraic methods for deriving phi, computers give us this power to solve through brute force. Some may frown on using such "mindless methods" but I'm thinking to go ahead and introduce them -- not exclusively, but as an exhibit along the way.
In the Python function below, we're looking for a way to break a line of unit length into two segments, the shorter 'a' and the longer 'b', such that the ratio b:a is as close as feasible to the ratio of the whole to b (1:b).
We move 'a' to the right by tiny increments, and keep track of which value minimizes the difference between these two ratios:
def findphi(step = 0.01): """ step -> -----|---------- (a+b)=1 a b
Lengthen a stepwise, while testing how closely b/a approaches 1/b, and return b/a for the least difference. """ diff = b = 1.0 a = phi = 0 while a < b: a += step b = 1 - a e = abs(b/a - 1/b) if e < diff: phi = b/a diff = e return phi
findphi(0.000001) 1.6180340658818939
Some lessons that might be learned from this approach:
(1) when working with floats, you want to compare differences, not check for equalities, e.g. looking for when b/a == 1/b would be a bad idea.
(2) you get greater accuracy in exchange for more cycles
(3) visualization helps
The last point is especially important. The code itself says nothing about lines. The diagram is what explains the logic behind the algorithm -- which is why it's included right in the comments, as primitive ASCII art (bad form, or a good idea?).
Kirby
[1] http://mathforum.org/kb/message.jspa?messageID=3867841&tstart=0
[2] http://altreligion.about.com/library/glossary/symbols/bldefswiccasymbols.htm
PS: happy birthday Dawn Wicca (9/20/2005)
_______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
-- David Handy Computer Programming is Fun! Beginning Computer Programming with Python http://www.handysoftware.com/cpif/ ----- End forwarded message ----- -- David Handy Computer Programming is Fun! Beginning Computer Programming with Python http://www.handysoftware.com/cpif/
(Yes, I know the original version wasn't claimed to be optimized, but it was crying to be optimized...)
Yes. This is a valuable addition to the thread. Thanks for taking the time. Reminds me of when Tim Peters used to swing by in the early days of edu-sig and optimize the hell out of my algorithms. I just agreed to teach Python to 8th graders for 9 weeks (one session per week) in my daughter's school, starting in November. There's a good chance I'll be using this phi stuff. Mine original draft makes sense to set the stage, cuz the reasoning is so dang primitive. Yours adds a layer of sophistication more reflective of how real world programmers learn to squeeze the most out of their cycles. Of course all of this requires temporarily ignoring the fact that algebraic methods give us a way to compute phi as simply (1 + math.sqrt(5))/2.0. Kirby
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 -- Maple Design - quality web design and programming http://www.mapledesign.co.uk
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/
participants (3)
-
David Handy -
Kirby Urner -
Peter Bowyer