The Children Are Our Future

Number Two son (age 8) comes in to report that Number One son (age 10) is calling him stupid!

Number One son comes in holding a piece of paper:

Happy Modification Of Most Sigificant Digit In Base 10 Representation Day!

I didn't even think to comment when the MSB in base 2 changed. What kind of a NERD am I?

Once my average catches up with the daily weigh-in, I'll be Officially At My (Original) Goal. I think I'm going to aim at another 10 lbs, though.

In other news, I've been messing around with Haskell, but I need a real programming project to really do something. I was thinking about this again.

I realized yesterday that it's not just hard but actually logically impossible to represent a mechanical object physically as a strict tree. Consider even just a triangle of beams. Two of them attach, making them children of the same parent (the joint). The third attaches to both, which is illegal.

A commenter suggested the netlist approach that electronic simulators take. The problem is that the netlist is a genome of the device. I have to be able to take a subset of the genome and swap it out for another piece that also has to drop in place. How does that work without leaving dangling "wires"? I could just leave them there for Nature to work out, but is that going to make success too infrequent for me to have patience for?

I think my algorithmic approach could work. But I haven't really worked it out. In any case, Haskell (or possibly better yet, Tcl or Lisp) is probably a good match. These languages already allow you to run data as code and treat code like data easily. Actually, now that I think about it, I'm not sure Haskell does that. What is that property even called?

Modulo Operator Considered Harmful

The way I think of the modulo operator is as a remainder. 10 mod 3 = 1, because 3 * 3 = 9 and 10 - 9 = 1. But what if one of the operands is negative? What is -10 mod 3?

My naive answer was that this is obvious. -10/3 = -3. -3 * 3 = -9. To get from -9 to -10, you need to add -1. Therefore the remainder is -1. Let's see what C thinks of that:

#include 

int main(void) {
  printf(" 10 mod  3 = %d\n", 10%3);
  printf("-10 mod  3 = %d\n", -10%3);
  printf(" 10 mod -3 = %d\n", 10%-3);
  printf("-10 mod -3 = %d\n", -10%-3);

  return 0;
}

$ gcc -o mod mod.c
$ ./mod
 10 mod  3 = 1
-10 mod  3 = -1
 10 mod -3 = 1
-10 mod -3 = -1

C agrees! And I'm sure Python must follow, right?

#!/usr/bin/env python

print " 10 mod  3 = ", 10 % 3
print "-10 mod  3 = ", -10 % 3
print " 10 mod -3 = ", 10 % -3
print "-10 mod -3 = ", -10 % -3

$ ./mod.py
 10 mod  3 =  1
-10 mod  3 =  2
 10 mod -3 =  -2
-10 mod -3 =  -1

2?!?!

There's a couple ways to look at this. First, what really is the answer of -10/3 in integer division? The "real" answer (seewhatididthere) is -3.333.... When I round that to an integer, do I round "down" meaning "to the left on the number line" or "down" meaning "towards zero"? If I mean the latter, -10/3 = -3. But if I mean the first meaning, then -10/3 = -4. Then 3*-4 = -12 and so the remainder is actually 2. (If you ask Python what -10/3 is, you do in fact get -4, btw.)

Alternatively, I could revert to doing modular arithmetic under it's old name of "clock arithmetic". For 10 mod 3, the face has 3 numbers and I'm going to take 10 steps around it, starting at 0 and moving clockwise. I end up on 1. For -10 mod 3, I'm going to go counterclockwise. I end up on 2.

To me, this second interpretation is better. For one thing, rounding leftwards seems to be as counterintuitive as the original problem. For another, this clock method explains what a 10 % -3 should be. The clock face contains the space of possible answers. Doing mod 3, the answers can only be 0, 1 or 2. Doing mod -3, the answers can only be 0, -1 and -2.

Wikipedia agrees with Python, which seems to leave C out in the cold. Its folk understanding of modulo as remainder is common sense but wrong. And it isn't alone. (Some languages have mod vs rem, with the latter being a remainder. That's a good idea. Naturally FORTRAN has called the two operators mod and modulo. Stay classy, FORTRAN.)

However, it is still true that if you are working only with positive numbers, mod is a remainder. Because of this intuitive understanding, and because of the obvious confusion among language designers, it seems a good idea to me to always frame mod operations in positive space.

Invention Idea #4?

