Candidates: "Must include" would be like an intersection of many sets in a Venn Diagram, where we all gave our favorite movies and a very few, such as 'Bagdad Cafe' or 'Wendy and Lucy' or... proved common to us all (no suggesting those'd be -- just personal favorites). In this category, three candidates come to mind right away: Guido's for the gcd: def gcd(a,b): while b: a, b = b, a % b return a Then two generics we've all seen many times, generators for Pascal's Triangle and Fibonacci Sequence respectively: def pascal(): """ Pascal's Triangle ** """ row = [1] while True: yield row row = [ a + b for a, b in zip( [0] + row, row + [0] ) ] and: def fibonacci(a=0, b=1): while True: yield a a, b = a + b, a IDLE 1.2.1
from first_steps import * gcd(51, 34) 17 g = pascal() g.next() [1] g.next() [1, 1] g.next() [1, 2, 1] g.next() [1, 3, 3, 1] f = fibonacci() f.next() 0 f.next() 1 f.next() 1 f.next() 2 f.next() 3 f.next() 5
Check 'em out in kid-friendly Akbar font (derives from Matt Groening of Simpsons fame): http://www.wobblymusic.com/groening/akbar.html http://www.flickr.com/photos/17157315@N00/3197681869/sizes/o/ ( feel free to link or embed in your gnu math website ) I'm not claiming these are the only ways to write these. I do think it's a feature, not a bug, that I'm eschewing recursion in all three. Will get to that later, maybe in Scheme just like the Scheme folks would prefer (big lambda instead of little, which latter I saw put to good use at PPUG last night, well attended (about 30)). http://mybizmo.blogspot.com/2009/01/ppug-2009113.html Rationale: In terms of curriculum, these belong together for a host of reasons, not just that we want students to use generators to explore On-Line Encyclopedia of Integer Sequences type sequences. Pascal's Triangle actually contains Fibonaccis along successive diagonals but more important we're laying the foundation for figurate and polyhedral ball packings ala The Book of Numbers, Synergetics, other late 20th century distillations (of math and philosophy respectively). Fibonaccis converge to Phi i.e. (1 + math.sqrt(5) )/2. gcd will be critical in our relative primality checks, leading up to Euler's Theorem thence RSA, per the review below (a literature search from my cube at CubeSpace on Grand Ave): http://cubespacepdx.com/ http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0 http://www.flickr.com/photos/17157315@N00/3195148912/ Remember, every browser has SSL, using RSA for handshaking, so it's not like we're giving them irrelevant info. Number theory goes into every DirecTV box thanks to NDS, other companies making use of this powerful public method.^^ You should understand, as a supermarket manager or museum administrator, something about encryption, security, what's tough to the crack and what's not. The battle to make RSA public property was hard won, so it's not like our public school system is eager to surrender it back to obscurity. Student geek wannabes perk up at the thought of getting how this works, not hard to show in Javascript and/or Python. Makes school more interesting, to be getting the low-down. By the same token, corporate trainers not having the luxury of doing the whole nine yards in our revamped grades 8-12, have the ability to excerpt specific juicy parts for the walk of life they're in. Our maths have a biological flavor, thanks to Spore, thanks to Sims. We do a Biotum class almost right away ("Hello World" is maybe part of it's __repr__ ?). I'm definitely tilting this towards the health professions, just as I did our First Person Physics campaign (Dr. Bob Fuller or leader, University of Nebraska emeritus). The reason for using bizarre charactersets in the group theory piece is we want to get their attention off numbers and onto something more generic, could be pictograms, icons, pictures of vegetables... Feedback welcome, Kirby ** http://www.flickr.com/photos/17157315@N00/3198473850/sizes/l/ ^^ http://www.allbusiness.com/media-telecommunications/telecommunications/59235...
I like this. I think another 'must include' for math classes would be list comprehension syntax. Not an algorithm in itself, but an important way of thinking. It's what we try to get them to do using set notation, but in math classes it seems simply like a formality for describing domains, nothing more. In Python, it DOES stuff. - Michel 2009/1/14 kirby urner <kirby.urner@gmail.com>
Candidates:
"Must include" would be like an intersection of many sets in a Venn Diagram, where we all gave our favorite movies and a very few, such as 'Bagdad Cafe' or 'Wendy and Lucy' or... proved common to us all (no suggesting those'd be -- just personal favorites).
In this category, three candidates come to mind right away:
Guido's for the gcd:
def gcd(a,b): while b: a, b = b, a % b return a
Then two generics we've all seen many times, generators for Pascal's Triangle and Fibonacci Sequence respectively:
def pascal(): """ Pascal's Triangle ** """ row = [1] while True: yield row row = [ a + b for a, b in zip( [0] + row, row + [0] ) ]
and:
def fibonacci(a=0, b=1): while True: yield a a, b = a + b, a
IDLE 1.2.1
from first_steps import * gcd(51, 34) 17 g = pascal() g.next() [1] g.next() [1, 1] g.next() [1, 2, 1] g.next() [1, 3, 3, 1] f = fibonacci() f.next() 0 f.next() 1 f.next() 1 f.next() 2 f.next() 3 f.next() 5
Check 'em out in kid-friendly Akbar font (derives from Matt Groening of Simpsons fame): http://www.wobblymusic.com/groening/akbar.html
http://www.flickr.com/photos/17157315@N00/3197681869/sizes/o/
( feel free to link or embed in your gnu math website )
I'm not claiming these are the only ways to write these. I do think it's a feature, not a bug, that I'm eschewing recursion in all three. Will get to that later, maybe in Scheme just like the Scheme folks would prefer (big lambda instead of little, which latter I saw put to good use at PPUG last night, well attended (about 30)).
http://mybizmo.blogspot.com/2009/01/ppug-2009113.html
Rationale:
In terms of curriculum, these belong together for a host of reasons, not just that we want students to use generators to explore On-Line Encyclopedia of Integer Sequences type sequences. Pascal's Triangle actually contains Fibonaccis along successive diagonals but more important we're laying the foundation for figurate and polyhedral ball packings ala The Book of Numbers, Synergetics, other late 20th century distillations (of math and philosophy respectively). Fibonaccis converge to Phi i.e. (1 + math.sqrt(5) )/2. gcd will be critical in our relative primality checks, leading up to Euler's Theorem thence RSA, per the review below (a literature search from my cube at CubeSpace on Grand Ave):
http://cubespacepdx.com/ http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0 http://www.flickr.com/photos/17157315@N00/3195148912/
Remember, every browser has SSL, using RSA for handshaking, so it's not like we're giving them irrelevant info. Number theory goes into every DirecTV box thanks to NDS, other companies making use of this powerful public method.^^
You should understand, as a supermarket manager or museum administrator, something about encryption, security, what's tough to the crack and what's not. The battle to make RSA public property was hard won, so it's not like our public school system is eager to surrender it back to obscurity. Student geek wannabes perk up at the thought of getting how this works, not hard to show in Javascript and/or Python. Makes school more interesting, to be getting the low-down.
By the same token, corporate trainers not having the luxury of doing the whole nine yards in our revamped grades 8-12, have the ability to excerpt specific juicy parts for the walk of life they're in.
Our maths have a biological flavor, thanks to Spore, thanks to Sims. We do a Biotum class almost right away ("Hello World" is maybe part of it's __repr__ ?). I'm definitely tilting this towards the health professions, just as I did our First Person Physics campaign (Dr. Bob Fuller or leader, University of Nebraska emeritus).
The reason for using bizarre charactersets in the group theory piece is we want to get their attention off numbers and onto something more generic, could be pictograms, icons, pictures of vegetables...
Feedback welcome,
Kirby
** http://www.flickr.com/photos/17157315@N00/3198473850/sizes/l/ ^^ http://www.allbusiness.com/media-telecommunications/telecommunications/59235...
_______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Yes, note that my Pascal's includes it, with an embedded zip. Another place list comprehension comes up is in our naive definition of totatives as: def totative(n): return [ t for t in range(1, n) if gcd(t, n) == 1] i.e. all 0 < t < n such that (t, n) have no factors in common (are relatively prime). Then our totient function is simply the len of this list, giving us a quick way to assert (test) Euler's theorem: b ** totient(d) % d == 1 where gcd(b,d)==1. There's an easy enough proof in 'Number' by Midhat Gazale, a must have on our syllabus (I'm suggesting). Kirby On Thu, Jan 15, 2009 at 6:35 AM, michel paul <mpaul213@gmail.com> wrote:
I like this.
I think another 'must include' for math classes would be list comprehension syntax. Not an algorithm in itself, but an important way of thinking. It's what we try to get them to do using set notation, but in math classes it seems simply like a formality for describing domains, nothing more. In Python, it DOES stuff.
- Michel
2009/1/14 kirby urner <kirby.urner@gmail.com>
Candidates:
"Must include" would be like an intersection of many sets in a Venn Diagram, where we all gave our favorite movies and a very few, such as 'Bagdad Cafe' or 'Wendy and Lucy' or... proved common to us all (no suggesting those'd be -- just personal favorites).
In this category, three candidates come to mind right away:
Guido's for the gcd:
def gcd(a,b): while b: a, b = b, a % b return a
Then two generics we've all seen many times, generators for Pascal's Triangle and Fibonacci Sequence respectively:
def pascal(): """ Pascal's Triangle ** """ row = [1] while True: yield row row = [ a + b for a, b in zip( [0] + row, row + [0] ) ]
and:
def fibonacci(a=0, b=1): while True: yield a a, b = a + b, a
IDLE 1.2.1
from first_steps import * gcd(51, 34) 17 g = pascal() g.next() [1] g.next() [1, 1] g.next() [1, 2, 1] g.next() [1, 3, 3, 1] f = fibonacci() f.next() 0 f.next() 1 f.next() 1 f.next() 2 f.next() 3 f.next() 5
Check 'em out in kid-friendly Akbar font (derives from Matt Groening of Simpsons fame): http://www.wobblymusic.com/groening/akbar.html
http://www.flickr.com/photos/17157315@N00/3197681869/sizes/o/
( feel free to link or embed in your gnu math website )
I'm not claiming these are the only ways to write these. I do think it's a feature, not a bug, that I'm eschewing recursion in all three. Will get to that later, maybe in Scheme just like the Scheme folks would prefer (big lambda instead of little, which latter I saw put to good use at PPUG last night, well attended (about 30)).
http://mybizmo.blogspot.com/2009/01/ppug-2009113.html
Rationale:
In terms of curriculum, these belong together for a host of reasons, not just that we want students to use generators to explore On-Line Encyclopedia of Integer Sequences type sequences. Pascal's Triangle actually contains Fibonaccis along successive diagonals but more important we're laying the foundation for figurate and polyhedral ball packings ala The Book of Numbers, Synergetics, other late 20th century distillations (of math and philosophy respectively). Fibonaccis converge to Phi i.e. (1 + math.sqrt(5) )/2. gcd will be critical in our relative primality checks, leading up to Euler's Theorem thence RSA, per the review below (a literature search from my cube at CubeSpace on Grand Ave):
http://cubespacepdx.com/ http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0 http://www.flickr.com/photos/17157315@N00/3195148912/
Remember, every browser has SSL, using RSA for handshaking, so it's not like we're giving them irrelevant info. Number theory goes into every DirecTV box thanks to NDS, other companies making use of this powerful public method.^^
You should understand, as a supermarket manager or museum administrator, something about encryption, security, what's tough to the crack and what's not. The battle to make RSA public property was hard won, so it's not like our public school system is eager to surrender it back to obscurity. Student geek wannabes perk up at the thought of getting how this works, not hard to show in Javascript and/or Python. Makes school more interesting, to be getting the low-down.
By the same token, corporate trainers not having the luxury of doing the whole nine yards in our revamped grades 8-12, have the ability to excerpt specific juicy parts for the walk of life they're in.
Our maths have a biological flavor, thanks to Spore, thanks to Sims. We do a Biotum class almost right away ("Hello World" is maybe part of it's __repr__ ?). I'm definitely tilting this towards the health professions, just as I did our First Person Physics campaign (Dr. Bob Fuller or leader, University of Nebraska emeritus).
The reason for using bizarre charactersets in the group theory piece is we want to get their attention off numbers and onto something more generic, could be pictograms, icons, pictures of vegetables...
Feedback welcome,
Kirby
** http://www.flickr.com/photos/17157315@N00/3198473850/sizes/l/ ^^ http://www.allbusiness.com/media-telecommunications/telecommunications/59235...
_______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
I'd like to suggest, that some sort of sieve could be included, for instance as a non very fancy example something like def primes(n): s = set(range(3,n+1,2)) if n >= 2: s.add(2) m=3 while m * m < n: s.difference_update(range(m*m, n+1, 2*m)) m += 2 while m not in s: m += 2 return sorted(s) (as a starting point), or something similar, a bit beautified or perhaps you know some different more concise solution ... An even more compact albeit slightly slower version would be: def primes(n): s = set(range(3,n+1,2)) for m in range(3, int(n**.5)+1, 2): s.difference_update(range(m*m, n+1, 2*m)) return [2]*(2<=n) + sorted(s) Or something in between. These are imho nice applications of the set type. Gregor kirby urner schrieb:
Yes, note that my Pascal's includes it, with an embedded zip. Another place list comprehension comes up is in our naive definition of totatives as:
def totative(n): return [ t for t in range(1, n) if gcd(t, n) == 1]
i.e. all 0 < t < n such that (t, n) have no factors in common (are relatively prime). Then our totient function is simply the len of this list, giving us a quick way to assert (test) Euler's theorem: b ** totient(d) % d == 1 where gcd(b,d)==1. There's an easy enough proof in 'Number' by Midhat Gazale, a must have on our syllabus (I'm suggesting).
Kirby
On Thu, Jan 15, 2009 at 6:35 AM, michel paul <mpaul213@gmail.com <mailto:mpaul213@gmail.com>> wrote:
I like this.
I think another 'must include' for math classes would be list comprehension syntax. Not an algorithm in itself, but an important way of thinking. It's what we try to get them to do using set notation, but in math classes it seems simply like a formality for describing domains, nothing more. In Python, it DOES stuff.
- Michel
2009/1/14 kirby urner <kirby.urner@gmail.com <mailto:kirby.urner@gmail.com>>
Candidates:
"Must include" would be like an intersection of many sets in a Venn Diagram, where we all gave our favorite movies and a very few, such as 'Bagdad Cafe' or 'Wendy and Lucy' or... proved common to us all (no suggesting those'd be -- just personal favorites).
In this category, three candidates come to mind right away:
Guido's for the gcd:
def gcd(a,b): while b: a, b = b, a % b return a
Then two generics we've all seen many times, generators for Pascal's Triangle and Fibonacci Sequence respectively:
def pascal(): """ Pascal's Triangle ** """ row = [1] while True: yield row row = [ a + b for a, b in zip( [0] + row, row + [0] ) ]
and:
def fibonacci(a=0, b=1): while True: yield a a, b = a + b, a
IDLE 1.2.1 >>> from first_steps import * >>> gcd(51, 34) 17 >>> g = pascal() >>> g.next() [1] >>> g.next() [1, 1] >>> g.next() [1, 2, 1] >>> g.next() [1, 3, 3, 1] >>> f = fibonacci() >>> f.next() 0 >>> f.next() 1 >>> f.next() 1 >>> f.next() 2 >>> f.next() 3 >>> f.next() 5
Check 'em out in kid-friendly Akbar font (derives from Matt Groening of Simpsons fame): http://www.wobblymusic.com/groening/akbar.html
http://www.flickr.com/photos/17157315@N00/3197681869/sizes/o/
( feel free to link or embed in your gnu math website )
I'm not claiming these are the only ways to write these. I do think it's a feature, not a bug, that I'm eschewing recursion in all three. Will get to that later, maybe in Scheme just like the Scheme folks would prefer (big lambda instead of little, which latter I saw put to good use at PPUG last night, well attended (about 30)).
http://mybizmo.blogspot.com/2009/01/ppug-2009113.html
Rationale:
In terms of curriculum, these belong together for a host of reasons, not just that we want students to use generators to explore On-Line Encyclopedia of Integer Sequences type sequences. Pascal's Triangle actually contains Fibonaccis along successive diagonals but more important we're laying the foundation for figurate and polyhedral ball packings ala The Book of Numbers, Synergetics, other late 20th century distillations (of math and philosophy respectively). Fibonaccis converge to Phi i.e. (1 + math.sqrt(5) )/2. gcd will be critical in our relative primality checks, leading up to Euler's Theorem thence RSA, per the review below (a literature search from my cube at CubeSpace on Grand Ave):
http://cubespacepdx.com/ http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0 <http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0> http://www.flickr.com/photos/17157315@N00/3195148912/
Remember, every browser has SSL, using RSA for handshaking, so it's not like we're giving them irrelevant info. Number theory goes into every DirecTV box thanks to NDS, other companies making use of this powerful public method.^^
You should understand, as a supermarket manager or museum administrator, something about encryption, security, what's tough to the crack and what's not. The battle to make RSA public property was hard won, so it's not like our public school system is eager to surrender it back to obscurity. Student geek wannabes perk up at the thought of getting how this works, not hard to show in Javascript and/or Python. Makes school more interesting, to be getting the low-down.
By the same token, corporate trainers not having the luxury of doing the whole nine yards in our revamped grades 8-12, have the ability to excerpt specific juicy parts for the walk of life they're in.
Our maths have a biological flavor, thanks to Spore, thanks to Sims. We do a Biotum class almost right away ("Hello World" is maybe part of it's __repr__ ?). I'm definitely tilting this towards the health professions, just as I did our First Person Physics campaign (Dr. Bob Fuller or leader, University of Nebraska emeritus).
The reason for using bizarre charactersets in the group theory piece is we want to get their attention off numbers and onto something more generic, could be pictograms, icons, pictures of vegetables...
Feedback welcome,
Kirby
** http://www.flickr.com/photos/17157315@N00/3198473850/sizes/l/ ^^ http://www.allbusiness.com/media-telecommunications/telecommunications/59235...
_______________________________________________ Edu-sig mailing list Edu-sig@python.org <mailto:Edu-sig@python.org> http://mail.python.org/mailman/listinfo/edu-sig
------------------------------------------------------------------------
_______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Yes thank you I completely agree. A stash of sieves, plus data mine this very archive for our earlier work on this topic. My only suggestion is you include a generator version e.g.: Using Python 3:
g = Primes() next(g) -1 next(g) 2 next(g) 3 next(g) 5
etc. Generators are cool for any infinite sequence, be it convergent, divergent, oscillatory, or chaotic (finite too). That's Conway's thing about -1 being prime, feel free to ignore (or not -- see link). Bottom line is I'm encouraging us to have RSA in the final mix for Portland Public (e.g. LEP High and such), meaning we need: (a) Miller-Rabin or one of those for highly probably prime numbers (Jython gives direct access to math.BigInteger.probablePrime woo hoo! or just use my http://markmail.org/message/v43sry4svsvk5nli -- lots of help from Tim Peters which I'm still happy about) and (b) Euclid's extended algorithm (Guido's for the GCD being non-extended). EEA has other uses, Diophantine equations, continued fractions... Cut the Knot a good web site. In other words, in addition to a sieve, we'd like some callables to test and return (probable) primes (we're talking hundreds of digits in RSA world). Kirby Da links! http://www.cut-the-knot.org/blue/extension.shtml http://www.youtube.com/watch?v=4GxP9EVKCjo (for engineers) http://mathforum.org/library/drmath/view/54241.html http://www.informationsuebertragung.ch/indexAlgorithmen.html http://eprints.iisc.ernet.in/11336/ http://mathforum.org/kb/message.jspa?messageID=1093178&tstart=0 (conway.primes) http://mlblog.osdir.com/python.education/2002-08/msg00084.shtml (clever marketing) http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.html#probablePr...) On Thu, Jan 15, 2009 at 5:33 PM, Gregor Lingl <gregor.lingl@aon.at> wrote:
I'd like to suggest, that some sort of sieve could be included, for instance as a non very fancy example something like
def primes(n): s = set(range(3,n+1,2)) if n >= 2: s.add(2) m=3 while m * m < n: s.difference_update(range(m*m, n+1, 2*m)) m += 2 while m not in s: m += 2 return sorted(s)
(as a starting point), or something similar, a bit beautified or perhaps you know some different more concise solution ...
An even more compact albeit slightly slower version would be:
def primes(n): s = set(range(3,n+1,2)) for m in range(3, int(n**.5)+1, 2): s.difference_update(range(m*m, n+1, 2*m)) return [2]*(2<=n) + sorted(s)
Or something in between. These are imho nice applications of the set type.
Gregor
kirby urner schrieb:
Yes, note that my Pascal's includes it, with an embedded zip. Another place list comprehension comes up is in our naive definition of totatives as:
def totative(n): return [ t for t in range(1, n) if gcd(t, n) == 1]
i.e. all 0 < t < n such that (t, n) have no factors in common (are relatively prime). Then our totient function is simply the len of this list, giving us a quick way to assert (test) Euler's theorem: b ** totient(d) % d == 1 where gcd(b,d)==1. There's an easy enough proof in 'Number' by Midhat Gazale, a must have on our syllabus (I'm suggesting).
Kirby
On Thu, Jan 15, 2009 at 6:35 AM, michel paul <mpaul213@gmail.com <mailto:mpaul213@gmail.com>> wrote:
I like this.
I think another 'must include' for math classes would be list comprehension syntax. Not an algorithm in itself, but an important way of thinking. It's what we try to get them to do using set notation, but in math classes it seems simply like a formality for describing domains, nothing more. In Python, it DOES stuff.
- Michel
2009/1/14 kirby urner <kirby.urner@gmail.com <mailto:kirby.urner@gmail.com>>
Candidates:
"Must include" would be like an intersection of many sets in a Venn Diagram, where we all gave our favorite movies and a very few, such as 'Bagdad Cafe' or 'Wendy and Lucy' or... proved common to us all (no suggesting those'd be -- just personal favorites).
In this category, three candidates come to mind right away:
Guido's for the gcd:
def gcd(a,b): while b: a, b = b, a % b return a
Then two generics we've all seen many times, generators for Pascal's Triangle and Fibonacci Sequence respectively:
def pascal(): """ Pascal's Triangle ** """ row = [1] while True: yield row row = [ a + b for a, b in zip( [0] + row, row + [0] ) ]
and:
def fibonacci(a=0, b=1): while True: yield a a, b = a + b, a
IDLE 1.2.1 >>> from first_steps import * >>> gcd(51, 34) 17 >>> g = pascal() >>> g.next() [1] >>> g.next() [1, 1] >>> g.next() [1, 2, 1] >>> g.next() [1, 3, 3, 1] >>> f = fibonacci() >>> f.next() 0 >>> f.next() 1 >>> f.next() 1 >>> f.next() 2 >>> f.next() 3 >>> f.next() 5
Check 'em out in kid-friendly Akbar font (derives from Matt Groening of Simpsons fame): http://www.wobblymusic.com/groening/akbar.html
http://www.flickr.com/photos/17157315@N00/3197681869/sizes/o/
( feel free to link or embed in your gnu math website )
I'm not claiming these are the only ways to write these. I do think it's a feature, not a bug, that I'm eschewing recursion in all three. Will get to that later, maybe in Scheme just like the Scheme folks would prefer (big lambda instead of little, which latter I saw put to good use at PPUG last night, well attended (about 30)).
http://mybizmo.blogspot.com/2009/01/ppug-2009113.html
Rationale:
In terms of curriculum, these belong together for a host of reasons, not just that we want students to use generators to explore On-Line Encyclopedia of Integer Sequences type sequences. Pascal's Triangle actually contains Fibonaccis along successive diagonals but more important we're laying the foundation for figurate and polyhedral ball packings ala The Book of Numbers, Synergetics, other late 20th century distillations (of math and philosophy respectively). Fibonaccis converge to Phi i.e. (1 + math.sqrt(5) )/2. gcd will be critical in our relative primality checks, leading up to Euler's Theorem thence RSA, per the review below (a literature search from my cube at CubeSpace on Grand Ave):
http://cubespacepdx.com/ http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0 <http://mathforum.org/kb/thread.jspa?threadID=1885121&tstart=0> http://www.flickr.com/photos/17157315@N00/3195148912/
Remember, every browser has SSL, using RSA for handshaking, so it's not like we're giving them irrelevant info. Number theory goes into every DirecTV box thanks to NDS, other companies making use of this powerful public method.^^
You should understand, as a supermarket manager or museum administrator, something about encryption, security, what's tough to the crack and what's not. The battle to make RSA public property was hard won, so it's not like our public school system is eager to surrender it back to obscurity. Student geek wannabes perk up at the thought of getting how this works, not hard to show in Javascript and/or Python. Makes school more interesting, to be getting the low-down.
By the same token, corporate trainers not having the luxury of doing the whole nine yards in our revamped grades 8-12, have the ability to excerpt specific juicy parts for the walk of life they're in. Our maths have a biological flavor, thanks to Spore, thanks to Sims. We do a Biotum class almost right away ("Hello World" is maybe part of it's __repr__ ?). I'm definitely tilting this towards the health professions, just as I did our First Person Physics campaign (Dr. Bob Fuller or leader, University of Nebraska emeritus).
The reason for using bizarre charactersets in the group theory piece is we want to get their attention off numbers and onto something more generic, could be pictograms, icons, pictures of vegetables...
Feedback welcome,
Kirby
** http://www.flickr.com/photos/17157315@N00/3198473850/sizes/l/ ^^
http://www.allbusiness.com/media-telecommunications/telecommunications/59235...
_______________________________________________ Edu-sig mailing list Edu-sig@python.org <mailto:Edu-sig@python.org> http://mail.python.org/mailman/listinfo/edu-sig
------------------------------------------------------------------------
_______________________________________________ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
kirby urner schrieb:
Yes thank you I completely agree. A stash of sieves, plus data mine this very archive for our earlier work on this topic.
My only suggestion is you include a generator version e.g.:
At first this seems an attractive idea, but in my opinion the idea of sieves is fairly antagonistic to that of generators. A sieve is used to eliminate from a given set elements that have not some desired property, while generators (ideally) create objects, one at atime, with that desired property. Drastically: you cannot sieve at first all even numbers from an infinite set or sequence. For educational purposes I'd prefer examples that display a single concept in a small and simple way. :-* A prime number generater based on some different algorithm of course may be interesting and useful. To continue work in this area one (or at least me) has to have some criteria to judge the solutions. Clearly it was advantageous if there was some consensus about these criteria in the community. There should be some criteria concerning (a) the choice of problems and themes, e.g. to prefer small problems that expose a single idea - or rather not ... etc., as well as some (b) code related criteria, like clarity, conciseness, efficiency, beauty (!) etc., ranked according to their priorities. Once I had the following idea: there are so many renowned pythonistas in the developers community, many of them also interested to promote Python in the educational area (see for instance the protagonists in Jeffrey Elkners "Introducing Python"). How about to ask them to make a personal donation to the educators and learners: a piece of code, 10 to 12 lines at most, that they individually consider to show most convincingly the power or the beauty of programming with Python - or the fun they have with it. Young people like role models ;-) Regrettably I didn't persue that idea further. What do you think of it. Ok, the days of the early pioneers are over, but perhaps it's still worth a try? Regards, Gregor
Using Python 3:
g = Primes() next(g)
-1
next(g)
....
On Sat, Jan 17, 2009 at 5:40 PM, Gregor Lingl <gregor.lingl@aon.at> wrote:
kirby urner schrieb:
Yes thank you I completely agree. A stash of sieves, plus data mine this very archive for our earlier work on this topic.
My only suggestion is you include a generator version e.g.:
At first this seems an attractive idea, but in my opinion the idea of sieves is fairly antagonistic to that of generators. A sieve is used to eliminate from a given set elements that have not some desired property, while generators (ideally) create objects, one at atime, with that desired property. Drastically: you cannot sieve at first all even numbers from an infinite set or sequence. For educational purposes I'd prefer examples that display a single concept in a small and simple way. :-* A prime number generater based on some different algorithm of course may be interesting and useful.
Yes sir! Excellent clarification. The goal is to have a worthy generator that always gives the next prime. "Trial by division" is the simplest approach I can think of...
def primes(): sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway yield sofar[0] # get these out of the way yield sofar[1] # the only even prime yield sofar[2] # and then 3 candidate = 5 # we'll increment from here on while True: # go forever for factor in sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? yield candidate # woo hoo! sofar.append(candidate) # keep the gold break # onward! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please
g = primes() next(g) -1 next(g) 2 next(g) 3 next(g) 5 next(g) 7 next(g) 11 next(g) 13 next(g) 17 next(g) 19 next(g) 23 next(g) 29 next(g) 31 next(g) 37 next(g) 41
I think you're correct that the sieve best works with a pre-specified finite domain: sieve it completely, using divisors < math.sqrt(len(domain)) then iterate over it maybe, but the array is already populated, taking up memory. The above generator, in contrast, gradually takes up more memory (shows what generators are good for then: saving state between cycles).
To continue work in this area one (or at least me) has to have some criteria to judge the solutions. Clearly it was advantageous if there was some consensus about these criteria in the community.
Fortunately, we have hundreds of years of math pedagogy, so in terms of avoiding quarrels, start with what's already on the books are "must have" and just render it Pythonically. So, for example, every pre-college math curriculum I'm aware of makes the distinction between prime and composite numbers. On the other hand, few include the Fermat test or Fermat's Little Theorem, don't have RSA as a goal. So whereas generators for primes, fibonaccis, pascal's triangle, would seem non-controversial, anything having to do with Fermat's Little Theorem would seem an uphill battle, especially without buy in on the RSA bit. What makes a lot of this stuff more accessible than before is we have the ability to work with large numbers of digits. Both text books and calculators tend to crap out at more that 15 significant figures. Not so in Python or any significantly endowed language. 2 ** 10000 is no problem for us, is for the paper and pencil crowd, or the TI crowd (both pitiable). I don't think there's a way to avoid quarrels. People have different leadings, throw their hats in the ring, and we see what synergies develop. My goal is to keep the process open and participatory, not to close it down. The sight of people debating is far less disturbing than the sight of everyone in lockstep (the Borg).
There should be some criteria concerning (a) the choice of problems and themes, e.g. to prefer small problems that expose a single idea - or rather not ... etc., as well as some (b) code related criteria, like clarity, conciseness, efficiency, beauty (!) etc., ranked according to their priorities.
This will be up to each professional teacher in whatever walk of life -- to judge what to include and what to exclude. Each teacher will find her or himself in agreement with some, disagreement with others, over what to include. Twas ever thus. What to avoid, in my book, is a restrictive environment which takes a one size fits all approach and dictates to all teachers how it must be, removing much individual freedom. Reduction in biodiversity is dangerous in my estimation. That's why I fight against "national curriculum" ideologues on the Math Forum, other places.
Once I had the following idea: there are so many renowned pythonistas in the developers community, many of them also interested to promote Python in the educational area (see for instance the protagonists in Jeffrey Elkners "Introducing Python"). How about to ask them to make a personal donation to the educators and learners: a piece of code, 10 to 12 lines at most, that they individually consider to show most convincingly the power or the beauty of programming with Python - or the fun they have with it. Young people like role models ;-)
That's a fun idea. Another approach is to start some schools in which Python is defacto included as an important tool in the math curriculum, and compete with other schools that make different choices, see how that goes. Don't try to "convince the world" before starting your experiment. You need no one's permission to take the initiative. Individuals make all the difference in this world, alone and in groups.
Regrettably I didn't persue that idea further. What do you think of it. Ok, the days of the early pioneers are over, but perhaps it's still worth a try?
I think the first generation of Pythoneers, counting myself as one of them, should be collecting momentos and souvenirs, as soon enough our generation will no longer be heard from, in terms of contributing new material. Your idea reminds me of the recipe book they made for Bucky Fuller, his many friends contributing their favorites. Looking back at 2008, random geek viewpoint: http://www.iht.com/articles/2008/12/22/arts/design22.php Kirby
Regards, Gregor
Using Python 3:
g = Primes() next(g)
-1
next(g)
....
I definitely believe that a good way to improve our current math curriculum would be to weave in computational number theory. This would be the 21st century answer to 'back to basics'. I think a huge problem in student math illiteracy has to do with not understanding division, remainders, and ratios. When dealing with division, our curriculum tends to focus on quotients, but understanding the nature of the remainder has a lot to do with what math and technology are about these days. Exploring how to find primes is definitely a 'must include' in a computational math curriculum. I think students should explore this in a variety of ways, including both sieves and generators, discussing why one might choose one approach or another in various situations. This would do a whole lot of good for both math and tech literacy simultaneously. An interesting fact is that, except for 2 and 3, all primes are adjacent to a multiple of 6. That is easy to prove: Let n be a multiple of 6. n+1 might be prime. n+2 is divisible by 2. n+3 is divisible by 3. n+4 is divisible by 2. n+5 might be prime n+6 is another multiple of 6. Here's a generator that uses this jumping by 6 approach: def primes(): p = [-1, 2, 3] for x in p: yield x def is_prime(n): for factor in p[1:]: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: if is_prime(multiple-1): yield multiple-1; p.append(multiple-1) if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1) multiple += 6 - Michel On Sat, Jan 17, 2009 at 9:31 PM, kirby urner <kirby.urner@gmail.com> wrote:
On Sat, Jan 17, 2009 at 5:40 PM, Gregor Lingl <gregor.lingl@aon.at> wrote:
kirby urner schrieb:
Yes thank you I completely agree. A stash of sieves, plus data mine this very archive for our earlier work on this topic.
My only suggestion is you include a generator version e.g.:
At first this seems an attractive idea, but in my opinion the idea of sieves is fairly antagonistic to that of generators. A sieve is used to eliminate from a given set elements that have not some desired property, while generators (ideally) create objects, one at atime, with that desired property. Drastically: you cannot sieve at first all even numbers from an infinite set or sequence. For educational purposes I'd prefer examples that display a single concept in a small and simple way. :-* A prime number generater based on some different algorithm of course may be interesting and useful.
Yes sir! Excellent clarification. The goal is to have a worthy generator that always gives the next prime. "Trial by division" is the simplest approach I can think of...
def primes(): sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway yield sofar[0] # get these out of the way yield sofar[1] # the only even prime yield sofar[2] # and then 3 candidate = 5 # we'll increment from here on while True: # go forever for factor in sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? yield candidate # woo hoo! sofar.append(candidate) # keep the gold break # onward! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please
g = primes() next(g) -1 next(g) 2 next(g) 3 next(g) 5 next(g) 7 next(g) 11 next(g) 13 next(g) 17 next(g) 19 next(g) 23 next(g) 29 next(g) 31 next(g) 37 next(g) 41
I think you're correct that the sieve best works with a pre-specified finite domain: sieve it completely, using divisors < math.sqrt(len(domain)) then iterate over it maybe, but the array is already populated, taking up memory. The above generator, in contrast, gradually takes up more memory (shows what generators are good for then: saving state between cycles).
To continue work in this area one (or at least me) has to have some criteria to judge the solutions. Clearly it was advantageous if there was some consensus about these criteria in the community.
Fortunately, we have hundreds of years of math pedagogy, so in terms of avoiding quarrels, start with what's already on the books are "must have" and just render it Pythonically.
So, for example, every pre-college math curriculum I'm aware of makes the distinction between prime and composite numbers.
On the other hand, few include the Fermat test or Fermat's Little Theorem, don't have RSA as a goal. So whereas generators for primes, fibonaccis, pascal's triangle, would seem non-controversial, anything having to do with Fermat's Little Theorem would seem an uphill battle, especially without buy in on the RSA bit.
What makes a lot of this stuff more accessible than before is we have the ability to work with large numbers of digits. Both text books and calculators tend to crap out at more that 15 significant figures. Not so in Python or any significantly endowed language. 2 ** 10000 is no problem for us, is for the paper and pencil crowd, or the TI crowd (both pitiable).
I don't think there's a way to avoid quarrels. People have different leadings, throw their hats in the ring, and we see what synergies develop. My goal is to keep the process open and participatory, not to close it down. The sight of people debating is far less disturbing than the sight of everyone in lockstep (the Borg).
There should be some criteria concerning (a) the choice of problems and themes, e.g. to prefer small problems that expose a single idea - or rather
not
... etc., as well as some (b) code related criteria, like clarity, conciseness, efficiency, beauty (!) etc., ranked according to their priorities.
This will be up to each professional teacher in whatever walk of life -- to judge what to include and what to exclude. Each teacher will find her or himself in agreement with some, disagreement with others, over what to include. Twas ever thus.
What to avoid, in my book, is a restrictive environment which takes a one size fits all approach and dictates to all teachers how it must be, removing much individual freedom.
Reduction in biodiversity is dangerous in my estimation.
That's why I fight against "national curriculum" ideologues on the Math Forum, other places.
Once I had the following idea: there are so many renowned pythonistas in the developers community, many of them also interested to promote Python in the educational area (see for instance the protagonists in Jeffrey Elkners "Introducing Python"). How about to ask them to make a personal donation to the educators and learners: a piece of code, 10 to 12 lines at most, that they individually consider to show most convincingly the power or the beauty of programming with Python - or the fun they have with it. Young people like role models ;-)
That's a fun idea.
Another approach is to start some schools in which Python is defacto included as an important tool in the math curriculum, and compete with other schools that make different choices, see how that goes.
Don't try to "convince the world" before starting your experiment.
You need no one's permission to take the initiative.
Individuals make all the difference in this world, alone and in groups.
Regrettably I didn't persue that idea further. What do you think of it. Ok, the days of the early pioneers are over, but perhaps it's still worth a try?
I think the first generation of Pythoneers, counting myself as one of them, should be collecting momentos and souvenirs, as soon enough our generation will no longer be heard from, in terms of contributing new material.
Your idea reminds me of the recipe book they made for Bucky Fuller, his many friends contributing their favorites.
Looking back at 2008, random geek viewpoint: http://www.iht.com/articles/2008/12/22/arts/design22.php
Kirby
Regards, Gregor
Using Python 3:
g = Primes() next(g)
-1
next(g)
....
On Sat, Jan 17, 2009 at 11:59 PM, michel paul <mpaul213@gmail.com> wrote:
I definitely believe that a good way to improve our current math curriculum would be to weave in computational number theory. This would be the 21st century answer to 'back to basics'.
Yes. OSCON avatar R0ml has puts a strong liberal arts spin, says these language games with computers are the new rhetoric, the basis for responsible civic participation. If they deny you access to these skills, that's a clear conspiracy to disempower you, or feel free to treat it that way: blend in, act like nothing is wrong, then network with your friends like crazy after school, do peer to peer teaching. Bone up on what they're withholding, your right as a citizen. Fortunately, Portland makes that easy, what with OS Bridge, Saturday Academy and so on. Plus some of our public schools have already turned the corner. LEP High is all open source Ubuntu on wireless, had me in peer teaching Python years ago by now (realized they could do it).
I think a huge problem in student math illiteracy has to do with not understanding division, remainders, and ratios. When dealing with division, our curriculum tends to focus on quotients, but understanding the nature of the remainder has a lot to do with what math and technology are about these days.
Per our Shuttleworth meetup in London that time (some years ago), in South Africa at least they're just bored out of their skulls if you didn't share the cool toys with them (the students). "When do we get to learn about computers? That's what we're here for. We know this knowledge is necessary to run companies, governments, any large scale service. If that's not what we're learning, why are we here?" Tuxlabs, Freedom Toasters, OLPC... all pieces of the puzzle. Many (not all) North Americans are more docile and controllable, weren't oppressed by years of apartheid, and so take it sitting down when you say you're "teaching math" but teach nothing about the executable math notations except on a TI (very anemic and underpowered, a joke if you're trying to run a railroad).
Exploring how to find primes is definitely a 'must include' in a computational math curriculum. I think students should explore this in a variety of ways, including both sieves and generators, discussing why one might choose one approach or another in various situations. This would do a whole lot of good for both math and tech literacy simultaneously.
Yes, and the literature is already well developed. The Fermat Test works pretty well actually. If 2**(p-1) % p is 1, you're likely dealing with a prime. Let's test it:
sequence = fermat_test() next(sequence) 5 next(sequence) 7 next(sequence) 11 next(sequence) 13 next(sequence) 17 next(sequence) 19 next(sequence) 23 next(sequence) 29 next(sequence) 31
Pretty good huh. If you hard code the exceptions (as a list) you can get a long way with this. It's also a good lesson in simple logic: "IF you're a prime THEN you will pass the Fermat Test" is true, but "IF you pass the Fermat Test THEN you are prime" is false. Talk about Carmichael Numbers. The Fermat Test is based on Euler's Theorem that a base to a totient power of N, mod N, nets you unity. RSA encrypts your message m by raising it to a 3rd power (say) mod public key i.e. c = pow(m, 3, N), but then we know the inverse of 3, call it d, mod totient(N) such that pow(c, d, N) will be the base itself, i.e. m (we've gone "around the clock" just the right distance). d is kept secret to the receiver, N is published and used to encrypt by the sender (as is the source code, patent expired). Unless you know totient(N) you're unable to crack c, but that requires knowing the two prime factors of N, which got thrown away. totient(N) = (p-1)*(q-1). Example: N = 17 * 23 totN = 16 * 22 m = 111 Go c = pow(111, 3, N) get d such that 3*d % totN == 1 Brute force why not:
for i in range(1, totN): if (3*i) % totN == 1: print(i)
235 get m back:
c 304 (3 * d) % totN 1 pow(c, d, N) 111
Ta da! In SSL, you don't need any published N, can establish that upon handshaking. If you want your email encrypted, then publish your N. Thanks to our early group theory exercises (e.g. Vegetable Group Soup), our South Africans, North Americans or whatever, know "inverse" means something vis-a-vis a multiplicative identity, i.e. 1 or unity. These "modulo numbers" (as we call them), may be defined as a simple Python class and made to spit out their tables, including their power tables. We override __mul__ to get these, study group properties of Closure, Associativity, Inverse and Neutral element (CAIN). Even before this, we've used the concept of "relatively prime" to define totatives and totient. The whole discussion of primes versus composites goes into this, which is where we get to these generators. Miller-Rabin is a strong primality tester, stronger than Fermat's, and might be used as a generator also (it's not a sieve). We can use the extended version of Euclid's Algorithm for the gcd, to compute the inverse of a modulo number, build it right into the class definition.
An interesting fact is that, except for 2 and 3, all primes are adjacent to a multiple of 6. That is easy to prove:
That's true of every odd number not a multiple of 3 (it's next to an even number that is a multiple of 3), some of which are also prime.
Let n be a multiple of 6. n+1 might be prime. n+2 is divisible by 2. n+3 is divisible by 3. n+4 is divisible by 2. n+5 might be prime n+6 is another multiple of 6.
Here's a generator that uses this jumping by 6 approach:
def primes(): p = [-1, 2, 3] for x in p: yield x def is_prime(n): for factor in p[1:]: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: if is_prime(multiple-1): yield multiple-1; p.append(multiple-1) if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1) multiple += 6
Yes, another way of doing trial by division, checking all odd-number candidates (automatically skipping those divisible by 3). Kirby
- Michel
michel paul wrote:
... An interesting fact is that, except for 2 and 3, all primes are adjacent to a multiple of 6.... Having once been interested in prime pairs, I remember having written a lot of code based on this "back in the day." Here is my version of your generator:
def primes(): for x in -1, 2, 3: yield x gen = primes().next for top in iter(gen, 3): pass # skip useless tests (we skip all multiples of 2 or 3) factors = [] # get pump ready for a 5 check = -1 limit = 3 * 3 - 2 # How far will 3 work as top prime? factors = [] while True: check += 6 if check >= limit: # move if this pair needs another factor top = gen() limit = top * top - 2 # limit for both candidates factors.append(top) for element in check, check + 2: for factor in factors: if element % factor == 0: break else: yield element --Scott David Daniels Scott.Daniels@Acm.Org
kirby urner schrieb:
I think you're correct that the sieve best works with a pre-specified finite domain:
....
To continue work in this area one (or at least me) has to have some criteria to judge the solutions. Clearly it was advantageous if there was some consensus about these criteria in the community.
Fortunately, we have hundreds of years of math pedagogy, so in terms of avoiding quarrels, start with what's already on the books are "must have" and just render it Pythonically. ....
There should be some criteria concerning (a) the choice of problems and themes, e.g. to prefer small problems that expose a single idea - or rather not ... etc., as well as some (b) code related criteria, like clarity, conciseness, efficiency, beauty (!) etc., ranked according to their priorities.
This will be up to each professional teacher in whatever walk of life -- to judge what to include and what to exclude. Each teacher will find her or himself in agreement with some, disagreement with others, over what to include. Twas ever thus.
I think it's not that easy. I'd like to dive a bit into this topic, resuming the code examples given in this thread and adding a few additional ideas. What concerns efficiency, I've measured the time to compute the 9592/9593 primes in the range up to 100000 and (in order to get some idea how the algorithm scales) also those up to 500000 (on my machine). Here is your, Kirby's, code: def primes(): sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway yield sofar[0] # get these out of the way yield sofar[1] # the only even prime yield sofar[2] # and then 3 candidate = 5 # we'll increment from here on while True: # go forever for factor in sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? yield candidate # woo hoo! sofar.append(candidate) # keep the gold break # onward! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please Time: 100000: 1.71 s 500000: 42.72 s ----- Michel Paul's code: def primes(): sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway yield sofar[0] # get these out of the way yield sofar[1] # the only even prime yield sofar[2] # and then 3 candidate = 5 # we'll increment from here on while True: # go forever for factor in sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? yield candidate # woo hoo! sofar.append(candidate) # keep the gold break # onward! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please Time: 100000: 1.58 s 500000: 32.25 s ----- I've modified this one slightly, with a surprising effect (I conjecture mainly due to avoiding copying p repeatedly): def primes(): yield(-1) p = [2, 3] for x in p: yield x def is_prime(n): for factor in p: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: for cand in multiple-1, multiple+1: if is_prime(cand): yield cand p.append(cand) multiple += 6 Time: 100000: 0.14 s 500000: 1.05 s ----- Scott Daniels code: def primes(): for x in -1, 2, 3: yield x gen = primes().next for top in iter(gen, 3): pass # skip useless tests (we skip all multiples of 2 or 3) factors = [] # get pump ready for a 5 check = -1 limit = 3 * 3 - 2 # How far will 3 work as top prime? factors = [] while True: check += 6 if check >= limit: # move if this pair needs another factor top = gen() limit = top * top - 2 # limit for both candidates factors.append(top) for element in check, check + 2: for factor in factors: if element % factor == 0: break else: yield element Time: 100000: 0.07 s 500000: 0.50 s ----- Compare the above generators to sieve algorithms: G.L. minimal sieve def primes(n): s = set(range(3,n+1,2)) for m in range(3, int(n**.5)+1, 2): s.difference_update(range(m*m, n+1, 2*m)) return [2]*(2<=n) + sorted(s) Time: 100000: 0.014 s 500000: 0.11 s ----- G.L.: sieve def primes(n): s = set(range(3,n+1,2)) if n >= 2: s.add(2) m=3 while m * m < n: s.difference_update(range(m*m, n+1, 2*m)) m += 2 while m not in s: m += 2 return sorted(s) Time: 100000: 0.012 s 500000: 0.086 s ----- Apparently sieves are considerably faster at the cost that the whole sieve has to be calculated before the primes can be retrieved. Not a disadvantage if you only want to know the n-th prime. So this suggests to make use of the sieve-paradigm also for prime generators. Here is a rather primitive example: G.L. sieve based generator: def primes(): CHUNKSIZE = 5000 # arbitrary even primes = [] yield 2 # first chunk candidates = range(3,CHUNKSIZE,2) chunk = set(candidates) for m in candidates: if m*m > CHUNKSIZE: break chunk.difference_update(range(m*m, CHUNKSIZE, m)) chunk = sorted(list(chunk)) for p in chunk: yield p primes.extend(chunk) lower = CHUNKSIZE # more chunks while True: upper = lower + CHUNKSIZE chunk = set(range(lower+1,upper,2)) for m in primes: if m*m > upper: break chunk.difference_update(range(lower + m - lower%m, upper, m)) chunk = sorted(list(chunk)) for p in chunk: yield p primes.extend(chunk) lower = upper Time: 100000: 0.023 s 500000: 0.113 s ----- Of course there are many more possibilities to realize this, for instance to use slice-assignment instead of sets. This would require some somewhat opaque index calculations, but be - as far as I rember - even faster. Particularly I suppose that there exist faster algorithms for generating primes, but I admittedly don't know them. ====================================================== Summing up: Kirby 1.71 s 42.72 s Michel Paul 1.58 s 32.25 s Michel Paul modified:: 0.14 s 1.05 s Scott Daniels: 0.07 s 0.50 s G.L. minimal sieve: 0.014 s 0.109 s G.L. sieve: 0.012 s 0.086 s G.L. sieve-based generator: 0.023 s 0.113 s (performance depends on CHUNKSIZE) This exposes in my opinion an unsurmountable dilemma, namely that usually you cannot meet even those few criteria mentioned in the beginning in a single solution. So under the aspects you exposed at the beginning of this thread, "Pythonic Math", which title in some sense includes and/or addresses this dilemma, how would you prefer to weight those criteria? Regards Gregor
On Sun, Jan 18, 2009 at 7:31 PM, Gregor Lingl <gregor.lingl@aon.at> wrote: [SNIP]
======================================================
Summing up:
Kirby 1.71 s 42.72 s Michel Paul 1.58 s 32.25 s Michel Paul modified:: 0.14 s 1.05 s Scott Daniels: 0.07 s 0.50 s G.L. minimal sieve: 0.014 s 0.109 s G.L. sieve: 0.012 s 0.086 s G.L. sieve-based generator: 0.023 s 0.113 s (performance depends on CHUNKSIZE)
You may also want to consider the following: ''' Sieve of erathosthenes, from the Python Cookbook, 2nd edition ''' import itertools import pprint def erathosthenes(): '''Yields the sequence of prime numbers via the Sieve of Erathosthenes.''' D = {} # map each composite integer to its first-found prime factor for q in itertools.count(2): # q gets 2, 3, 4, 5, ... ad infinitum p = D.pop(q, None) if p is None: # q not a key in D, so q is a prime, therefore, yield it yield q # mark q square as not-prime (with q as first found prime factor) D[q*q] = q if __name__ == '__main__': pprint.pprint(D) else: # q is a composite number with p as its first-found prime number # So, let's try to find the next smallest possible composite to # add and that was not already present with the same first-found # prime number x = q + p while x in D: x += p D[x] = p if __name__ == '__main__': sieve = erathosthenes() for i in range(10): print sieve.next() === André
On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <gregor.lingl@aon.at> wrote:
Michel Paul's code:
def primes(): sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway yield sofar[0] # get these out of the way yield sofar[1] # the only even prime yield sofar[2] # and then 3 candidate = 5 # we'll increment from here on while True: # go forever for factor in sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? yield candidate # woo hoo! sofar.append(candidate) # keep the gold break # onward! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please
Time: 100000: 1.58 s 500000: 32.25 s -----
Actually, that's Kirby's code. This is what I sent: def primes(): p = [-1, 2, 3] for x in p: yield x def is_prime(n): for factor in p[1:]: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: if is_prime(multiple-1): yield multiple-1; p.append(multiple-1) if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1) multiple += 6 Is this what was tested? Or what was listed? Just curious.
I've modified this one slightly, with a surprising effect (I conjecture mainly due to avoiding copying p repeatedly):
def primes(): yield(-1) p = [2, 3] for x in p: yield x def is_prime(n): for factor in p: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: for cand in multiple-1, multiple+1: if is_prime(cand): yield cand p.append(cand) multiple += 6
Time: 100000: 0.14 s 500000: 1.05 s -----
Yeah, I like the 'for cand in multiple-1, multiple+1'. I actually did do it that way on a previous occasion. So this is very interesting. - Michel
On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <gregor.lingl@aon.at <mailto:gregor.lingl@aon.at>> wrote:
Michel Paul's code:
def primes(): sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway yield sofar[0] # get these out of the way yield sofar[1] # the only even prime yield sofar[2] # and then 3 candidate = 5 # we'll increment from here on while True: # go forever for factor in sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? yield candidate # woo hoo! sofar.append(candidate) # keep the gold break # onward! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please
Time: 100000: 1.58 s 500000: 32.25 s -----
Actually, that's Kirby's code. This is what I sent:
def primes(): p = [-1, 2, 3] for x in p: yield x def is_prime(n): for factor in p[1:]: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: if is_prime(multiple-1): yield multiple-1; p.append(multiple-1) if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1) multiple += 6
Is this what was tested? Or what was listed? Just curious. Sorry. Of course, you are right. That was a copy and paste - error. Your code was what was tested and the result of which is listed in
michel paul schrieb: the table. And you can easily recognize, that it was also your code, that I had modified. (see below) Next time I'll be more careful Gregor
I've modified this one slightly, with a surprising effect (I conjecture mainly due to avoiding copying p repeatedly):
def primes(): yield(-1) p = [2, 3]
for x in p: yield x def is_prime(n): for factor in p:
if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: for cand in multiple-1, multiple+1: if is_prime(cand): yield cand p.append(cand) multiple += 6
Time: 100000: 0.14 s 500000: 1.05 s -----
Yeah, I like the 'for cand in multiple-1, multiple+1'. I actually did do it that way on a previous occasion. So this is very interesting.
- Michel
This is a corrected version of my previous posting. (1) According to the complaint of Michel I have inserted *his* code instead of Kirby's, which ocurred there (for a second time). (2) According to a suggestion of Andre I've added (towards the end of the posting) the code form the cookbook, which is ingenious but not the fastest one. (3) I've updated the table of the timings. Regards, Gregor kirby urner schrieb:
I think you're correct that the sieve best works with a pre-specified finite domain: ....
To continue work in this area one (or at least me) has to have some criteria to judge the solutions. Clearly it was advantageous if there was some consensus about these criteria in the community.
Fortunately, we have hundreds of years of math pedagogy, so in terms of avoiding quarrels, start with what's already on the books are "must have" and just render it Pythonically. ....
There should be some criteria concerning (a) the choice of problems and themes, e.g. to prefer small problems that expose a single idea - or rather not ... etc., as well as some (b) code related criteria, like clarity, conciseness, efficiency, beauty (!) etc., ranked according to their priorities.
This will be up to each professional teacher in whatever walk of life -- to judge what to include and what to exclude. Each teacher will find her or himself in agreement with some, disagreement with others, over what to include. Twas ever thus.
I think it's not that easy. I'd like to dive a bit into this topic, resuming the code examples given in this thread and adding a few additional ideas. What concerns efficiency, I've measured the time to compute the 9592/9593 primes in the range up to 100000 and (in order to get some idea how the algorithm scales) also those up to 500000 (on my machine). Here is your, Kirby's, code: def primes(): sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway yield sofar[0] # get these out of the way yield sofar[1] # the only even prime yield sofar[2] # and then 3 candidate = 5 # we'll increment from here on while True: # go forever for factor in sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? yield candidate # woo hoo! sofar.append(candidate) # keep the gold break # onward! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please Time: 100000: 1.71 s 500000: 42.72 s ----- Michel Paul's code: def primes(): p = [-1, 2, 3] for x in p: yield x def is_prime(n): for factor in p[1:]: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: if is_prime(multiple-1): yield multiple-1; p.append(multiple-1) if is_prime(multiple+1): yield multiple + 1; p.append(multiple+1) multiple += 6 Time: 100000: 1.58 s 500000: 32.25 s ----- I've modified this one slightly, with a surprising effect (I conjecture mainly due to avoiding copying p repeatedly): def primes(): yield(-1) p = [2, 3] for x in p: yield x def is_prime(n): for factor in p: if factor**2 > n: return True if n%factor == 0: return False multiple = 6 while True: for cand in multiple-1, multiple+1: if is_prime(cand): yield cand p.append(cand) multiple += 6 Time: 100000: 0.14 s 500000: 1.05 s ----- Scott Daniels code: def primes(): for x in -1, 2, 3: yield x gen = primes().next for top in iter(gen, 3): pass # skip useless tests (we skip all multiples of 2 or 3) factors = [] # get pump ready for a 5 check = -1 limit = 3 * 3 - 2 # How far will 3 work as top prime? factors = [] while True: check += 6 if check >= limit: # move if this pair needs another factor top = gen() limit = top * top - 2 # limit for both candidates factors.append(top) for element in check, check + 2: for factor in factors: if element % factor == 0: break else: yield element Time: 100000: 0.07 s 500000: 0.50 s ----- Compare the above generators to sieve algorithms: G.L. minimal sieve def primes(n): s = set(range(3,n+1,2)) for m in range(3, int(n**.5)+1, 2): s.difference_update(range(m*m, n+1, 2*m)) return [2]*(2<=n) + sorted(s) Time: 100000: 0.014 s 500000: 0.11 s ----- G.L.: sieve def primes(n): s = set(range(3,n+1,2)) if n >= 2: s.add(2) m=3 while m * m < n: s.difference_update(range(m*m, n+1, 2*m)) m += 2 while m not in s: m += 2 return sorted(s) Time: 100000: 0.012 s 500000: 0.086 s ----- Apparently sieves are considerably faster at the cost that the whole sieve has to be calculated before the primes can be retrieved. Not a disadvantage if you only want to know the n-th prime. So this suggests to make use of the sieve-paradigm also for prime generators. Here is a rather primitive example: G.L. sieve based generator: def primes(): CHUNKSIZE = 5000 # arbitrary even primes = [] yield 2 # first chunk candidates = range(3,CHUNKSIZE,2) chunk = set(candidates) for m in candidates: if m*m > CHUNKSIZE: break chunk.difference_update(range(m*m, CHUNKSIZE, m)) chunk = sorted(list(chunk)) for p in chunk: yield p primes.extend(chunk) lower = CHUNKSIZE # more chunks while True: upper = lower + CHUNKSIZE chunk = set(range(lower+1,upper,2)) for m in primes: if m*m > upper: break chunk.difference_update(range(lower + m - lower%m, upper, m)) chunk = sorted(list(chunk)) for p in chunk: yield p primes.extend(chunk) lower = upper Time: 100000: 0.023 s 500000: 0.113 s ----- Of course there are many more possibilities to realize this, for instance to use slice-assignment instead of sets. This would require some somewhat opaque index calculations, but be - as far as I rember - even faster. Particularly I suppose that there exist faster algorithms for generating primes, but I admittedly don't know them. To one more we were pointed by Andre Roberge. It is form the Python cookbook (2nd ed.). Stupendous, but not easy to understand imho, especially as a disguised sieve of Eratosthenes (and not Erathosthenes!) D strangely contains just the next composite numbers, which normally are cancelled from the sieve. So this sieve doesn't first "cancel all multiples of 2" and then all those of three etc. but just the nearest still not cancelled multiples of all the primes already found. Marvelous! def eratosthenes(): '''Yields the sequence of prime numbers via the Sieve of Erathosthenes.''' D = {} # map each composite integer to its first-found prime factor for q in itertools.count(2): # q gets 2, 3, 4, 5, ... ad infinitum p = D.pop(q, None) if p is None: # q not a key in D, so q is a prime, therefore, yield it yield q # mark q square as not-prime (with q as first found prime factor) D[q*q] = q else: # q is a composite number with p as its first-found prime number # So, let's try to find the next smallest possible composite to # add and that was not already present with the same first-found # prime number x = q + p while x in D: x += p D[x] = p Time: 100000: 0.067 s 500000: 0.34 s ----- ====================================================== Summing up: Kirby 1.71 s 42.72 s Michel Paul 1.58 s 32.25 s Michel Paul modified:: 0.14 s 1.05 s Scott Daniels: 0.07 s 0.50 s G.L. minimal sieve: 0.014 s 0.109 s G.L. sieve: 0.012 s 0.086 s G.L. sieve-based generator: 0.023 s 0.113 s (performance depends on CHUNKSIZE) cookbook - sieve generator: 0.067 s 0.34 s This exposes in my opinion an unsurmountable dilemma, namely that usually you cannot meet even those few criteria mentioned in the beginning in a single solution. So under the aspects you exposed at the beginning of this thread, "Pythonic Math", which title in some sense includes and/or addresses this dilemma, how would you prefer to weight those criteria? Regards Gregor
On Sun, Jan 18, 2009 at 6:11 PM, Gregor Lingl <gregor.lingl@aon.at> wrote:
This exposes in my opinion an unsurmountable dilemma, namely that usually you cannot meet even those few criteria mentioned in the beginning in a single solution.
I think it's OK that there's not a 'single' solution. If I saw math students interested in coming up with their own ways to generate primes, even if not optimized, wow, I'd be thrilled. I gave my math students the opportunity to do end of semester projects using either Python or GeoGebra <http://www.geogebra.org/cms/>. One kid emailed me saying he had figured out a way to generate any number of rows of Pascal's triangle using Python, and he wanted to know if this would be an OK kind of project. I found that really interesting given the topics in this thread occurring simultaneously. I replied to him "Absolutely!" I haven't seen his code yet, but I'm really glad that this is what he wanted to explore.
On Sun, Jan 18, 2009 at 3:31 PM, Gregor Lingl <gregor.lingl@aon.at> wrote: << SNIP >>
Of course there are many more possibilities to realize this, for instance to use slice-assignment instead of sets. This would require some somewhat opaque index calculations, but be - as far as I rember - even faster. Particularly I suppose that there exist faster algorithms for generating primes, but I admittedly don't know them.
======================================================
Summing up:
Kirby 1.71 s 42.72 s Michel Paul 1.58 s 32.25 s Michel Paul modified:: 0.14 s 1.05 s Scott Daniels: 0.07 s 0.50 s G.L. minimal sieve: 0.014 s 0.109 s G.L. sieve: 0.012 s 0.086 s G.L. sieve-based generator: 0.023 s 0.113 s (performance depends on CHUNKSIZE)
This exposes in my opinion an unsurmountable dilemma, namely that usually you cannot meet even those few criteria mentioned in the beginning in a single solution. So under the aspects you exposed at the beginning of this thread, "Pythonic Math", which title in some sense includes and/or addresses this dilemma, how would you prefer to weight those criteria?
Regards
Gregor
Hey Gregor, I'm really pleased you would do some careful analysis regarding efficiency, one of the several criteria you mentioned. I do think it's important to look at mathematics as an energetic, ergo economic, activity, in the sense of consuming clock cycles while burning through joules, calories (Roz Savage is one of my "action figures" in my curriculum writing, burning joules as she rows the Atlantic). First Person Physics is likewise focused in athletics, stress medicine. An inefficient algorithm may well cost you, eat into your free time, when you could be cutting yourself slack by putting a little more thought into your technique. Efficiency matters. Sometimes we say "the math is bad" because it's just too dang slow, even if correct (years too late). You want a reasoning process able to keep up with the demands of the day. So, again, agreeing with you, efficiency is a critical parameter (interesting conversations with my colleague Trevor Blake on precisely this point at FG the other day (FG of Fine Grind Productions, undertaken with Jody Francis (cns.cfo)). On the other hand, if we're really trying to be blindingly fast, why are we using Python at all? Answer: we're not really trying to be as fast as possible. We're more like this: http://www.istockphoto.com/file_thumbview_approve/422526/2/istockphoto_42252... Speed of execution must not be what matters most. We're avoiding cluttering our code with type declarations (yay). We're indulging in clean syntax, no curly braces. We're learning something cross-platform, respected by industry. Which is why we're *not* using VBA-per-Access or VB# (smile). Trial by division is just one of those generic topics the pre-computer mathematicians would dwell upon, in contrast to the sieve, not that they're unrelated. Given we're quite young, just learning about composite versus prime, starting to get our feet wet in algebra, which is more abstract this time around, thanks to operator overloading, thanks to "modulo numbers", we have more of an interest in the timeline, the chronology. How have people tackled this problem, of getting prime numbers of arbitrary size. Why do we call them "probable primes" in that Jython method? By the way, here's a class, adapted from my trial-by-division generator, that saves state in object variables, and so doesn't need to be written with yield. class Primes(): def __init__(self): self.sofar = [-1, 2,3] # a running start, -1 proposed by J.H. Conway self.counter = 0 self.maxprime = 3 def __next__(self): if self.counter < 3: self.counter = self.counter + 1 return self.sofar[self.counter - 1] candidate = self.maxprime + 2 # we'll increment from here on while True: for factor in self.sofar[1:]: # skip -1 (or don't use it in the first place) if factor ** 2 > candidate: # did we pass? self.sofar.append(candidate) # keep the gold self.maxprime = candidate self.counter += 1 return candidate # woo hoo! if not candidate % factor: # oops, no remainder break # this is a composite candidate += 2 # next odd number please In action, this looks a lot like a generator, except we're also using numeric indexing to retrieve any prime so far, a new wrinkle:
from trialbydivision import Primes g = Primes() next(g) -1 next(g) 2 next(g) 3 next(g) 5 next(g) 7 next(g) 11 next(g) 13 next(g) 17 next(g) 19 next(g) 23 g[3] 5 g[10] Traceback (most recent call last): File "<pyshell#91>", line 1, in <module> g[10] File "/home/kirby/trialbydivision.py", line 26, in __getitem__ return self.sofar[index] IndexError: list index out of range g[8] 19 g[6] 13
That we're able to work through either method in but seconds or less, up to what would have seemed pretty high numbers to be dealing with concretely, just a few decades back (ignoring scientific notation, talking about mantissas), would have seemed quasi-incredible to these Egyptian scribes or Imperial desk jobbers or whatever they were. How deeply do we want to go into the Python? Must we do both the generator *and* the class versions? It's not a matter of "must" (we hope) so much as each student following an IEP (an "individual learning plan"), freely exploring in ways that make sense. In your peer group, is it more important to develop this talent or that, this skill or that? There's a reason it's called "a gymnasium" in German I think: the different machines are marked, as to which muscle groups they exercise. If you're racing through in a crypto thread, anxious to get to the RSA part, then maybe we don't waste your time on the intricacies of metaclasses or deques. On the other hand, if you're anxious to master Python the language, because of a newspaper job where Django gets used, then don't waste your time on RSA just now, focus on regular expressions. Work back from your goals, anticipate job requirements, cram where you think it'll pay off. Encourage students to make these calculations themselves. It's not all up to the guidance counselors, or shouldn't be. Obviously, if it's a "group march" (the typical classroom, taking kids through as a group), with teacher as tour guide, then it's good to give some up front info about what's to be covered, with referrals to other options if this doesn't sound like what you're into. Corporate training same deal: (e.g) in this class, we will be looking at CREATE TABLE syntax in SQL for 30 mins, then moving to the "Django way" of specifying tables. Lunch. Then a review, a few more running examples. We're used to this from OSCON, Pycon, whatever conferences: a catalog of offerings with blurbs as to what to expect. Imagine these topic sections in a Gnu Math PDF: SQL and supermarket management SQL and library science SQL and hotel reservations systems ... (many more, all with SQL -- students filter through in different queues) My Saturday Academy course in April won't have much SQL even though this is a good age to learn some, is mostly about two ways of rendering computer graphics: either by real time animation (Sims, games, VRML, VPython, Pygame) or by high lag time ray tracing (POV-Ray). We talk about Model, View, Controller (MVC) where our Model is persistent data in an algebra, a View is a rendering (visualization), and the Controller is Python. In sum, I think the stress to put on the "time efficiency" is related to the goals of the particular class (this doesn't sound controversial to me ears, more like a truism). In many math classes, where the goal is conceptual clarity and fluency within specific namespaces (language games), we will consider the fast response times of an interpreted bytecode language such as Python to be miraculous in comparison to our old ways with paper and pencil. We're like that old Xerox commercial with that monk copyist (that's what they'd do all day: transcribe), satisfied to finally have a fast photocopier. http://www.youtube.com/watch?v=_IgH2M02xek In our intro to maths context, we will prefer short and succinct over cluttered, even at a speed cost. In another [13-16 college] course, we'll maybe learn MMIX and use that instead, covering a lot of the same algorithms. This literature is already well developed, so no need to reinvent that wheel. http://www-cs-faculty.stanford.edu/~uno/taocp.html Note: my trial-by-divison code is quirky cluttered with comments, plus some would complain the -1 is cluttering things. Others are glad to see J.H. Conway's suggestion finally percolating outward in some subculture's archive (Python Nation's in this case). Kirby
participants (5)
-
Andre Roberge -
Gregor Lingl -
kirby urner -
michel paul -
Scott David Daniels