Category Archives: Uncategorized

  • 0

Art with Complex Numbers!

Category : Uncategorized

Complex numbers are numbers made up of a real part and an imaginary part containing i, the square root of negative 1. They’re usually expressed as z = a + bi, where a and b are real numbers, as in z = 2 + 3i. In fact, every number you’ve used is a complex number, but a real number like 5 is expressed as 5 + 0i, meaning it has no imaginary part. It reminds me of the character in the Moliere play who was tickled to learn he had been speaking prose his entire life without knowing it.

When you learn about complex numbers in a traditional math class you seldom get to do much with them, because it takes a lot of algebra to multiply them together (think FOIL) and forget dividing them. Your textbook says they’re used in such fractals as the Mandelbrot set but it never tells you how.

The great thing about using computers in math class is you can write functions to operate on complex numbers and (once you’ve ensured your code works) easily transform them. Every point on the plane is given a coordinate, not unlike the (x,y) coordinate system you see in Algebra class. In fact each point (x,y) in the traditional Cartesian coordinate system can be expressed as a complex number in the complex coordinate system, as z = x + iy:

 Here’s where you start learning about transformations. Obviously, adding and subtracting complex numbers corresponds to translating a point. Multiplying complex numbers corresponds to rotating. Squaring complex numbers is particularly interesting, because of the patterns that result. In the figure below I created a grid inside a tiny part of the coordinate grid. The blue lines are one unit apart, so we’re really just dealing with the points between 0 and 1 horizontally and 0 and i vertically.

The black grid in the lower right is composed of a bunch of points, and when they’re put into a function they’re transformed into the red points. In this case, I created a function to square a complex number like this:

def cMult(a,b):
    '''Returns the product of two complex numbers'''
    return [a[0]*b[0]-a[1]*b[1],a[1]*b[0]+a[0]*b[1]]

Of course, multiplying a number by itself is squaring, so this will square the complex number a:

>> a = [1.0,1.0]
>>> cMult(a,a)
[0.0, 2.0]

In the graph, the complex number a = 1.0 + 1.0 i is the top right corner of the black grid. In the red grid, you can see it maps to the point 2i, at the top of the screen. The complex version is 0 + 2i, and that’s why the output says “[0.0, 2.0]”

 Santa Clara University Professor Frank Farris took this visualization one step further in his book Creating Symmetry. Instead of transforming a list of points, he transformed the pixels in pictures he took of flowers, fruit and other food. He took pictures like the one below at left, and transformed each pixel (which has a position on the screen just like points do) to another position using more and more complicated functions, resulting in surprisingly beautiful patterns like the one below at right:

The formula Farris used to map the pixels of the picture of the dahlia is

Once you’ve written the code for “take the coordinates of a pixel, run it through this function and place the color of that pixel at the new location” the rest is just giving the program new functions. I wanted to copy Farris’ beautiful wallpaper pictures and found this formula in Chapter 10:

Which leads to mapping the example color wheel to this fantastic rotation/translation design:

The equation looks ugly but once we’ve written the code for “e to the power something” and declared what the variables m and n are, the computer will do the rest. This is the output I got putting my dahlia into that function:

 Lavender’s nice, too:

Like I always say, Math is art!

My code is on github.


  • 0

Thinking About Neural Nets

Category : Uncategorized

In the spirit of tackling real-world problems we don’t know the answer to, the newest focus of the data science world is “Machine Learning.” It’s a pretty general term that applies to just about anything that deals with teaching computers to do something in an indirect way. When I teach students how to create a Tic Tac Toe game, for example, they have to tell it how to make a move and so on, and there’s a lot of “if this, then that” kind of code:

for i in range(1,10):  # Check if computer can win on next turn
    if board2[i] == ' ':        # if a space is open
        board2[i] = computer    #fill it with computer's letter
        if isWinner(board2, computer): # if it's a win
            return i                # return that move
            else:                   # Otherwise
                board2[i] = ' '     # open that space again

With Machine Learning, the computer (eventually) learns the best move through repeated training trials, like thousands of them. The Go-playing AI  from Google that just defeated the World Champion learned by being shown tens of millions of board positions from hundreds of thousands of games. The idea is good moves are reinforced while bad moves are weeded out. An Artificial Neural Net is designed to work like a human brain, where input neurons are connected to a bunch of neurons, eventually leading to output neurons. Here’s a simple view:

The idea for such a network originated in the late ’50s, but its progress had hit a brick wall before Paul Werbos came up with the idea of backpropagation in the ’70s. That means the weights and values of the paths and neurons in the network are recalculated after a trial and the network gets feedback. The mathematical methods of minimizing error are the subject of many books and Doctoral theses, but suffice it to say they involve linear algebra, statistics and calculus.

