# Brute force solutions Classic List Threaded 15 messages Open this post in threaded view
|

## Brute force solutions

 Per my 'Pentagon math' thread, I think the golden ratio (phi) is an important one to explore in K-12.  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. 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  http://mathforum.org/kb/message.jspa?messageID=3867841&tstart=0 http://altreligion.about.com/library/glossary/symbols/bldefswiccasymbols.htmPS:  happy birthday Dawn Wicca (9/20/2005) _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

Open this post in threaded view
|

## Re: Brute force solutions

 > (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 _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 In reply to this post by david-2 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  _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 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/_______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 In reply to this post by david-2 On Wed, Sep 21, 2005 at 09:31:41AM -0700, Kirby Urner wrote: > 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. Your original draft was a great baseline. That's one good reason not to prematurely optimize: it makes you look like a hero when you optimize later. :) > > 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. The technique is generally useful to solve any equation of one variable, given: 1. You have an interval in which the solution lies 2. You have an error function that is monotonically increasing over the interval the further you get from the solution (and goes to zero at the solution) I think exposing students to numerical equation solving using Python can give them an understanding that will help them later when they are trying to, i.e. figure out how to solve a problem with their fancy caculator, spreadsheet functions, etc. > > Kirby > > -- David Handy Computer Programming is Fun! Beginning Computer Programming with Python http://www.handysoftware.com/cpif/_______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 David Handy wrote: > On Wed, Sep 21, 2005 at 09:31:41AM -0700, Kirby Urner wrote: > >>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. > > > Your original draft was a great baseline. That's one good reason not to > prematurely optimize: it makes you look like a hero when you optimize > later. :) > > >>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. > > > The technique is generally useful to solve any equation of one variable, > given: > > 1. You have an interval in which the solution lies > 2. You have an error function that is monotonically increasing over the > interval the further you get from the solution (and goes to zero at the > solution) > If you have the sign of the error, you can also make use of simple bisection (aka binary search). Here's a version: def findphi3(tolerance=0.01):      low = 0.0      high = 1.0      while True:          a = (low + high)/2.0          b = 1.0-a          e = b/a - 1/b          if abs(e) < tolerance:              break          if  e > 0:              low = a          else:              high = a      return b/a Which turns out to be a bit more efficient than the adaptive stepsize version in this case: Slow method -- result: 1.61803406588 time: 0.756837797165 seconds Faster method -- result: 1.6180333003 time: 0.000106906890869 seconds Bisection -- result: 1.61803328419 time: 3.86953353882e-05 seconds > I think exposing students to numerical equation solving using Python can > give them an understanding that will help them later when they are trying > to, i.e. figure out how to solve a problem with their fancy caculator, > spreadsheet functions, etc. > > >>Kirby >> >> > > -- John M. Zelle, Ph.D.             Wartburg College Professor of Computer Science    Waverly, IA [hidden email]          (319) 352-8360 _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 In reply to this post by david-2 > On Wed, Sep 21, 2005 at 09:31:41AM -0700, Kirby Urner wrote: > >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. I've been considering this a bit. The closed form here begs the question, what is math.sqrt(5)? Sure, we have a built-in function that computes this, but someone had to write the algorithm that computes sqrt. That calculation makes use of numerical techniques similar to what we are discussing w.r.t. phi (much more efficient ones, of course). In a sense, you could view your discussion as a look under the hood at possible implementations. In fact, I would think a good problem to tackle in a math class is to develop some algorithms for approximating square roots. Various "guess and check" techniques can be successful. Newton's method is vary good, and can easily be "derived"/motivated without actually looking at any of the calculus. --John -- John M. Zelle, Ph.D.             Wartburg College Professor of Computer Science    Waverly, IA [hidden email]          (319) 352-8360 _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 In reply to this post by Kirby Urner On 22 Sep 2005 at 12:00, (Kirby Urner) wrote: > > 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 My approach to teaching about phi is by asking kids to draw construction #78 http://mondragon.angeltowns.net/paradiso/Construcciones.html  Daniel ***************************** OpenWorld Learning http://www.openworldlearning.org_______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 > -----Original Message----- > From: [hidden email] [mailto:[hidden email]] On > Behalf Of Daniel Ajoy > Sent: Thursday, September 22, 2005 10:07 AM > To: [hidden email] > Subject: Re: [Edu-sig] Brute force solutions > > My approach to teaching about phi is by asking kids to draw > construction #78 > > http://mondragon.angeltowns.net/paradiso/Construcciones.htmlThat would be more my approach as well. My learning theory - yes I am repeating myself - is that it is absolutely disorienting and ineffective to loose all sense of history when approaching these things.   It is great to get to the algorithmics, but we can't get there effectively by skipping over 30 centuries of history. Start by drawing pictures in the sand. But certainly don't stop there. And there comes appoint when there are no pictures in the sand to be drawn. The necessary pictures became too complex.  Mathematicians - 17th century, say  - began drawing the pictures in their head.  But they were in fact still drawing pictures. With computers we can begin to draw those pictures, and better pick their brains.  That's essentially what PyGeo is about. Art _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 In reply to this post by John Zelle > I've been considering this a bit. The closed form here begs the > question, what is math.sqrt(5)? Sure, we have a built-in function that > computes this, but someone had to write the algorithm that computes > sqrt. That calculation makes use of numerical techniques similar to what > we are discussing w.r.t. phi (much more efficient ones, of course). > Good point.  A mathematician gets around this with a certain philosophy of language that says "if I just write sqrt(5) -- using a surd -- that's already infinitely precise."  Then he gets to look down his nose at those imprecise computer people who traffic in floating point evaluations.   Those floating point people don't have the benefit of "real numbers." > In a sense, you could view your discussion as a look under the hood at > possible implementations. In fact, I would think a good problem to > tackle in a math class is to develop some algorithms for approximating > square roots. Various "guess and check" techniques can be successful. > Newton's method is vary good, and can easily be "derived"/motivated > without actually looking at any of the calculus. > > --John I've a couple times implemented the old manual algorithm for finding square roots.  I might be able to dig those up for discussion.  The longer it runs, the more digits you get. Kirby _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 In reply to this post by Kirby Urner > I've a couple times implemented the old manual algorithm for finding > square roots.  I might be able to dig those up for discussion.  The longer > it runs, the more digits you get. > > Kirby But instead, this steaming unoptimized octopus of a code specimen spits back the repeating digits for any positive integer, as needed to generate the ongoing continued fraction, for said integer's square root. def sqrtcf(n):     orig = n     denom = 1     addterm = 0     cflist = []     while True:         m = int(pow(n,0.5)) # <-- replace with function call         cflist.append(m)         if len(cflist)>1 and denom == 1:             break                 addterm = -(addterm - m*denom)         denom = (orig - addterm**2)/denom         n = ((pow(orig,0.5) + addterm)/denom)**2     return cflist IDLE 1.1       >>> from gonzo import sqrtcf >>> sqrtcf(19) [4, 2, 1, 3, 1, 2, 8] >>> sqrtcf(13) [3, 1, 1, 1, 1, 6] >>> sqrtcf(2) [1, 2] What's especially inelegant is that it uses pow, whereas with some Zelle-style numeric method, we could compute successive m's with more primitive primitives (e.g. Newton's method).  Then we'd have a bona fide square root generator that didn't use any built-in square root generator. The only remaining piece is to feed the repeating lists, e.g. [4, 2, 1, 3, 1, 2, 8] in the case of sqrt(19), to a continued fraction evaluator.  I've recently shared a recursive one, based on building a rational number class and using its objects.  However, a non-recursive cf algorithm exists, as Tim Peters mentioned way early in the archives of edu-sig (we played with it then, if memory serves). So.... (a) To get the square root of integer N, write a Zelle-style optimized approximater to get the biggest m = integer sqrt of N (i.e. m**2 < N < (m+1)**2). (b) call this in an implementation of the algorithm at this web page (with lots of check data): http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/cfINTRO.html (the algebraic algorithm). (c) use the returned list to feed a continued fractions evaluator.   The fun part here is we can use numerator/denominator syntax with open-ended precision integers, to like express sqrt of 19 as some humongous fraction (as many digits as memory will allow).  This lets us far surpass the floating point barrier. This is *not* a super-efficient way of getting 2nd roots, just a way that meanders through a lot of interesting math (continued fractions have a lot of cool features). Math through programming, we call it. Kirby _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig
Open this post in threaded view
|

## Re: Brute force solutions

 In reply to this post by Kirby Urner >The fun part here is we can use numerator/denominator syntax with open-ended >precision integers, to like express sqrt of 19 as some humongous fraction >(as many digits as memory will allow).  This lets us far surpass the >floating point barrier. For example, the sqrt of 19 is rougly: 745969084203762918506900171 6630770611758990188906918072 4013315460866431392624885605 5112125808098871177881508095 4010864598095 ---------------------------- 1711370448973571545640915466 3001505416992487326376156603 4301985589644920244770721090 4993017822174818974832607428 966608330904 (that's a numerator over a denominator). Here's the code behind it (still need to replace int(pow(x,0.5)) with a numerical method that doesn't do all the work to find an actual floating point sqrt -- overkill): """ gonzo.py """ from mathteach import cf2 # http://www.4dsolutions.net/ocn/python/mathteach.pydef sqrtcf(n):     orig = n     denom = 1     addterm = 0     cflist = []     while True:         m = int(pow(n,0.5)) # <-- replace with function call         cflist.append(m)         if len(cflist)>1 and denom == 1:             break         addterm = -(addterm - m*denom)         denom = (orig - addterm**2)/denom         n = ((pow(orig,0.5) + addterm)/denom)**2     return cflist def getsqrt(n,default=30):     thelist = sqrtcf(n)     while len(thelist)>> from gonzo import getsqrt >>> getsqrt(19) ... Kirby _______________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig-------------------------------------------------------------------- mail2web - Check your email from the web at http://mail2web.com/ . _______________________________________________ Edu-sig mailing list [hidden email] http://mail.python.org/mailman/listinfo/edu-sig