Re: [Edu-sig] Brute force solutions
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/
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@wartburg.edu (319) 352-8360
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 john.zelle@wartburg.edu (319) 352-8360
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
participants (3)
-
David Handy -
John Zelle -
Kirby Urner