Simple nets can be made with a surprisingly few lines of Python code. I worked with a few students at the Coder School last night, and even though none of them were ready to tackle a real net yet, we made sketches of how an impulse travels from the input neurons to the output. This is what it looks like so far. Click the nodes on the left to activate a random path through the network. Notice even when no longer activated this strengthens those paths a bit each time.

See the Pen Neural Net by Peter Farrell (@peterfarrell66) on CodePen.


The next step would be to use the numbers from the weights and values of the paths and nodes to realistically depict the forward- and back-propagation until it settles on the best path through the network!


  • 0

Into the Unknown

Category : Uncategorized

One of my (grown-up) students at JobTrain wasn’t impressed with my Shakespeare-writing organisms since we knew the phrase we were trying to make it write. He has a point, and that’s what’s wrong with a lot of problems we assign in Math: we already know the answer. It reminded me of the Simpson’s episode where Lisa steals all the Teachers’ Editions of the schoolbooks. Without the answers, the teachers panic!

Making sure a formula or a program works is important and that’s why we test it with something we know the answer to. But once we know it works correctly, we should be extending it and using it on questions we don’t know the answer to!

There’s a famous problem in math and programming called the Traveling Salesman Problem (TSP), in which a salesperson has to travel to a bunch of cities and is of course looking for the shortest route. Even introducing it is a terrific math problem: how many routes are there between 3 cities? 4 cities? 10 cities? It really starts to add up!

Between n cities there are (n-1)! routes, and you need to divide that by 2 because half of them are duplicates, just in the opposite direction.

So between 10 cities there are 181,440 unique routes, and between 20 cities there are 60,822,550,204,416,000 routes! If you could check a million routes randomly every second, that would still take you 1,928 years.

In programming it’s challenging enough to draw the routes between the cities randomly and test their total distance. That’s what I did, following one of Dan Shiffman’s excellent Code Challenges on YouTube. But then you leave it running and it just chooses random routes. The best route improves a little now and then. To apply the genetic algorithm, I gave each organism a score, a length, and a list of numbers signifying a route through the cities. If there were 10 cities, the “cities” list would just be the numbers 0 through 9, shuffled randomly:

class Organism:
    def __init__(self):
        self.score = 0
        self.length = 0
        self.cities = nums[:]
        random.shuffle(self.cities)

Just like the Shakespeare program, but with numbers instead of letters. But how do you score the organism if you don’t know the answer? You give the highest score to the route with the lowest distance.

 def calcScore(self):
     #calculate the length of the route:
     myLength = self.calculateLength()
     #give a score. Lower distance --> higher score
     self.score = 1000000.0/myLength
  
     return self.score

Those organisms with “better genes” get more copies put into the mating pool and little by little the surviving routes improve. I added in some helpful mutations, where a random number of genes get switched.

It isn’t a foolproof system, though: the pool of genes could get stuck in a non-optimal route, but it does a great job for 10,000 organisms (in this model) starting with random routes. In this GIF you can see the process of improving the route in increments of 100 generations per frame. The white number is the best distance in the first generation: 13,537 units. By the end of 1000 generations or so of the organisms evolving better and better genes (which are just lists of numbers), we’ve improved the distance to 3,808 units.

My entire code is on Github.

Your students might be fascinated to know they (and their virtual helpers) are solving problems that have never been solved before! Is their solution the best one? There’s no answer in the back of the book!

Have fun and Go Organisms!


-Peter Farrell
May 15, 2017


  • 0

I Do Have a Point – in fact, I have a list of them!

Category : Uncategorized

A student found a page on Code Golf – using the least number of characters to do a task in code. It’s a popular sport:

The designs they made interested me. It was really just a bunch of points spaced out around the circumference of a circle, and each point was connected to each other point by a segment. What a great mathematical exercise! It’s simple to space points out around a circle using rotate and translate in Processing:

Unfortunately, when you transform points in Processing, they don’t have absolute coordinates you can use anymore. If you want to keep their coordinates intact, you have to use sines and cosines. Here’s the position of a point r units away from the origin and rotated a certain angle:

You have to convert degrees to radians, or even better, have the computer do it. In Processing it’s as easy as putting the degrees into a function called “radians” and it will convert it for you.

 points = [] #empty points list
 for i in range(12):
     x = 250*cos(radians(360.0*i/12))
     y = 250*sin(radians(360.0*i/12))
     #put point in a list
     points.append([x,y])

