John Myles White: Die Sudelbücher

To say it once and for all: using ” as the escape character for ‘ within single-quoted strings is a poor decision in language design.

As part of my current strategy for delaying my return to the ongoing growing pains of learning probability theory, I just installed the most recent best of Firefox 3.1. Its speed really is amazing, so I would recommend it to anyone who can afford to risk having their browser crash once in a while. It renders most of the pages I frequent substantially faster than Firefox 3.0.

Today I started reading the Ruby Snips website, which has a pretty good sample of interesting snippets of Ruby code on it. I was particularly intrigued by the following snippet from a post on Prime Numbers dating back to March 23rd, 2007:

1
2
3
4
5

class Fixnum
  def prime?
    ('1' * self) !~ /^1?$|^(11+?)\1+$/
  end
end

At first, I was convinced this code was broken. Before I had given much thought to the algorithm, I was ready to assume that the “prime?” name was a misnomer: I assumed the code was actually testing for members of a specific class of palindromes. After a minute or two, I pieced together what was really happening when testing a number:

1. The number, n, is expanded into a string of 1’s of length n.
2. The string of 1’s is testing using a regex with back-references that finds the presence of a repeated divisor, a technique that works because a string of length a * b = n is composed of b copies of a string of length a.

At that point, I began to marvel at the simplicity of the algorithm relative to the obscurity of the code. And while I was so amazed by this, it occurred to me: this is an absolutely terrible way to test for primality. Because you have no control over the loop bounds for the regex, you effectively test every number up to n as a possible divisor if n is a prime. But you really only need to test up to the square root of n to determine if n is prime. So your code runs for the square of the time it should run. And the expansion of n into a string, at least theoretically, requires exponentially more space than an integer expressed in binary would. This seemed like one of the worst possible ways to test for primality I had ever seen.

Still, I wanted to verify this empirically as well as theoretically, so I typed in

1

399839483.prime?

during an IRB session. The CPU and memory usage were absurd for a primality test on such a small number. I didn’t even bother letting the code complete after a few seconds of the watching interpreter hanging there, silently wasting CPU cycles. In contrast, the simpler, clearer code,

1
2
3
4
5
6
7
8
9
10

class Fixnum
  def prime?
    (2..Math.sqrt(self).to_i).each do |i|
      if i * (self / i) == self
        return false
      end
    end
    return true
  end
end

runs fairly quickly.

The lesson I think everyone should take from this is a simple one: don’t be clever when writing code. At the very least, don’t be clever in the way the author of this snippet was. Your code is likely to end up being unclear, slow and wasteful with memory.

Perhaps I should be clearer about the problems of cleverness. Clever code is a mistake; clever algorithms are wonderful. Quick sort is a clever algorithm that always confuses me until I think carefully about it — and then I marvel at its superiority over other less efficient sorting algorithms; this snippet is a mediocre algorithm written in a style of code that’s needlessly confusing.

My attempts to work this weekend on updates to a MySQL database-driven CGI application I wrote a few years ago were all delayed by a recurring problem during the installation of the DBD::MySQL module on my Powerbook. I finally solved the problem a few minutes ago after reading several articles, particularly one from JayAllen.org. In the interests of saving others’ time, here is the solution I came upon to getting DBD::MySQL to run on Mac OS X Tiger 10.4.10 with Perl 5.8.6.

The first set of problems I had were caused by the makefile for the CPAN module trying to access a non-existent library directory, /usr/local/mysql/lib/mysql. To solve this problem, I created a symbolic link to the missing directory:

1

sudo ln -s /usr/local/mysql/lib /usr/local/mysql/lib/mysql

After this, I got a new batch of errors about password problems during the test phase. The module was attempting to log in as root to the MySQL server without giving a password. The solution was to temporarily open the MySQL server with root requiring no password:

1

sudo mysqld --skip-grant-tables -u root &

These two steps, discovered after considerable bug-tracking, solved all of my problems. Hopefully this can save other Tiger users a great deal of time.