Friday, May 13, 2011

My 0.015 minutes of fame on CNN

I recently wound up on CNN for a couple seconds doing some Arduino hacking as part of a segment on Google's workshops. Click the image for the full video. If you don't want to watch the whole thing, I appear at 1:00 and 1:39.

Ken Shirriff on CNN

For those who want technical details, I hacked together the following quick sketch to generate the interesting patterns you can see on the oscilloscope:

void setup()
  pinMode(4, OUTPUT);
  pinMode(5, OUTPUT);

int state = 1;
int count1 = 0;
int state2 = 1;
int count12 = 0;
int max1 = 20;
int max2 = 200;
int t = 0;

void loop() {

  if (count1-- <= 0) {
    state = 1-state;
    digitalWrite(5, state);
    count1 = max1;
  if (count12-- <= 0) {
    state2 = 1-state2;
    digitalWrite(4, state2);
    count12 = max2;

    if (t++ > 20000) {
      max2 -= 1;
      if (max2 < 1) {
        max2 = 500;
      t = 0;
This sketch manually generates two square wave output with periods determined by max1 and max2. The frequency of the second varies occasionally (controlled by the loop with t). I used simple R-C filters on the outputs to turn the square waves into roughly triangular waves, and then fed this into the X and Y inputs of the oscilloscope. The result was constantly-varying Lissajou-like patterns.

I should point out the outputs generated this way are rather unstable because many thing can interrupt the timing loop. The above code is provided just in case your are curious. I don't recommend using this approach for anything real; using the PWM timers would yield much cleaner results.

Anyone have other ideas for easy ways to generate cool oscilloscope patterns with an Arduino?

Friday, May 6, 2011

My Knuth reward check

I attended a very interesting talk "All Questions Answered" by the famous computer science professor Don Knuth in March, where he talked about many things, including his new book.

The talk inspired me to read The Art of Computer Programming, Volume 4A: Combinatorial Algorithms. As he described in the talk, he gives a reward check (for 1 hexadecimal dollar) to anyone who finds an error in one of his books, so I set myself the goal of finding an error in the book while on vacation.

After a lot of study, I thought I'd found an error in a diagram, but then I realized I was confused. Next, I found a blatant error in an appendix, but that error had already been discovered and was listed in the errata. Finally I found an error on page 574 that I hoped hadn't been found yet and sent it off to Professor Knuth.

I was delighted to receive my reward check today, which Wikipedia calls "among computerdom's most prized trophies". That's a big exaggeration but nonetheless, I'm happy to get one. Note that the check is from the fictional Bank of San Seriffe to avoid check fraud problems from all the images of his checks on the web.

My Knuth TAOCP reward check

As for the book itself, it's interesting even if you're not after a reward, although very challenging to read. Volume 4a describes combinatorial algorithms, including more ways of computing permutations and combinations than you can shake a stick at. It also has an extensive discussion of BDDs and ZDDs, which are newish data structures for representing sets. The section on bitwise tricks and techniques is interesting if you like HAKMEM-style tricks such as reversing the bits in an integer through a short sequence of incomprehensible operations.

I have to admit that trying to find an error in a book is a strange vacation goal, but I'm glad I succeeded and Knuth's book taught me some interesting algorithms in the process.

P.S. I was very surprised to see this article on the front page of Hacker News. To answer the questions there and below, the error I found was in volume 4a page 574 (as the memo line on the check shows). The solution to exercise 67 on that page says a particular circuit uses 6 ANDN gates, which I thought should be NAND gates. It gets a bit more complicated because Knuth was referring to the ANDN op code for MMIX, but there was still a mistake with and-not versus not-and. (The other error I noticed was n choose k on page 824, but I checked the errata and it had already been found.)