Radix sort with index cards

I showed my kids the radix sort.

Math Camp I: Recursion and such

The past two years I’ve taught at a summer math camp for high school students. In 2010 I assisted with a class on chaos and fractals. This year I assisted with a computers class. I’m planning to do a couple of posts about the class. This is the first of those posts.

The computer class that I helped teach focused on hardware, but also included some software topics. My main role was teaching programming. I should point out that I am not really a programmer. I’m a mathematician who uses some programming in his work. I’ve never had a programming class. Nevertheless, I hope that I was able to get some of the basics across to the students.

I first introduced programming to the students by describing a simple language for manipulating a cube, the goal being to get the cube in a prescribed orientation. More on that in a later post.

We did our programming in two languages: Python (which you can try in your browser at: Try Python) and Alice. Both are freely available. In Python we did some simple procedural programming (I had them code up a function that computes the factorial of a number and another that runs the Collatz algorithm). One of the students was able to produce a factorial algorithm very quickly. Here is his python code:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

It surprised me that he used recursion, though I think he has had some programming experience in the past. Most of the other students had had no prior programming experience and were having a hard time producing a factorial function. This also surprised me. This was my first time teaching programming, so I had little intuition for where the students might get hung up.

Alice is a drag-and-drop object-oriented language for manipulating characters in a 3-D virtual world. We mostly let the students explore Alice on their own as their interests dictated. One student wrote a very simple first-person shooter game.

In any case it was hard to get any of the kids very interested in programming. If I go back next year and assist with this same class, then I think I would like to have some compelling problems or mini-projects that would grab the kids attention and require them to do some programming. Suggestions anyone?

Building a Computer 1111: Video of our Signal-Split Prototype

As I’ve said previously we are currently working on developing a signal-split device: that is, we want something that takes one input and creates a copy of it. Or in other words one marble in, two marbles out. Below is the design we settled on for our first physical prototype of the signal split toggle.

We cut one out and mounted it. Here is video of it at work.

It works pretty well! It’s not perfect, we’ll have to keep working on it. The tough part at this point is that we don’t know whether faults in our prototypes are due to faulty craftsmanship or faulty design. We will have to make several prototypes and carefully observe them in operation to figure this out. My lack of any schooling or experience in engineering and woodworking is becoming a hindrance at this point.

Building a Computer 1110: Video of the 4-bit Adder

As promised in a previous post, here is video of our 4-bit adder prototype. We used Wandel’s plans for it, but it is missing several niceties that Wandel’s version has: a top tray that holds marbles and releases them all at once, a bottom tray to catch the marbles, and a reset mechanism

Below are a couple of pictures of detail on the adder that I invented myself. When I first put the adder together, the toggles were not working well at all. After a good deal of thought I came up with the idea of putting a couple of paper washer behind each toggle. This solved the problem.

Building a Computer 1101: Signal Split

I had an idea for a marble implementation of the signal split. It is very closely related to Wandel’s toggle. I ran the idea by my nine-year-old, then showed him the basics of Inkscape and let him do the drawing. Here is what he came up with. I think this is very close to what we will end up using, but of course we haven’t actually built it yet…

The funny thing about the signal split is it’s simple electronically: just solder a couple of wires together and you’re good. This video that I found on youtube shows a simple marble implementation of a signal split…
…but we need something that is self-resetting. I think what we’ve designed here fits the bill. Building and testing to come…

Building a Computer 1100: Multiplication and Subtraction with an Adder

My nine-year-old has been playing with our prototype four-bit adder quite a lot. After getting bored with adding, he figured out how to do subtraction with it. Of course we talked about how to do subtraction earlier. What he ended up doing is taking a pair of numbers (x,y). Finding the two’s complement representation of -y (on his own, not using the machine), and then feeding x and -y through the machine. After playing with that for a while, he told me that he had also figured out how to multiply with it. To multiply x and y, simply feed x through the machine y times, or feed y through the machine x times. Despite Keith Devlin‘s insistence that multiplication is not just repeated addition, this works (though to be fair to Devlin, he frankly admits that it works). My son keeps asking about making a multiplier. I’ve been trying to explain to him that we will be implementing multiplication in software. I’m not sure that he gets it yet, but once we get that far his experiments should help him see how to do it.

Building a Computer 1010: Counting and Human versus Machine Error

I decided that we should use the prototype toggle that we built to actually do a computation. I realized that with some manual interaction we could do a marble count. Here is how it works:

Start with a pile of marbles and feed them all through the machine. Collect the marbles that come out of the two toggle outputs in two bowls (which I have labeled bowl A and bowl B. Once all of the marbles have been fed through, the machine will be in one of its two states: either the rocker will be to the left with no marble in the catch, or the rocker will be to the right with a marble in the catch. If you watch the machine operate you realize that when marbles are output they always come in twos. That is every time a marble goes into bowl A one also goes into bowl B and vice versa. So you can see that there will be a marble in the catch if and only if the number of marbles fed through the machine is odd. Furthermore, a binary number ends in a one if and only if it is odd. In other words, once all of the marbles have been fed through the machine you can read the right-most (or least-significant) bit off from the machine: a one if there is a marble in the catch, and a zero if there isn’t.

Once all of the marbles have been fed through and the bit recorded, you should reset the machine (move the toggle to the left, releasing the marble that’s caught if there is one). Now take out the contents of bowl A; this becomes your new pile.

Repeat the process, feeding all of your new pile through the machine, record the next bit (I’ll leave it to you to convince yourself that this really does tell you the next bit) and repeat the whole process until all of the marbles are in bowl B. At this time you should have the complete binary representation of your total number of marbles.

We carried this program out for our set of marbles four times…and we got four different answers….OK, I never claimed that our prototype machine works perfectly. Actually there were two things that went wrong. Sometimes two marbles would sneak through the same side of the machine before the toggle could flip to the other side. We called this a machine error. Sometimes we would do silly things like fail to empty bowl A before feeding its contents through the machine. Thus, some of the contents of bowl A from round n would get mixed with the contents of bowl A from round n+1. This (pretty clearly) causes problems. The results we got for our number of marbles were 96, 118, 119, and 136. Then we counted them by hand and got 118. One other thing I should mention is that we watched the machine as we fed the marbles through, and sometimes there were machine errors that we noticed and corrected in real time. In any case I think that 118 is the correct number.

This experiment has got me thinking a bit about operator error versus machine error. Often one hears operator errors called “human errors”, but it occurs to me that even the machine errors are due to humans. That is, the machine errors that occurred in our little exercise were due (almost certainly) to our poor craftsmanship and possibly due to bad engineering. So machine versus operator errors really come down, not to machines versus humans, but to the people who designed and built the machines on one hand and those who are operating them on the other.

Building a Computer 1001: Video of our One-Bit Adder Prototype

As promised in a previous post, here is video of what we have working so far. Based on Wandel‘s plans, this mechanism constitutes a full adder. For my less than stellar craftsmanship it works remarkably well.

Building a Computer 1000: Subtraction

First off, here is a photo of what we have so far for our four-bit adder:

Nothing is glued down and we still have holes to cut and more pieces to cut out.

Last night my nine-year-old was asking more about subtraction. He had made a chart of four-bit binary representations of negative numbers. It started like this:

1    2    3    4    5
0001 0010 0011 0100 0101
------------------------  etc
1111 1110 1101 1100 1011
-1   -2   -3   -4   -5

With some prodding he found the pattern that -2 is the same 1 only with 1s replaced with 0s and 0s replaced with 1s. Likewise for -3 and 2, -4 and 3, -5 and 4, etc. Another way to say this is that you can get -3 from 2 by flipping all of the bits, and similarly for the other pairs.

Next I had him try the following process: Take two positive numbers. Write them out as four-bit binary numerals. Flip all of the bits of the larger one. Add the original smaller number and the bit-flipped number together. Flip all of the bits of the result. He did the following example

1:  0001
2:  0010

bit flipped 2:
    1101

add:  1  <-(carry)
    0001
   +1101
    ----
    1110

flip bits of result:
    0001

The result is the binary representation of one, which is the difference 2-1. Here’s another example:

8:  1000
3:  0011

bit flipped 8:
    0111

add: 111  <-(carries)
     0111
    +0011
     ----
     1010   

flip bits of result:
    0101 = 5

So we have to figure out how to flip bits with marbles.

Building a Computer 111: Negative Numbers

We have started building a 4-bit adder using Wandel’s plans. Photos to come! It’s amazing what you can do with a coping saw and some pine planks. It won’t look as nice as Wandel’s but I hope that it works. We have even been cutting the holes with the coping saw since I don’t have the proper drill bit. So far they have come out rounder than I expected. Straight lines are hard to do with a coping saw, but…meh they should be straight enough.

Anyway, we got some notebooks to write down our ideas and plans in. Tonight the nine-year-old set to work on how we can represent negative numbers in our binary machine. (I clued him in that this seemed to be the way to go to get a subtractor.) Since we are building a 4-bit machine currently I had him work with 4-bit numerals. This means that any carries into the fifth palce just roll off and are lost. I told him to try to find a numeral that when added to 0001 (using the algorithm that we know) gives 0000. What ever that numeral is it should represent -1. He soon found that 1111 works. Then he set to work adding 1111 iteratively to get -2, -3, etc.

The numerals he is working out for the negatives are what computer scientists call two’s complement. Computer folks will probably tell you that the name two’s complement derives from the fact that is represented by , where is the number of bits. This seems like a silly reason to call it two’s complement to me (two-to-the-N’s compliment, OK). Mathematicians will probably tell you that the name is a joke, deriving from another negative-number convention called one’s complement. What’s really happening (or what a mathematician like me would say is really happening) is that–since working with -bit numbers means you are working modulo –two’s compliment is completely natural; that is, it plays very nicely with arithmetic operations such as + and -.

Anyway, two’s compliment not only has nice properties with respect to arithmetic operations, it has a pretty clean description in terms of flipping bits. I’ll get to that later as I’m planning on having my kids discover it soon…which will lead us to want to have some other logic gates…

While the nine-year-old was at this, the seven-year-old was busy diagramming the marble adder in her notebook, while the four-year-old drew a picture of a computer in hers.

Also I’ve begun to read my book. Thoughts on it to come.