In the above code I created a list to put points in, then started a for loop that would space the points evenly around the circle. Now I just had to go over every point and draw a line between it and every other point. That’s done with this nested loop:

for p in points: #from every point
    for other in points: #to every "other" point
        stroke(255,0,0) #red
        line(p[0],p[1],other[0],other[1])

“[0]” means the x-value, and “[1]” means the y-value. Now I can see the outcome with 12 points:

Of course I wanted to make it fancy and interactive, so I connected the number of points to the x-value of the mouse. Now if the user moves their mouse left and right the number of points increases and decreases.

I like the interactivity. You get to choose how crazy it gets.


-Peter Farrell
May 10, 2017


  • 0

Solving Problems with Genetic Algorithms

Category : Uncategorized

Talk about an all-around STEM topic! If you’re interested in exploring genetics through modeling, Genetic Algorithms are a great start! I followed Chapter 9 in Dan Shiffman’s excellent book The Nature of Code (you can order it or read it for free here), where he creates a population of organisms to work out a target phrase:

target = "wherefore art thou romeo"

In Python, I created an Organism class so each organism would have a set of “genes,” or randomly generated letters to guess the target string.

characters = 'abcdefghijklmnopqrstuvwxyz '

class Organism(object):
   def __init__(self):
       self.score = 0
       self.genes = ''
       for i in range(len(target)):
           self.genes += choice(characters)

Each organism would get a score based on matched letters divided by the length of the target phrase. The score would be multiplied by 100 so it would be a whole number and that number of copies of the organism would be added to a mating pool to reproduce.

“Reproduction” would consist of splicing together two organisms’ genes at a random point so the result would still be the length of the target phrase. A certain number of the child’s genes would be replaced by random characters according to a mutation rate. Then the child organism would take one parent’s place in the population. Repeat for the next generation, and the next and the next…

It doesn’t sound particularly promising with all the randomness factored in. We kept track of the best fit phrase among the organisms and it didn’t start off well:

But in a few dozen generations there was success:

This may not be so miraculous, since we knew the target phrase, but just imagine applying this method to a problem where we don’t know the answer. In the Traveling Salesperson’s Problem (TSP), for example, you don’t know the shortest path between the cities but you can score the attempts by length and use the genetic algorithm to evolve a pretty good approximation!


-Peter Farrell
April 26, 2017


  • 0

Programming the Environment

Category : Uncategorized

If STEM is really all about linking Science and Technology, for example biology, the environment and programming, how do your students explore sustainability? If only there were a way to have students create their own virtual environment model with grass that grows and sheep that eat, reproduce and die. It would really help them to appreciate the complex interaction of elements in the environment with every new organism they add.

Years ago I was introduced to the grass-eating colony of turtles exploration on the NetLogo site and it’s a great programming challenge. Unfortunately, the Logo programming language isn’t of much use outside of the classroom. But Python is definitely a useful skill and by using the Processing graphics library we can make a visual, dynamic, interactive (and memorable!) model in maybe a couple of class periods.

We’ll start with a “sheep,” which my students and I simplified to a circle, but you can draw it as realistically as you like. Sheep need an x-y position, a color, a size, an age, and an energy level. When they’re “born” they’re added to the sheep list. So in Python the Sheep object is created like this:

class Sheep:
    def __init__(self,x,y,sList,col):
        self.x = x #x-position
        self.y = y #y-position
        self.col = col #color
        self.age = 0
        self.sz = 10 #size
        self.energy = 20 #energy level
        #add it to the sheep list
        sList.append(self)


Then you have to tell the program how to update the sheep, to make it walk around (which costs it energy points) and “eat” the grass to increase its energy points. If its energy gets down to 0, it dies and is removed from the sheep list. Every loop the Sheep’s age is incremented, and if it reaches a certain age it dies. Finally you draw the Sheep. That code looks like this:

def update(self):
    #make sheep walk randomly
    move = 10 #the distance they can move
    self.x += random(-move, move)
    self.y += random(-move, move)
    self.energy -= 1
    self.age += 1
 
    #if the sheep gets enough energy, reproduce
    if self.energy > 50:
        #create another Sheep on the same spot
        Sheep(self.x,self.y,
              sheepList,self.col)
        self.energy -= 30 #this costs energy!
 
    #draw sheep
    fill(self.col)
    ellipse(self.x,
            self.y,
            self.sz, self.sz)

Compared to Sheep, the patches of grass are pretty simple. They just need an x-y position, a size, an energy content, and an “eaten” property which can be True or False:

