Re: [Edu-sig] Brute force solutions
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.py 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 def getsqrt(n,default=30): thelist = sqrtcf(n) while len(thelist)default: thelist += thelist[1:] thelist = thelist[:default] return cf2(thelist * 10) from gonzo import getsqrt getsqrt(19) ... Kirby ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig mail2web - Check your email from the web at http://mail2web.com/ . ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Brute force solutions
n = ((pow(orig,0.5) + addterm)/denom)**2 H, this may be the Achilles heal of my project, to not use any sqrt finder in the process of finding a sqrt using continued fractions. Back to the drawing board? Kirby mail2web - Check your email from the web at http://mail2web.com/ . ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Brute force solutions
[EMAIL PROTECTED] wrote: 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. OK, here we go: def test_sqrt(numerator, denominator, trial): '''True iff trial (a num,den pair) over-estimates the sqrt(n/d)''' root_n, root_d = trial # return numerator / denominator = root_n ** 2 / root_d ** 2 return root_d ** 2 * numerator = root_n ** 2 * denominator # since we don't have 2.5 yet, here's a version of partial: def partial(function, *args): '''Simple no-kwargs version of partial''' def andthen(*final_args): return function(*(args + final_args)) return andthen def farey_trials(tester): '''Binary search for fraction. value must be between 0 and +Inf tester((num, den)) returns True if fract is high, False if Low ''' low_n, low_d = low = 0, 1# 0/1 = 0 .. high_n, high_d = high = 1, 0 # 1/0 = Infinity while True: mediant_n = low_n + high_n mediant_d = low_d + high_d mediant = mediant_n, mediant_d yield mediant if tester(mediant): low_n, low_d = low = mediant else: high_n, high_d = high = mediant # Now here is a cute reporter that relies on another trick: # n -n == n only if n is either 0 or a power of 2. for n, fraction in enumerate(farey_trials(partial(test_sqrt, 19, 1))): if n -n == n: # report increasingly rarely print n, fraction if n 4096: break -- Scott David Daniels [EMAIL PROTECTED] ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Brute force solutions
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 ScienceWaverly, IA [EMAIL PROTECTED] (319) 352-8360 ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Brute force solutions
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 Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Brute force solutions
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Daniel Ajoy Sent: Thursday, September 22, 2005 10:07 AM To: edu-sig@python.org 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.html That 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 Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Brute force solutions
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 Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
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 (1% 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.01), n = 10 timer1 = timeit.Timer(stmt='findphi(0.01)', setup='from phi import findphi') t1 = timer1.timeit(number=n) print time:, t1/n, seconds print Faster method -- result:, findphi2(0.01), timer2 = timeit.Timer(stmt='findphi2(0.01)', 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.0001), timer2 = timeit.Timer(stmt='findphi2(0.0001)', setup='from phi import findphi2') n = 1000 t2 = timer2.timeit(number=n) print time:, t2/n, seconds if __name__ == '__main__': test() # end-of-file [EMAIL PROTECTED]:~$ 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 [EMAIL PROTECTED]:~$ 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.01) 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
Re: [Edu-sig] Brute force solutions
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 Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] 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 100x 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 Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
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/ ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] 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 ScienceWaverly, IA [EMAIL PROTECTED] (319) 352-8360 ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
[Edu-sig] Brute force solutions
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.01) 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=3867841tstart=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
