Mailman 3 September 2005 - Edu-sig

Rich Data Structures
by Kirby Urner 05 Oct '05

05 Oct '05

So I'm meditating on pedagogy again, having signed up for quite a few hours of presentation time, regarding Python etc. I've got a PSU class (high schoolers my target audience), and a volunteer gig with PPS, teaching math/CS to 8th graders (under a union member's supervision). For a long time, I've felt some frustration with published CS teaching texts because they don't put much textured information into their example data structures, by which I mean, I've never seen the Roman emperors, in chrono order, or the succession of rock bands played in by drummer X or guitarist Y. Not much about the history of trains, pre or post diesel. Or lets compile some data on Barbie's boy friends (just Ken?) -- or Buffy's (most of them vampires). Here's an opportunity to impart the humanities entirely tangentially to the engineering curriculum. As drivers of a new math/CS hybrid, I think we now realize that such opportunities for orthogonality should be prized, not sneezed at. Retaining student attention and interest, a precious commodity, is a worthy goal, and if a percentage of your student gain most from gazing absently at your wall posters, then at least make sure you've got some interesting wall posters (like, have you considered plasma?). Pile on opportunities for your lurker/auditors to jump to a higher bandwidth, even at the risk of pointing to content beyond your own specific scope (e.g. I'm no pro astronomer, but I'm happy and eager to share the experience with my students). So like here's what I mean (somewhat decayed fragment, imagine found in some archeological dig): moons = { 'Jupiter': ['Metis','Adrastea','Amalthea','Thebe', 'Leda','Ananke','Himalia','Carme', 'Lysithea','Pasiphae','Elara','Sinope', 'Io','Europa','Ganymede','Callisto'], 'Saturn': ['Pan','Atlas','Prometheus','Pandora', 'Epimetheus','Janus','Mimas','Enceladus', 'Tethys','Telesto','Calypso','Dione', 'Helene','Rhea','Titan','Hyperion', 'Iapetus','Phoebe'], 'Uranus': ['Cordelia','Ophelia','Bianca','Cressida', 'Desdemonia','Juliet','Portia','Rosalind', 'Belinda','Puck' There're a few goals here, not just to impress ourselves with the number of moons Jupiter's got, or Saturn. And pretty cool how much Shakespeare got mapped, at least in this particular namespace. We also want to demonstrate nesting, and here in this example I've not yet gone very deep: string-indexed lists of strings, basically. But of course we could go with things like lists of tuples of dictionaries of tuples of named functions (one could write some algorithm to randomly deepen nesting, always/only per the grammar of the language, e.g. per Python in this case). The push here is towards ultra-fluency when first learning the language, and then it's OK when adult-minded rust sets in, and one's data structures retreat to sane depths. That comes later, in the workaday world, when we've got weekend plans and want to get home and don't necessarily have time to appreciate some geek's damnably clever code. We acknowledge extreme fluency as a phase in the training, yet we don't insist these standards be met in the average workaday world. On the contrary, we insist on more a mellow programming style -- and that's both reasonable and right. Overly clever code is simply overly taxing to decipher and debug. Yet sometimes we need it and use it. We like our clowns to stay clever over time, true, however not every Python programmer should come to work wearing big shoes and a red nose. At least, not all at the same time. Vary your diet -- the usual middle way type teaching, as relevant in CS as in everyday living. Kirby

2 1

Re: [Edu-sig] Brute force solutions
by urnerk＠qwest.net 25 Sep '05

25 Sep '05

>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(a)python.org http://mail.python.org/mailman/listinfo/edu-sig -------------------------------------------------------------------- mail2web - Check your email from the web at http://mail2web.com/ .

2 1

Re: [Edu-sig] Brute force solutions
by urnerk＠qwest.net 24 Sep '05

24 Sep '05

> n = ((pow(orig,0.5) + addterm)/denom)**2 Hmmmm, 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/ .

1 0

Re: [Edu-sig] Brute force solutions
by Kirby Urner 24 Sep '05

24 Sep '05

> 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

1 0

Re: [Edu-sig] Brute force solutions
by David Handy 22 Sep '05

22 Sep '05

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/

3 3

Re: [Edu-sig] Brute force solutions
by Daniel Ajoy 22 Sep '05

22 Sep '05

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

2 1

Re: [Edu-sig] Brute force solutions
by David Handy 21 Sep '05

21 Sep '05

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 (10000% 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.000001), n = 10 timer1 = timeit.Timer(stmt='findphi(0.000001)', setup='from phi import findphi') t1 = timer1.timeit(number=n) print "time:", t1/n, "seconds" print "Faster method -- result:", findphi2(0.000001), timer2 = timeit.Timer(stmt='findphi2(0.000001)', 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.00000001), timer2 = timeit.Timer(stmt='findphi2(0.00000001)', setup='from phi import findphi2') n = 1000 t2 = timer2.timeit(number=n) print "time:", t2/n, "seconds" if __name__ == '__main__': test() # end-of-file david@arno2:~$ 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 david@arno2:~$ 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.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 > > [1] > http://mathforum.org/kb/message.jspa?messageID=3867841&tstart=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(a)python.org > http://mail.python.org/mailman/listinfo/edu-sig > -- David Handy Computer Programming is Fun! Beginning Computer Programming with Python http://www.handysoftware.com/cpif/ ----- End forwarded message ----- -- David Handy Computer Programming is Fun! Beginning Computer Programming with Python http://www.handysoftware.com/cpif/

3 3

Brute force solutions
by Kirby Urner 20 Sep '05

20 Sep '05

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.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 [1] http://mathforum.org/kb/message.jspa?messageID=3867841&tstart=0 [2] http://altreligion.about.com/library/glossary/symbols/bldefswiccasymbols.htm PS: happy birthday Dawn Wicca (9/20/2005)

1 0

Re: [Edu-sig] quantum instance
by ajsiegel＠optonline.net 20 Sep '05

20 Sep '05

----- Original Message ----- From: Kirby Urner <urnerk(a)qwest.net> Date: Tuesday, September 20, 2005 12:34 pm Subject: RE: [Edu-sig] quantum instance > > I'm in no way persuaded that you have some special insight into > what the > property feature is "really" intended to provide, based on some > supposedlyclose reading of Guido's examples. It's there for the > same reason it's in > other OO languages, to help coders build and maintain APIs that > make sense > to their users. You win. But only in the sense that you get the last word. Even *I'm* tired of the thread. Let's move on. Art

2 1

Re: [Edu-sig] quantum instance
by Arthur 20 Sep '05

20 Sep '05

> -----Original Message----- > From: Kirby Urner [mailto:urnerk@qwest.net] > Sent: Monday, September 19, 2005 4:09 PM > To: ajsiegel(a)optonline.net > Cc: edu-sig(a)python.org; 'John Zelle' > Subject: RE: [Edu-sig] quantum instance > > > You want to have your intuition as to someone else's intuition control - > > in a scientific setting. We are at unscience**2 - before we get > started. > > > > No, we're having a meeting of the minds, me and the client. I go through > iterations of the API, and the client lets me know if I'm on the right > track. You make it sound like it's all guess work. It ain't. Of course you are not representing that you are talking about an actual Python Application Programmers Interface that you have written for actual surgeons who intend to use it - in reality - as an Application Programmers Interface. You are talking about something else, applying a few decorators to a few property functions, which then entitle you to talk about it as if you were - in reality. Speculating along those lines of course makes me an obnoxious bastard - but we already knew that. Art

2 1