class Patch:
    def __init__(self,x,y):
        self.x = x #x-position
        self.y = y #y-position
        self.energy = 2 #energy from eating this patch
        self.eaten = False #hasn't been eaten yet
        self.sz = 10 #size
 
    def update(self):
        if self.eaten: #if it's been eaten
                       #it can randomly "regrow"
            if random(100)<5:
                self.eaten = False
            else:
                fill(BROWN) #eaten grass is brown
        else:
            fill(GREEN) #un-eaten grass is green
        #draw the square patch of grass:
        rect(self.x, self.y, self.sz,self.sz)

Now it’s just a matter of creating a field of grass and a bunch of sheep at random locations. I’ve put the entire code on Github. You let the model run and see how it turns out. You can change the rate at which the grass grows, the energy content of the grass, the sheep’s maximum age and many other factors, to see the changes in the environment:

Evolution

My favorite thing to do with this model is give one species of Sheep a small Evolutionary advantage, like being able to walk just a bit further, like this:

if self.col == PURPLE: 
    move = 12

Students can come up with other advantages, like giving birth to more offspring or getting more energy out of the grass. When you run the model, does the advantage matter? Here’s a screenshot from a model where the advantage certainly did matter and the purple Sheep ended up dominating the environment:

Students love to watch the model run and will come up with all kinds of interesting ideas for expanding on this template. Have fun and Go Sheep!

-Peter Farrell
April 16, 2017


  • 0

Do All the Dimensions

Category : Uncategorized

There was a great brainteaser a few years ago that asked:

Since Shaquille O’Neal’s height (7’1″) makes him so good at basketball, how much better would he be if he were 15 feet tall? How about 30 feet tall?

This should lead to a discussion of how strong a 15-foot tall person would be. Physics students have all played around with making bridges and other structures that can support hundreds of times their own weight. Why don’t we just make the same bridge 1,000 times bigger?

All other things being equal, the strength of a material (like a beam or cable) varies with the area of its cross-section. There’s an old story that gets told of a 2-inch cable breaking in a machine shop and a foolish mechanic replacing it with 2 one-inch cables. It makes mathematical sense until you calculate its area (and therefore its strength): the cross section of the 2-inch cable is a circle with an area of pi square inches:

               A = πr2 = π(1)2 = π

(A “2-inch” cable has a diameter of 2 inches and a radius of 1 inch.) The area of a one-inch circle is only a quarter of pi.

             A = πr2 = π(1/2)2 = π(1/4) = π/4

In the image below, the ratio of the radii is two-to one, but the ratio of the areas is 4 to 1.

So the 2 one-inch cables would only sum to a half of pi square units, or a half of the area (and strength) of the 2-inch cable. That’s because we’re doubling the length in 2 dimensions. A circle with 3 times the radius would have 9 times the area of the original circle.

There’s a similar step up in dimension when we’re talking about volume. And of course volume is what we mean when we talk about weight. Sure, Shaq is only doubling or tripling his height, but his volume is doubling or tripling in all 3 dimensions. That’s cubing! As you can see in the picture below, as the sidelength of the cube is doubled, the volume is multiplied by 8. Triple the sidelength and you have 27 times as much volume.

That means when we scale up our cube, our bridge, or our basketball player, the weight (volume) goes up a lot faster than its area (strength). Let’s say normal-sized Shaq, weighing 300 pounds (this is early 90s, Orlando Shaq), can lift 500 pounds. If we double his height, we’ll be multiplying his strength (area) by 4 (2 squared), meaning he could lift 2,000 pounds! Sounds impressive until we realize we’ll be multiplying his weight by 8 (2 cubed). “Shaq 2.0” would weigh 2,400 pounds, meaning he couldn’t even lift his own bodyweight off the bench.

This is the reason the tongue-depressor bridges built every day in physics classes could never really work: because as you scale them up, their volume (and thus their weight) increases much more quickly than their area (their strength). Sorry, coach!

-Peter Farrell 4/5/2017


  • 0

Computer-Aided Art

Category : Uncategorized

Yesterday at the Coder School a student and I were looking for inspiration; a Processing sketch to recreate to test our Python skills. There’s a Dutch artist named Saskia Freeke who posts a new Processing sketch every day on Twitter, and yesterday her sketch was a doozy:

I tell my students the ancient Nasrudin joke I originally read in a book by Idries Shah:

Nasrudin was asked to describe his house. He brought the man a brick and said, “It’s just a collection of these.”

My student and I tried to break down the sketch into its simplest component(s), and it’s just a collection of squares. He easily drew a square in Processing.

Next, can we make the square rotate back and forth and get bigger and smaller? Those are both behaviors that can be modeled using sines and cosines. First we needed a bunch of squares, meaning we used a loop. In Python that’s

