Donnie’s Blog

Lately I have been tinkering with a simple little 3D graphics program in my spare time. To support my various graphics and math projects I have put together a simple C++ math library including matrices, vectors, and the like. My matrices are stored in row-major order, like most matrices in C/C++ programs, but OpenGL uses column-major order. “Simple,” I think, “I just need to transpose my orientation matrices before passing them to OpenGL!”

But it just wouldn’t work. See if you can figure out why:

  template<class T, int dim> class SquareMatrix {
    ...
    /** Transpose the matrix. **/
    void transpose() {
      for (int r = 0; r < dim; r++) {
        for (int c = 0; c < dim; c++) {
          // Diagonal elements don't need transposing!
          if (r == c) continue;

          T tmp = getElem(r, c);
          setElem(r, c, getElem(c, r));
          setElem(c, r, tmp);
        }
      }
    }
    ...
  };

Last night I was looking for interesting programming problems, and I came across this page about the Möbius Function. It’s a pretty simple idea, although I have no idea how August Möbius came up with the idea in the first place.

Given a positive integer n, the Möbius function μ(n) returns:

• 0 if the number is a multiple of a square
• -1 if the number has an odd number of distinct prime factors
• 1 if the number has an even number of distinct prime factors

The n = 1 case is a special case; μ(1) is defined to return 1.

I thought this would be a fun little problem to play around with; it’s all about generating the list of prime factors for the input value. A number is a multiple of a square if it has any duplicate prime factors; for example, 12 = 2 × 2 × 3, so it is a multiple of a square, and μ(12) = 0.

An interesting little related problem is to find runs of numbers for which μ(n) is 0. For example, the first run of three multiples of squares is {48, 49, 50}. The first run of six square-multiples starts at 22020.

So, I wrote a Scheme program to implement the Möbius Function, and to find runs of square-multiples; here it is if you want to take a look! It was pretty fun, although the program starts to get annoyingly slow when hunting for runs of 7 or 8 square-multiples. I would have to upgrade to a much faster language if I were going to do something like that. Or perhaps there’s something I can improve in my implementation…

The summer break is finally here, and I for one am very excited about this summer. This year I have a SURF student helping me out with the implementation of my “educational database system” in Java. The working name is currently NanoDB, although I am certainly open to other suggestions.

(more…)

A few days ago there was this Slashdot article about a serious Linux kernel security hole. Since I was running a version of Linux that had the issue, I thought I had better patch it on my server ASAP.

My machine basically has nobody on it, so I am really not worried about somebody using the exploit directly. But, I do have a number of network services, like my mailserver, webserver, SSH server - and if any of those has a vulnerability, I sure don’t want somebody using that to get root access on my box!

So, last night I manually patched my kernel source, rebuilt my kernel, and rebooted the machine. It was exciting and nerve-wracking; since it’s been so long since I built a kernel myself (2000? 2001? It was at DALi I am sure…), I didn’t know if I would get it right! Then there’s the fact that I am running RAID1 on my boot partition, and I wasn’t sure how the kernel update would go with that.

But, everything went fine. The machine rebooted fine, and when I tried the exploit on the patched system, nothing bad happened. All my services started back up without a hitch.

It was kind of exciting!

Saturday, November 10 was the ACM regional programming contest. Caltech won yet again… Go Caltech!

This year was definitely one of the least intentional wins. There was little interest in an ACM programming contest track for CS11, so we just didn’t have one. Then, two weeks before the contest was scheduled, some all-star students expressed interest in going, so we arranged it. And they won! Caltech rocks.

Anyway. Hopefully we won’t do it this way ever again. Next year I want to really try to drum up interest in the contest and actually get 3 or 4 teams out there. But at least we were able to land the win this year!

I just added a new programming note about a project I have been tinkering with lately. The project is a Buddhabrot image generator. Right now I am still working on generating some images so I will add those tomorrow, but tonight I wrote up a page about some of the interesting things I learned from this little project. So, check it out. Hopefully you will find it interesting too.

One of the software projects I have been working on over the summer required the software to be built for MacOS X, but not just any old version - it had to be built for MacOS X 10.3.9, and it had to run on the PowerPC.

This was an interesting challenge. Especially since I didn’t have a Mac!

(more…)

This is an interview question I had at Microsoft, from when I was interviewing for my very first internship. That would have been way back in early 1996.

“You are given an integer n, and you need to write a function to count how many bits in n are set to 1.”

As most reasonably savvy programmers would do, I wrote a function that shifts n to the right, counting the times that the least-significant bit is set to 1, until n is 0. Something like this:

  int countBits(int n) {
    int count = 0;
    while (n != 0) {
      if (n & 1)
        count++;

      n = n >> 1;
    }

    return count;
  }

In general, this function will take O(b) time to complete, where b is the bit-width of n. This is fine; it’s a constant, so we are all happy with that.

But it turns out that there’s a faster way!

Question 1: Do you know what the faster way is?

Question 2: Do you know how it works?

I will admit up front that my interviewer showed me, way back in 1996, the faster way. But I just figured out how it works this weekend.

(more…)

I wrote a fun little program for computing the closure of a set of functional dependencies this week. Functional dependency theory is the foundation for Third Normal Form and Boyce-Codd Normal Form, and a variety of other neat things you can do with relation schemas. An interesting and powerful set of ideas, but I think that most database designers don’t really use functional dependency theory so much. But it is fun to play with!

Anyway, a lot of the problems are very simple in that they work with abstracted schemas, such as R(A, B, C, D, E), and if you take a set F of functional dependencies against the relation R, you would like to compute things like “What is the closure of F?” or “What is a canonical cover of F?” Then you can answer questions like “What are the candidate keys of R, given F?”

(more…)

I have been thinking for a long time about what language would be best to use for implementing a relational database system. Keep in mind that this is not for any serious use; I want to implement this as an educational platform for the students in my database systems course, so that they can have some of the grungier details all nailed down for them. So, a clean, modular architecture is the number one focus, and performance is a rather distant concern.

(This is also why I have generally ruled out open-source database systems as a teaching aid. Although most open-source databases are quite impressive in their capabilities and performance, they just don’t have the modularity and the simplicity that an effective teaching tool would need.)

(more…)