I tried to research whether this has already been invented, but I'm too lazy, too busy and too dumb to be complete. The fact that I've never heard of this will have to be enough to show that it hasn't been invented well enough.

The basic idea came from the Wikipedia fundraiser. Why does Wikipedia need to raise funds? All the "real" work of creating and editing articles is done for free. I don't know if their software costs are $0, but they should be. It's possible they might need to pay for specialized knowledge to set up some configuration files and so forth, but that's about it. Oh and servers and bandwidth.

Why are servers still trapped in the "single big centralized cost" world that software development and encyclopedia authorship used to be trapped in? Why couldn't the articles on Wikipedia be distributed across the world? It would be kind of like BitTorrent, but for small files and in real time. Another example, which is perhaps close enough to not even be an analogy anymore, is FreeNet:

Freenet works by pooling the contributed bandwidth and storage space of member computers to allow users to anonymously publish or retrieve various kinds of information. It can be thought of as a large storage device which uses key based routing similar to a distributed hash table to locate peers' data. When a file is stored in Freenet, a key which can be used to retrieve the file is generated. The storage space is distributed among all connected nodes on Freenet.

If Wikipedia were on FreeNet and my browser knew how to get there, wouldn't Wikipedia have zero server costs? The problem of bandwidth still exists, though. Most articles are rarely accessed, but some articles are accessed a lot even if for short periods of time. For instance, I bet the Inauguration 2009 page was reloaded a few times yesterday. Whoever's computer happens to have that article will get hammered. (Also, traffic analysis would reveal that they were hosting that article, which would be a problem for free-speechy issues. Probably FreeNet has already thought of this and has a solution?)

However, I think even this problem could be overcome with some redundancy and distribution. Put that page on multiple machines and everyone accesses different ones. Of course you have editing race conditions that way, but I dismiss those with a wave of my hand (while not volunteering to solve them).

(Reading farther down the FreeNet page I see there are IRC-like and forum "APIs" for using FreeNet as a network in this way, so I'm probably behind the times with my invention idea. However, it looks like they are mainly using it as an anonymous way to share porn whereas I'm interested in saving money by distributing cost.)

How Do You SolveRepresent A Problem Like Mariaechanics?

First, this. (Explanation)

It would be cool to make something like that, but more general. A wider scope of problems, more construction elements, more universal attachments, etc.

The standard method of genetic programming is to represent your algorithm/whatever as a tree. The leaves are data and the nodes are operations that the "universe" supports. Then two parents producing a child via "sex" is just trading subbranches. Mutation is random changes.

That works for a linear sequence of steps because there's a standard way to traverse a tree. The question is, how do you represent a machine in a tree? It's (usually) not a linear thing.

Take a wheel and a stick. They are two leaves, I guess. The node is the operator "attach"? But where? I need to know where on the stick AND where on the wheel. And if the connection is rigid, floppy, powered or what. Where is all that knowledge stored? How can I "break out" each of those things to allow them to mutate separately? Also, you can't have a whole-organism coordinate system, for instance, because a single mutation messes it all up.

Another idea is to use an algorithm to build the machine and represent the algorithm as a tree. But what's the advantage of that? I didn't realize until this morning: This is exactly what embryology is. A machine isn't a linear object, but constructing a machine is a linear process.

So to attach a wheel and a stick, I'd have an embryology something like this:

1) Place stick
2) Locate end of stick
3) Locate center of wheel
4) Attach

Or maybe:

1) Place stick
2) Advertises marker at X
3) Locate marker
4) Locate center of wheel
5) Attach

The marker system would be key. If there's more than one stick in the structure, "locate end of stick" is ambiguous. Whereas if the stick knows that it is, say, the left shin, it can hang out cards saying "I'M THE LEFT SHIN" and "HERE IS MY LOWER EXTREMITY" and the wheel can look for that.

Could one of my graduate students get on this and give me credit so I become rich and famous but don't have to stop the N projects I'm working on to get it done? Kthx!

Wooo