for i in range(20):

where i is an iterator, and it takes a different value from 0 to 19 in this case. So every square will have its own i. We made the angle change with the time variable t like this:

#angle of rotation
angle = sin(t-i)

That made each square in a column rotate a little differently from the one next to it:

After that we put in a line for making the size oscillate:

#size of each square
sz = 40+20*sin(t-i/4)

Another application of the “sin(t-i)” trick. But the output of the sine function is between -1 and 1. With the “40 + 20*sin…” part, the size of the squares would oscillate between 20 and 60 pixels. So now the size oscillates:

Since every square has its own i, we can easily use that to make each square its own color. My life changed the day I learned to use HSB values. Every color is a combination of three numbers: Hue, Saturation and Brightness. Only the first number, Hue, needs to change for our purposes, so I used this code to change the color for every square:

#color of the outline
stroke(10*i,300,300)

I had to tweak the code until I settled on the “10” which would make a nice rainbow effect, my trademark. Finally we can draw the rectangle. This line means, “Draw a rectangle in the middle of the screen (0,0) with a length and width of whatever value the “sz” variable has.”

rect(0,0,sz,sz)

I posted it on Twitter, and guess who gave us a favorable comment? See below the sketch!

Procedural Art makes friends over the Internet!

 


  • 0

Free STEAM Professional Development for Teachers!

Category : Uncategorized

Ken Hawthorn and Peter Farrell will be teaching introductory Python programming and Electronics using the Arduino and the Raspberry Pi. It’s taking place on Saturday, April 8, 2017 from 8 am to 2 pm at St. Raymond’s School in Menlo Park. We’ll provide the computers and all the necessary hardware and software, and we’ll even provide pizza for lunch. Let us know if you’re interested in attending!

Here’s a map to St. Raymond’s School:


  • 0

McNugget Math

Category : Uncategorized

There’s a brainteaser that goes:

McNuggets come in packages of 6, 9 or 20 pieces. So you can easily make any multiple of 6, for example, but you can’t make exactly 7 or 8. You can combine any number of packages, so you can make 6 + 9 + 9 + 20 = 44. What’s the highest number you can’t make (exactly) out of a combination of McNugget packages?

So we know we can make 20, and 21 = 6 + 6 + 9. But we can’t make 22. Or 23. We could keep going, finding which numbers are possible and which ones aren’t. How do we know there’s a maximum “impossible” number? Once we can make a certain number of “possibles” in a row, we can assume we can make any number above that. Do you know what that is?

It’s a pretty decent brainteaser but there’s no nice algebraic way to put the numbers into an equation and spit out the answer. It might seem unsatisfying to a student used to algebra and equations. But it’s a great programming exercise!

Python to the Rescue!

I wrote a Python program to go through every possible combination of packages (6, 9 and 20) up to the number we’re investigating. If the combination comes out to be exactly 23, for example, it prints out the combination that works. Otherwise it returns an empty list.

def nuggets(num):
    '''returns the combination [i,j,k]
    of nuggets to equal num'''
    solution = [] #empty list
    # i represents the number of 6-nugget packages
    for i in range(int(num/6)+1):
        # j represents the number of 9-nugget packages
        for j in range(int(num/9)+1):
            # k is the 20 nugget packages
            for k in range(int(num/20)+1):
                # if they combine to make "num"
                if 6*i+9*j+20*k == num:
                    #add that combo to the solution list
                    solution.append([i,j,k])
    return solution

The solution for 23 and 24 are shown:

>>> nuggets(23)
[]
>>> nuggets(24)
[[1, 2, 0], [4, 0, 0]]
>>> 

This means there’s no solution for 23, but you can make 24 in two different ways: 1 x 6 + 2 x 9 = 24 and 4 x 6 = 24. I put the numbers in a loop and went up a few dozen to see if they ended:

>>> for i in range(25,50):
	print(i,nuggets(i))
...
43 []
44 [[1, 2, 1], [4, 0, 1]]
45 [[0, 5, 0], [3, 3, 0], [6, 1, 0]]
46 [[1, 0, 2]]
47 [[0, 3, 1], [3, 1, 1]]
48 [[2, 4, 0], [5, 2, 0], [8, 0, 0]]
49 [[0, 1, 2]]

So there’s no way to make 43, but you can make 44 through 49. Do we need to go any higher? Obviously if you can make 44, then you can add a 6-nugget package and make 50. Same with 45. You know you can make 51 by adding a 6. And so on all the way up. The highest number you can’t make is 43.