[Edu-sig] Brute force solutions

[John Zelle]

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
john.zelle at wartburg.edu          (319) 352-8360