• I cracked 50 lb of weight loss today. I'm still on track (±ε) to reach my original goal by Christmas. It also happens to be, as of yesterday, 10 lbs in 100 days, or almost exactly 350 calories/day.
• Pursuant to that, I have made a breakthrough in food reduction technology. One of my favorite meals is...undocumented on this site?! WHAT. Anyway, it involves guacamole. The problem I've had is that I need to make enough to use up an entire avocado, which now that my metamabolism needs fewer calories is a little too much. Avocado turns brown if you look at it funny, so I can't put the excess in the fridge. I also can't throw it away because of the starving children in Africa. However, it turns out to freeze just fine. So now I can make M/Nths of a recipe which not only vastly reduces the hit points but also means I only use M avocados every N days.
• I'm trying to embed a microcontroller into a project that I'll describe more later. All I know is Arduino, so I'm going with that. (I guess I could just use the Atmega chip or however that works, but baby steps, people.) The basic Arduino is a little unwieldy for this, but last night I finished soldering and testing the Really Bare Bones Board. And besides being much smaller and breadboard-compatible, it's also much cheaper because it pushes some of the cost of the unit into a one-time-purchase cable.
• Number One Son, age 9, is trollering me. He just found out about HTML and has made a couple of pages. (With random size changes and font colors, naturally.) He keeps calling the .html file a "program".

New Control Structure Considered Useful

We have a large data processing problem at work. Basically, we get thousands of items every day and have to figure out which ones go together. The only way to know if they go together is to try them. Some items may not go with anything, some may fit with a hundred or more other items. The one nice thing is that once we've found 3-5 items that go together, we can zip through all the other members of the group.

The problem is finding those 3-5 items. Choosing every possible combination of 5 would take too long. Choosing every combination of 3 is fast enough, but leaves a lot of extras. The simple solution is to first try all the combos of 3, then try all the combos of 4 on the remainder, then try all the combos of 5 on the remainder of that. The smaller and smaller pile makes the larger and larger choices feasible.

My boss, who is a competent practical programmer, suggests we have 3 procedures: One that does a 3 nested loop, one that does a 4, and one that does a 5. Like this (in Tcl):

set items {apple orange banana grape strawberry}
set count 5

for {set i 0} {$i < $count} {incr i} {
    for {set j [expr $i + 1]} {$j < $count} {incr j} {
       for {set k [expr $j + 1]} {$k < $count} {incr k} {
         set string [lindex $items $i]
         lappend string [lindex $items $j]
         lappend string [lindex $items $k]
         puts $string
       }
    }
}

That's just the 3 level loop because the other two look almost the same. The 4 and 5 level loops are identical except for having additional levels. As a programmer who values elegance over readability, the phrase "identical except for" is a red flag. Why have 3 separate procedures when all you are adjusting is a single parameter? What I need is a new control structure that is basically a for loop but lets me control how many nested fors there are.

Tcl makes it easy to create new control structures. Here's the control structure definition:

# Usage:
#  indexcount - how many items are being chosen
#  itemcount  - how many items are being chosen from
#  indexvar   - variable to hold current combination of indexes
#  body       - code to execute for each combination
proc chooseloop {indexcount itemcount indexvar body} {

    if {$indexcount > $itemcount} { 
      error "More indexes than items"
    }

    if {$indexcount == 0} { return }

    set indexes {}
    for {set i 0} {$i < $indexcount} {incr i} {
       lappend indexes $i
    }

    set maxindexval [expr $itemcount - 1]

    while {1} {
 
       # make new body that sets indexvar first
       set newbody "set $indexvar {$indexes}\n$body"

       # do this iteration
       uplevel 1 [list eval $newbody]

       # find incrementable index
       set found no
       for {set i 0} {$i < $indexcount} {incr i} {
          set index [lindex $indexes end-$i]
          set thismax [expr $maxindexval - $i]
          if {$index < $thismax} {
             set found yes
             break
          }
       }

       if {!$found} { break }

       # increment this index and set all following ones
       set incrindex [expr ($indexcount - 1) - $i]
       set precedingval [lindex $indexes $incrindex]
       for {set j $incrindex} {$j < $indexcount} {incr j} {
          lset indexes $j [expr $precedingval + 1]
          set precedingval [lindex $indexes $j]
       }
    }
}

Now to get my 3 level loop, I can call like this:

chooseloop 3 5 indexes {
    set str ""
    foreach index $indexes {
       append str "[lindex $items $index] "
    }
    puts $str
}

In order to do 3, then 4, then 5, I can call like this:

for {set i 3} {$i < 6} {incr i} {
    chooseloop $i 5 indexes {
       set str ""
       foreach index $indexes {
          append str "[lindex $items $index] "
       }
       puts $str
    }
    puts "--"
}

The output of that last one is:

apple orange banana 
apple orange grape 
apple orange strawberry 
apple banana grape 
apple banana strawberry 
apple grape strawberry 
orange banana grape 
orange banana strawberry 
orange grape strawberry 
banana grape strawberry 
--
apple orange banana grape 
apple orange banana strawberry 
apple orange grape strawberry 
apple banana grape strawberry 
orange banana grape strawberry 
--
apple orange banana grape strawberry 
--

Things That Don't Work vs Things That Do

I've never been completely happy with my temperature logger. It's a bit fragile in the sense that if anything at all goes wrong, and there's no way to tell that at the time, I lose the entire run. I lost a run Memorial Day weekend.

Instead of storing the measurements on the Arduino, I'd like to instantly beam them onto my computer far inside the safety of the house. That way I can track things realtime as well as be assured that I have them. Coincidentally, for my birthday, I got both another Arduino¹ and Making Things Talk.

The book describes a great number of schemes to make microcontrollers talk to each other and to computers. You can use wireless networking, bluetooth, XBee, etc (I have only the vaguest notion what some of these are). Naturally the easiest protocols require the most expensive hardware. I only need one way, slow communication, so I got a simple RF module.

Claim:

It works just like a serial port! Just connect the transmitter to the TX pin and the receiver to the RX pin! It Just Works(tm)!

Reality:

No.

Perhaps my unit was faulty. I found many tutorials and guides across the internets and while results varies, I can't ever really say it worked. I did see data appear for a short time, but mainly what I saw was noise. Or nothing at all, which is even less explicable.

Last night I had a brainwave. Or brainstorm. Something happened to my brain and it resulted in an idea. Why not use a wireless laptop as the go between? The kids have these OLPC dealies. The laptop has a USB port and does WiFi. I have a WiFi router (specifically purchased, used, to work with these laptops). About 30 minutes and 10 lines of Python later, I was reading values from /dev/ttyUSB0 and sending them out over a socket to my desktop to another 15 minutes and 20 lines of Python.

The guts of the entire scheme are already there. But with so much success so fast, I'd like to add features. For instance, instant graphing of values on both ends. A protocol so that the laptop knows if there's been an error and can tell me, out in the field. When I have more than one sensor, I'll need a way to indicate which sensor had what value. It'll be like a complete Science Sensing Station!

¹If you are at all interested in robots, sensors, controlling stuff with computers, electronics or just plain messing around, I highly recommend the Arduino. That SparkFun item is all you need, assuming you have a USB port (and possibly a cable). Well....you may also need some external electronics, depending on what you want to do. LEDs, resistors, motors, etc.

The Etching Calculator [EDIT]

A lot of things, many of them new to me, went into this project. We have "regular" programming, "device" programming, a communication protocol, stepper motor control, motor mounting, power supply design and the mathematics of drawing an optimal line on a pixelated display. Some comments on each.

Mounting

I originally thought this was going to be the hardest part. "The rest is just sitting at my computer desk and either typing or handling tiny pieces of electronics" was my opinion. In fact, I just cut a couple spacers and then improvised mounting plates from....I don't know what that stuff is. It's like countertop covering. In any case, this part took maybe 45 minutes. It helps that one vital component of the mount is masking tape.

