[Edu-sig] Brute force solutions
John Zelle
john.zelle at wartburg.edu
Wed Sep 21 23:52:23 CEST 2005
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
More information about the Edu-sig
mailing list