Connecting the steppers to the knobs went through some iterations. The motors had gears on the ends, but of course the EAS isn't geared. I tried various ways of coupling one to the other, but wasn't satisfied. (This turned out to be a power supply problem, which I talk about below, but I didn't know that at the time.) In the end I managed to remove the gears--they are just press fit, so you can knock them off with a nailset and a hammer. The shafts of both motors and the EAS were almost all the same size, which in turn was just a tiny bit bigger than the internal diameter of some plastic tubing. I just cut a short length as a sleeve and voila.

Stepper Motor Control

Physical Computing was invaluable. In fact, reading about how to control a stepper was what gave me the original idea of controlling an EAS¹. (The guts of that section are online.) I originally tried to do the entire thing with totally generic components, i.e. plain transistors, but I soon gave that up. I unbent enough to use 2 dual H-bridges. Still generic, but you can't get them at Radio Shack (but what CAN you get at Radio Shack?). This compacts the wiring and anyway the motors need more current than a regular transistor can switch.

If this were a real product, I would definitely build/buy a stepper control board. Finer control isn't an issue, but sweet mother of crap this thing is loud. I think a board can ramp the amperage up and down to give a smoother movement that won't shake the house down.

"Device" Programming

The Arduino libraries include an object-oriented Stepper control library, but it wasn't really suited to what I was doing. The most basic fact it cared about was the RPM. The most basic fact I cared about was how many steps to take. So I wrote my own SingleStepper library. That makes me sound alphanerdy, but seriously, it was just a matter of copying and tweaking the existing library.

Another reason for writing my own was that the Stepper lib left the current on even when the motor wasn't turning. That's great if you need the torque to stay on, but non-great if you have a limited budget of amperage. So my library also turns the power on only long enough to move the motor, then turns it back off.

Communication Protocol

The stock Arduino serial comm library only supports reading a byte at a time. WTF ARDUINO ? Naturally I need to send coordinates larger than 255. The solution is conceptually not too difficult: Send a two-byte int a byte at a time and reassemble on the other end. This actually took a couple days to implement, though, because Python (on the other end of the wire) isn't geared towards working with binary data and then there's the question of negative numbers, twos complement, endianness, etc.

Also, in the case where a lot of coordinates are being generated very quickly, the internal buffer can overflow and the EAS goes haywire. So each coordinate has to be ACKed by the controller before the next is sent.

Line Drawing

Here's another place where I didn't go 100% from my own bootstraps. I actually did start deriving this myself, but soon realized that there were going to be special cases and stuff and I wasn't interested in debugging those. Instead, I just adapted a classic algorithm. I didn't use any of the optimizations on that page, since they are more for a digital display than position control. I did make one optimization of my own, though, which was to not move each motor a single step at a time if I could take 5 steps with one and then 1 with the other.

Theoretically, one could turn both motors on at the same time but at different rates to draw diagonal lines. But even if I had the electric power to do that it's just too hard to attempt.

"Regular" Programming

This is so dead simple that it's really not that interesting, but just for completeness: Generate a series of coordinates (either by hand typing in your own or using some equation) and send them out the serial port.

Actually, I should explain that a bit. I chose to implement this as a display-like device. You give it a coordinate pair X,Y and it moves there. The Arduino handles everything after being handed the values. So for instance the sine wave is being calculated as a series of points in Python on my computer and then sent over to the microcontroller for plotting.

Power Supply

Of these all, the one that I figured out last was the power. The EAS isn't really made with computer control in mind. The controls are surprisingly sticky. At first I thought the coupling between motor and EAS was slipping, but I eventually eliminated that. The power supply I bought is rated up to 1.5A, but only puts out 5V, so the motors only drew about 700mA. Turns out that wasn't quite enough to consistently turn the knobs. By bypassing the power supply, I was able to feed 1A directly to each motor (one at a time) and that was enough.

It may still be a little short, though, because I still get the occasional glitch. But I don't have a wall wart that puts out more than an amp at more than 8V.

Cost

The steppers I got out of a broken inkjet printer. (I really lucked out on that, I later realized. Two other inkjets I disassembled had steppers but they were tiny.) I already had the mounting stuff and the Arduino, as well as wires, resistors, etc. I had to buy the H-bridges, the power supply, a heatsink and some power resistors. That probably adds up to $20 or $25. But I can and will reuse it all, especially the power supply, which was the most expensive single purchase.

Oh yeah, and I had to buy an EAS. But one of my design goals (as well as an instruction from my seven year old) was to not alter it beyond being used by humans afterwards. So I consider that a capital investment as well.

¹Gave me the idea, but I wasn't actually spurred to do anything until I saw the EAS clock. The auto-erase functionality of the clock would be really nice to have, but I'd like to point out that the ability to draw curves is even nicer.

Per request, here's a closeup of a diagonal line. You can't see the "pixels".

That said, you actually can see the "pixels" in some curves. I think that's because of the (mathemetical) stepping involved in going from floating math to integer.

The Parable of the Parallel Parabola

OK, so....man, I wish I'd been detailing every little step so I wouldn't have to regurgitate it all up in a huge mass. I'll try to make this short.

First of all, I used my calculation to make a simple parabolic reflector. I just plotted it out on graph paper and then set a few nails as guides to hold the mirror in place. This actually worked really well. (Even more surprising in light of how poorly the (first!) oven-formed one came out. More about which below.)

The one on the right has a black dot where I pre-calculated the focus to be, the one on the left is just a different focal length.

Now then. Having a single strip mounted with nails isn't that useful to me, so I want to mass produce these. Can't use the nail thing as a form since it'll just bend unevenly. I spent quite a few days trying to figure out how to make a jig that would cut a perfect parabola, but it was too hard (I still have some ideas on that, though, but that's another 2 or 3 posts). (And before you tell me, I know all about the T-square and string method of drawing one.) I eventually decided to just freehand follow a line.

So I had my shop assistant cut a parabola for me and I sandwiched the mirror in there. (My shop assistant is my father-in-law down the street who actually owns a bandsaw.)

(Other item of note: I originally wanted to have the mirror soften and sink down into shape, but that creates alignment problems. Instead I clamped the bendy strip cold. But that means it's hard to tell when I've reached temperature. So I put a probe down into the coldest part of the thing. The tip of the temperature probe is resting right on the mirror, so when that gets up to ~210°F, I can stick a fork in it. This takes like 2 hours--wood is a really great insulator, unfortunately.)

(Oh also: You can't see it, but there's a little alignment peg sticking out of the convex part of the form. There's a corresponding hole in the concave part so it can stick through. There's also a hole in the middle of each mirror. If I put each mirror on the peg, then after I'm done with all of them, I can line them up perfectly. So clev.)

The result: Not so great.

How could that possibly be? How could a few nails hastily thrown together at a few points make a better parabola than a careful, full-contact form?

Then a phrase floated up out of the darkness¹. The curve parallel to a parabola is not another parabola. Just think about that for a minute. If you have a parabola and you want to make a curve parallel to it, you can't just take the same parabola and shift it up. Nor can you use some other parabola. (Read the gories yourself, it's pretty cool. If you like that sort of thing.)

So if you cut a parabolic form and sandwich it around a mirror, FOR EXAMPLE, then you are probably going to get the wrong shape because the two halves want to be parallel (i.e. separated by the thickness of the mirror) but can't. Wellity wellity wellity.

I took the equations in that paper and made a little program² that would generate an SVG file of the shapes I wanted. Now I can take those back to my shop assistant and have him cut it out again.

(Note to anyone who actually reads this far, runs the program, examines the output and starts wondering: The curves aren't really all that different. I think the issue isn't so much that the curve is wrong, but that the poor alignment doesn't provide even pressure across the entire mirror. So it ends up wibbly-wobbly rather than smooth. Then again, the freehand wood parabola isn't all that smooth either, so maybe THAT'S the source of the error. The nail method at least creates a smooth curve, even if it isn't mathematically perfect.)

¹I think it came from Practical Conic Sections, a really rip-roaring tale that I've been reading to the kids at bedtime. But seriously, it's very clear and pretty practical.

²

#!/usr/bin/python

# p1 and p2 are parallel to the parabola, i.e. a constant distance
# away *along the normal to the parabola*.

# For a curve C with generated by the function y = f(x), the parallel
# curve C' is given parametrically by:

#                 y'
# X = x - k -------------
#           sqrt(1+(y')^2)
#
#                 1
# Y = y + k -------------
#           sqrt(1+(y')^2)

# where k is the distance of the parallel from the curve.

# For derivation, see "The Curve Parallel to a Parabola is not a
# Parabola" by F. Max Stein.

import math

print '<?xml version="1.0" standalone="no"?>'
print '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"'
print '"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">'
print '<svg xmlns="http://www.w3.org/2000/svg"'
print '    width="8.5in" height="14in">'

focallength = 2.5
a = 1/(4.0 * focallength)
mirrorwidth = .125

vertoffset = 7
horizoffset = 2
phorizoffset = 2
prevx = 0
prevy = 0
pprevx = 0
pprevy = 0
first = True
x = -5.5
while x <= 5.5:
    y = a*x*x
    px = x - (mirrorwidth * 2 * a * x)/(math.sqrt(1 + (2*a*x)**2))
    py = y + (mirrorwidth * 1)/(math.sqrt(1 + (2*a*x)**2))
    if not first:
        print '<line x1="%.2fin" y1="%.2fin" x2="%.2fin" y2="%.2fin" style="stroke:black;stroke-width:2"/>' \
              % (prevy+horizoffset, prevx+vertoffset, y+horizoffset,x+vertoffset)
        print '<line x1="%.2fin" y1="%.2fin" x2="%.2fin" y2="%.2fin" style="stroke:red;stroke-width:2"/>' \
              % (pprevy+phorizoffset, pprevx+vertoffset, py+phorizoffset,px+vertoffset)
    prevx = x
    prevy = y
    pprevx = px
    pprevy = py
    x += .125
    first = False

print '</svg>'

Your Favorite Geek Desk Toy Sucks

I've seen these binary clocks around the office. They are fairly cool, but they fail to please in one important way: Each decimal digit is represented separately. 14 seconds is represented as a binary 1 and a binary 4, rather than a binary 14. Granted, reading 6 bits depicting 0-59 seconds is a little harder than the 4 bits required for 0-9. But is ease of use really the primary concern of a binary clock?

MISSION: Build this clock the right way. Namely, 6 bits for the seconds, 6 bits for the minutes and 5 bits for the hour (or maybe 4 bits for the hour with 1 bit for AM/PM). (Another idea would be a straight-up 17 bits for the 86400 seconds in a day, but seriously.)

Now then. I know there are clock chips out there. And it is probably possible to do this using hardware only, say with a 555. But I'm a dumb programmer, so everything looks like a Turing-complete problem to me. Plus I already have an Arduino. So that's the medium of choice. Using an Arduino, some LEDs and resistors and pure force of will, I'm going to make this work.

But there's a problem already. My design calls for 17 LEDs. The Arduino only has 14 output ports¹, 2 of which I can't use because they are special. The solution to this problem is multiplexing. The basic idea is that you use X/Y coordinates to address each LED, Battleship-style. So for MxN LEDs, you only need M+N ports.

Let's say I want to light up the LED labeled 0,0. I need to apply positive voltage to A (the left column) and negative to 1 (the bottom row). B and C should be low while 1 and 2 should be high to "push the wrong way" against the remaining diodes.

But now there's another problem. Let's say I want to light up both 0,0 and 2,2. I apply positive to A and C and negative to 1 and 3...and I get all four corners lit up. Long story short, it is also necessary to employ a spot of subterfuge. If I want 0,0 and 2,2 lit up, I have to do them one at a time, but switch back and forth so fast nobody's the wiser.

And finally, there's the little matter of the clock function itself. There isn't an API call for that exactly, but the underlying chip supports interrupts. I basically just copyandpasted the timer code from elsewhere and then added a long comment explaining it to myself, probably incorrectly.

Grainy video (the ticking is an amazingly coincidental loud clock in the same room):

Somewhat less grainy still shot:

The code:

#include <avr/interrupt.h>
#include <avr/io.h>

#define NUMPOS 6
#define NUMNEG 3

int pos[NUMPOS] = {9,8,7,6,5,4};
int neg[NUMNEG] = {12,11,10};

int i = 0;
int j = 0;
int k = 0;
int lastpos = 0;
int lastneg = 0;

int isr_counter = 0;
int oldsecond = 0;
volatile int second = 0;
int seconds = 0;
int minutes = 31;
int hours = 13;

/*  
   Here's how I think this works.  The Atmega168 clock runs at 16MHz.  
   The "prescaler" divides that down.  In this case, it clicks at 2MHz.  
   Each time it clicks, it increments at 8 bit register by 1.  The register
   overflows after 256 clicks.  That overflow is the interrupt we receive.

   2000000 clicks/second divided by 256 clicks/overflow = 7812.5 overflows/second.
   So if I could count 7812.5 overflows, I know a second has elapsed.  I can't
   find .5 of an overflow, so I should really use the /4 prescaler.  But 
   a) that uses more power and b) I can't figure out what bits to set to do that.  
*/

ISR(TIMER2_OVF_vect) {
  isr_counter++;
  if (isr_counter > 7811) {
    second++;
    isr_counter = 0;
  }
};  

void SetupTimer2(){
  //Timer2 Settings: Timer Prescaler /8, mode 0
  //Timer clock = 16MHz/8 = 2Mhz or 0.5us
  //The /8 prescale gives us a good range to work with
  //so we just hard code this for now.
  TCCR2A = 0;
  TCCR2B = 0<<CS22 | 1<<CS21 | 0<<CS20;

  //Timer2 Overflow Interrupt Enable
  TIMSK2 = 1<<TOIE2;

  //load the timer
  TCNT2=0;
}

void setup() {
  for(i = 0; i<NUMPOS; i++) {
    pinMode(pos[i], OUTPUT);
  }
  for(i = 0; i<NUMNEG; i++) {
    pinMode(neg[i], OUTPUT);
  }

  for(i = 0; i<NUMPOS; i++) {
    digitalWrite(pos[i],LOW);
  }
  for(i = 0; i<NUMNEG; i++) {
    digitalWrite(neg[i],HIGH);
  }
  
  Serial.begin(9600);
  SetupTimer2();
}

void showXY(int col, int row) {
  digitalWrite(pos[lastpos],LOW);
  digitalWrite(neg[lastneg],HIGH);

  digitalWrite(pos[row],HIGH);
  digitalWrite(neg[col],LOW);
  
  lastpos = row;
  lastneg = col;
}

void loop() {
  // time changed, so readjust all the details
  if (oldsecond != second) {
    if (second > 59) {
      second = 0;
      minutes++;
      if (minutes > 59) {
        minutes = 0;
        hours++;
        if (hours > 23) {
         hours = 0;
        }
      }
    }          
    seconds = second;
    oldsecond = second;
  }

  // seconds is column 2 and has 6 bits
  k = 2;
  for(j=0; j<6; j++) {
    if (seconds >> j & 1) {
      showXY(k,j);
    }
  }

  // minutes is column 1 and has 6 bits
  k = 1;
  for(j=0; j<6; j++) {
    if (minutes >> j & 1) {
      showXY(k,j);
    }
  }

  // hours is column 0 and has 5 bits
  k = 0;
  for(j=0; j<5; j++) {
    if (hours >> j & 1) {
      showXY(k,j);
    }
  }

}

¹Possibly not true. I found one post that said the 6 analog in ports could be used as digital out. But even if multiplexing isn't strictly necessary for this project, it would be for a larger one.

You Program My Back, I'll Program Yours

If you are a math/science/computer nerd and you have a child, you have undoubtedly wondered how you can teach your child programming. I googled for such a thing more than once and found the usual suspects: BASIC, LOGO, etc, etc. The free ones were all half-finished or too hard, the good ones were all expensive or geared towards classrooms.

I tried teaching Number One Son (8 years old) some pseudo-codey stuff to do simple math problems and learn about loops. He enjoyed that, but we didn't get very far and I always had to be the virtual machine to check if his program ran.

However, MIT has recently come up with something that absolutely rules--Scratch. And it's free!

Scratch is graphical. You drag the little components around to assemble a program. For instance, to make a loop, you drag your components into a loop widget, which wraps around it like a vice. If you want to construct a conditional, you get out the "if" widget and drag and drop logical/mathematical conditions in from the toolbox. Just fill in the blanks and go.

The GUI isn't just for show, either. You don't feel like you are using the mouse to write a program, you feel like you are literally assembling a physical object. And it eliminates syntax errors, which is a major deal in the under-13 crowd. Furthermore, the graphical programming language ties right in to the very graphics-oriented programs Scratch is targeted towards and children love. Creating and animating sprites takes just a few clicks. Object collision is just a matter of checking if two colors are touching. And this is all clearly presented enough that an 8 year old can (and has) figured most of it out himself.

I think he learned more about programming in 2 days with Scratch than he did in all the previous years of my bumbling explanations. He goes off and works on a program for a while and then will come to me with a question about how to do something. And they are pretty sophisticated problems (considering his age), such as how to cycle through sprite costumes and wraparound at the end or how to keep various sprites in sync. With the concrete example of his non-working program providing the motivation, the explanations of modular arithmetic or semaphores stick much better.

So far he's created programs that simulate a robot in a maze, animate a rocket flying to the moon, teach the alphabet to his two-year-old sibling and even one generic drawing program with adjustable pen size and color. All 100% on his own.

Windows and Mac only, but:

1. They claim they'll have a Linux version out "before the end of 2007".
2. The usefulness, fun and polish of Scratch is more than worth setting up an old PC with Windows.

It's possible to upload your program to share with other kids, but we haven't tried that yet. Videos of Scratch in action..