Bug Report Fallout

It seems my bug report is causing a bit of a stir within Microsoft. As Georgeo Pulikkathara writes,

This has certainly gotten the attention of folks internally wondering how come Ken didn't use the official bug reporting system.

It's mostly because Ken is a lazy sot. Like I wrote before, I looked around the support website for a few minutes but I couldn't find anything resembling an "official bug reporting system".

When I typed "report bug" into the search box it returned a link to some tips for reporting bugs in FoxPro and a plethora of, what else, bug reports.

Amongst all the other links on the support page, I honestly didn't notice the Contact Us link, but even if I had found the bug report page I very much doubt that I would have called the 800 number, which I can only guess (based on my experience with the call centres of other companies) would involve a 10 minute wait to get through to the operator, followed by 15 minutes of transfers to various people until I finally ended up at the person who can actually do anything about it. And besides, how am I going to send a screenshot over the phone?

I do realize there is a remote possibility that Microsoft has an exceptional customer support service and would get my report logged in less than a minute, but why take the risk? The bug is a mere nuisance. It has no effect on anybody but anal spelling-nazis like me. I could afford to have the report go ignored, though it would bother me in irrationally profound ways every time I saw the typo (but that's my problem, not Microsoft's)

So I guess it was the combination of the low importance of the bug, and the expectedly high cost of reporting it through the official channels that led me to post it here.

I'm genuinely surprised that nobody has reported a bug like this before. It seemed like a very natural choice to report it this way. I'm really not used to being the first to do something.

And my web server isn't used to seeing the kind of traffic this has generated (Report Magic graphs increasing dates from right to left for some unfathomable reason):



I hope Go Daddy will hold up after everybody returns from their long weekend getaways.

Block Diagram Progamming Comes To DSPs

According to this EDN article by Warren Webb, National Instruments has just released a LabView module that can generate machine code for the Texas Instruments C6711 or C6713 from a functional block diagram of a program.

To Engineer Is Human

I just finished reading Henry Petroski's To Engineer Is Human: the Role of Failure in Successful Design. I liked it.

One of the central themes of the book is that there is much more to learn from the failure of a design than from the success of one. When a structure collapses, the wreckage can be studied, and the cause identified, providing future designers with a definite mode of failure that they can plan to avoid and check for in their own designs.

Another major theme is an analogy of the design process as a scientific method. In science, a hypothesis can be disproved by experimentation, but it cannot be proven. If an experiment fails to disprove an hypothesis, it merely adds supporting evidence to it. The hypothesis may be incorrect, but no experiment has yet exposed its failure. Similarly, a design can be found lacking by analysis, but there is no guarantee that one which passes all the known analyses will, in fact, stand.

There is an oft-quoted saying among computer scientists from Dijkstra that makes a similar point: "Program testing can best show the presence of errors but never their absence."

Ken's Bug Reporting System

When I arrived at the office yesterday morning, I was greeted by the following message box.



Apparently our IT staff had applied some patches to my machine overnight and I needed to reboot. Fine. Whatever. I'm used to that with Windows. I've learned to accept that I occasionally have to waste 15 minutes of my day reconstructing my desktop after a reboot the I didn't initiate.

What bothered me was the typo in the message box. Successfully is spelled with three Ss, not two. I noticed the typo ages ago and every time I see it I get more annoyed by it. When I saw it yesterday, I'd had enough. I decided I was going to do something about it.

So I went to the Microsoft Support site looking for somewhere that I could report a bug. I poked around on the website for a few minutes, but quickly gave up. This is a bug that is going to take a developer two minutes to fix. Why should I put more effort than that into reporting a bug?

I finally decided to report the bug here instead of Microsoft's award-winning support site, in the hopes that some clueful Windows Update developer with a PubSub feed might happen by it and spend two minutes fixing it. Are you that developer? Please fix it.

Update: After PubSub founder, Bob Wyman, wondered whether anybody from Microsoft had seen this posting, Robert Scoble confirms that they have. Cool! It's working!

Solution to SICP Exercise 1.23

Solution to Exercise 1.23:

Here is the defintion of a next procedure.

(define (next x)
  (if (= x 2) 
      3
      (+ x 2)))

To use it, we need to modify find-divisor like so:

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next test-divisor)))))

When I rerun the code from exercise 1.22, I get the following output:

1009 *** 0s 310000ns
1013 *** 0s 320000ns
1019 *** 0s 150000ns
(#<void> #<void> #<void>)

10007 *** 0s 780000ns
10009 *** 0s 780000ns
10037 *** 0s 940000ns
(#<void> #<void> #<void>)


100003 *** 0s 2500000ns
100019 *** 0s 7500000ns
100043 *** 0s 2500000ns
(#<void> #<void> #<void>)


1000003 *** 0s 2190000ns
1000033 *** 0s 7810000ns
1000037 *** 0s 2190000ns
(#<void> #<void> #<void>)

Compared to the results of exercise 1.22:

Number	Ex 1.22 Time	Ex 1.23 Time	Ratio
1009	460000	310000	1.48
1013	470000	320000	1.47
1019	320000	150000	2.13
10007	1250000	780000	1.6
10009	1410000	780000	1.81
10037	1090000	940000	1.16
100003	5940000	2500000	2.38
100019	3910000	7500000	0.52
100043	4060000	2500000	1.62
1000003	7500000	2190000	3.42
1000033	1870000	7810000	0.24
1000037	2340000	2190000	1.07

If I throw away the top two and bottom two ratios, the average ratio is 1.54. This is close to but less than the expected speed up of 2. If the numbers are at all reliable — and I have my doubts — the extra 0.46 can be attributed to a combination of the procedure call to next (which could take longer than the call to + because it is user-defined versus built-in) and the additional if, with its test for equality to 2.

Bullies on Parade

Scientific American Mind has an story on schoolyard bullying and mobbing. Mechthild Schäfer, the author, was part of a study that aimed to discover why bullies bully. The results are discouraging, if not altogether surprising:

Likewise, we encountered eight-year-olds who, by their own statements and those of their contemporaries, had been the butt of mobbing for quite a while. They endured harassment and exclusion yet never put up resistance or informed adults about their situation. The consequences can be long-lasting. In earlier studies we had shown that children who are harassed by schoolmates over a lengthy period are often unable to defend themselves against hostility and react to attack with anxiety and helplessness. Such terrible experiences make it all the more likely that they will fall into the traps set by bullies.

When we asked the same questions six years later, the students' answers bore this out. After asking the 13- and 14-year-olds which kids they liked and which they did not, we developed a preference profile that gave us a good sense of an individual's social ranking in a class. The result was surprising. In contrast to the bullies' relative lower standing during elementary school, they had actually become very popular with their classmates. Their victims, on the other hand, got few sympathy points.

The good news?

The one positive note was that [the] previous experience [of former mobbing victims] was not usually repeated in their work lives, although mobbing in the workplace--the ganging up of subordinates or superiors through rumor, innuendo, intimidation, humiliation, discrediting and isolation--does happen.

I've always been a bit of a nerd so, as a kid, I took my fair share of name-calling and teasing, though I avoided the worst of it by having some athletic talent.

If you are still in school and having a tough go of things, keep in mind that it won't last forever. As Paul Graham writes:

It's important for nerds to realize, too, that school is not life. School is a strange, artificial thing, half sterile and half feral. It's all-encompassing, like life, but it isn't the real thing. It's only temporary, and if you look, you can see beyond it even while you're still in it.

Solid State "Disk" Arrives

Are the days of hard disk failures soon to be a thing of the past? I hope so.

Yesterday, Samsung announced the development of Solid State Disk with a capacity of 16GB and no moving parts. It consumes 5% of the power, weighs half as much, and transfers data at 150% the speed of a traditional hard drive. Cool stuff!

Hop a Ride on a Puzey Pumpabike

Looking for a human-powered hydrofoil vehicle? Check out Puzey Design's Pumpabike.

New Scientist's coverage contains a link to a short video (3.79MB).

Is Moralism an Evolutionary Maladaption?

Johnnie Moore has been reading Brad Blanton's Radical Honesty, and applying some of Blanton's ideas about moralizing to branding, marketing, and improvisation. As usual for Johnnie's posts, it is well worth a read.

What caught my attention was a quote from Blanton on what he calls the Disease of Moralism:

The passing on of learning from one generation to the next is not a bad design, and as an evolutionary development it seems to have triumphed... The ability to act based on accumulated information, and to pass great quantities of new information on, is the primary survival characteristic of the strongest animal on earth.

But, paradoxically, our survival mechanism has proved to be ultimately suicidal.

So is moralism an evolutionary maladaption? It is an interesting hypothesis, and for all I know, could very well be true, but it seems suspiciously oversimplified to me. [I could also very likely be misrepresenting Blanton's ideas, as I haven't actually read the quote in context, so take this all with a grain... no, a bag of salt.]

Given how pervasive moralizing is in western culture, I would guess that it probably has some evolutionary advantage, much like what scientists are uncovering with altruism. In fact, I'd guess that moralizing is an enormously beneficial tool; so beneficial that it is often misapplied in situations where it doesn't work, leading some observers, like Blanton, to believe it is always harmful.

So how could we test the hypothesis of moralism as a maladaption? There's something to think about.

Solution to SICP Exercise 1.22

Solution to Exercise 1.22:

DrScheme does not have a built-in runtime procedure that I could find, so I modified the code for timed-prime-test to use SRFI 19, like so

(require (lib "19.ss" "srfi"))
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (current-time time-process)))
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime 
       (time-difference 
        (current-time time-process) 
        start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display (time-second elapsed-time))
  (display "s ")
  (display (time-nanosecond elapsed-time))
  (display "ns"))

I implemented seach-for-primes as follows:

(define (search-for-next-prime starting-at)
  (if (prime? starting-at)
      starting-at
      (search-for-next-prime (+ starting-at 2))))

(define (search-for-primes find-n starting-at)
  (if (= find-n 0)
      null
      (let ((next-prime (search-for-next-prime starting-at)))
        (cons next-prime
              (search-for-primes (- find-n 1) (+ next-prime 2))))))

I could then run some tests:

(define (time-prime-tests primes)
  (map timed-prime-test primes))

(time-prime-tests (search-for-primes 3 1001))
(time-prime-tests (search-for-primes 3 10001))
(time-prime-tests (search-for-primes 3 100001))
(time-prime-tests (search-for-primes 3 1000001))

This gave the following output:

1009 *** 0s 0ns
1013 *** 0s 0ns
1019 *** 0s 0ns
(#<void> #<void> #<void>)

10007 *** 0s 0ns
10009 *** 0s 0ns
10037 *** 0s 0ns
(#<void> #<void> #<void>)

100003 *** 0s 0ns
100019 *** 0s 0ns
100043 *** 0s 0ns
(#<void> #<void> #<void>)

1000003 *** 0s 0ns
1000033 *** 0s 0ns
1000037 *** 0s 0ns
(#<void> #<void> #<void>)

As you can see, all of the tests for prime took no time at all. This is obviously wrong.

I have a feeling that all these processes complete in less time than a single tick of the process clock (which, on Windows, appears to have a resolution in milliseconds).

Let's magnify the results by calling prime? in timed-prime-test 1000 times instead of just once. Here's the modified definition:

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test 1000 n (current-time time-process)))
(define (start-prime-test i n start-time)
  (if (prime? n)
      (if (= i 0)
          (report-prime 
           (time-difference 
            (current-time time-process) 
            start-time))
          (start-prime-test (- i 1) n start-time))))

Now I get the following output:

1009 *** 0s 460000ns
1013 *** 0s 470000ns
1019 *** 0s 320000ns
(#<void> #<void> #<void>)

10007 *** 0s 1250000ns
10009 *** 0s 1410000ns
10037 *** 0s 1090000ns
(#<void> #<void> #<void>)

100003 *** 0s 5940000ns
100019 *** 0s 3910000ns
100043 *** 0s 4060000ns
(#<void> #<void> #<void>)

1000003 *** 0s 7500000ns
1000033 *** 0s 1870000ns
1000037 *** 0s 2340000ns
(#<void> #<void> #<void>)

Alright! We have some numbers. Unfortunately, when I run the tests again, I get totally different numbers. Grr! I'm going to consider these numbers representative of many runs, but they probably aren't. Let's start with some analysis.

Let's start by averaging the times for each group. We can multiply this by √10 to obtain an expected time for the following group, which we can compare against the measured time.

Group	Average Time	Expected time (based on lower group)	Difference
~1000	416667	—	—
~10000	1250000	1317616	-5%
~100000	4636667	3952847	17%
~1000000	3903333	14662427	-73%

With a difference of over 70% on the final group, this data clearly does not support the √n hypothesis, but it doesn't disprove it, either. For a definitive answer, we need a larger sample group. We need data for more values of n and for several runs. I'm not going to do that here because this post is already too long, and I'm sure you have better things to do.

Pakistan Trains Female Fighter Pilots

Boing boing is linking to a BBC story that Pakistan is now training women to be fighter pilots.

In the human factors course that I took as an undergrad years ago, the professor consulted with the military on the several designs. He told us of the stringent anthropometric (body-shape) requirements for fighter pilots. For example, their arms and legs must be a certain length because the seats cannot be made adjustable for G-forces expected in flight. Their torsos cannot be too tall or the canopy window won't close; nor too short or the pilot won't be able to see over the control panel.

There is also a weight restriction. The seat ejectors are designed for a very narrow range of weights (if I remember correctly, something like 175-190lbs). If the pilot is any heavier, there is a risk the ejected seat will not clear the aircraft. If the pilot is too light, there is a risk that ejection will cause severe spinal injury and/or death.

Given that women are, on average, lighter than men, I wonder if these women cadets fit the anthropometric requirements for the aircraft that they will be piloting.

Network Theory Study of the U.S. House of Representatives

A recent paper by Porter, Mucha, Newman, and Warmbrand studies the interconnections of the committees and sub-committees in the U.S. Congress from a network theoretic perspective. They conclude that the distribution of congressmen among the committees is not random — there's a shocker — that cliques rule over certain parts of the government. For example, there are strong ties between the Select Committee on Homeland Security and the House Rules Committee.

Regardless of the political implications of the study, I found it to be a fun example of network theory.

For those less inclined to read the paper, New Scientist has a summary.

Proving Theorem Provers Correct

In a Los Angeles Times commentary, Margaret Wertheim writes about one of the growning problems in modern mathematics:

People are now claiming proofs for two of the most famous problems in mathematics — the Riemann Hypothesis and the Poincare Conjecture — yet it is far from easy to tell whether either claim is valid. In the first case the purported proof is so long and the mathematics so obscure no one wants to spend the time checking through its hundreds of pages for fear they may be wasting their time. In the second case, a small army of experts has spent the last two years poring over the equations and still doesn't know whether they add up.

She claims that mathematics is evolving into a postmodern study where, according to Philip Davis, emeritus professor of mathematics at Brown University, mathematics is "a multi-semiotic enterprise" prone to ambiguity and definitional drift.

What I found interesting was this bit:

The [four-colour map] problem was first stated in 1853 and over the years a number of proofs have been given, all of which turned out to be wrong. In 1976, two mathematicians programmed a computer to exhaustively examine all the possible cases, determining that each case does indeed hold. Many mathematicians, however, have refused to accept this solution because it cannot be verified by hand. In 1996, another group came up with a different (more checkable) computer-assisted proof, and in December this new proof was verified by yet another program. Still, there are skeptics who hanker after a fully human proof.

I don't know if I buy the postmodern angle, but I believe she's right about the practice of mathematics changing. It seems to me that as the complexity of mathematical problems grows beyond the abilities of human minds, we are going to require computers to prove our theorems for us. My prediction: the job of mathematicians will eventually turn into proving that theorem-proving software is correct.

Solution to SICP Exercise 1.21

Solution to Exercise 1.21:

> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7

Bjorn Blogs about Eclipse

Bjorn Freeman-Benson has started blogging about the open source development of Eclipse. I've had the pleasure to sit through some talks that Bjorn's given at the past couple EclipseCons, including the tutorial he gave with Darin Wright on the debug framework in February. To say that he's a bright and articulate guy is a bit of an understatement. I'm looking forward to hearing what he has to say.

Forget Mars and Venus

When I Men are from Mars, Women are from Venus, I was sorely unimpressed with its (lack of) scientific rigour. I came across a Rebuttal from Uranus, a passionate challenge to Gray's assertions, but found it equally lacking in scientific study.

Happily, Edge has run several stories recently relating to gender differences including a debate between Pinker vs. Spelke on the results of recent gender difference studies, John Gottman's Mathematics of Love, and Simon Baron-Cohen's Assortative Mating Theory. Good stuff.

Taking the Digicam Plunge

For an embarrassingly long time, I've been promising Mandy that we would buy a digital camera. Last night, we finally took the plunge.

Our main criteria was price. We wanted to spend less than $300. After some surfing around TigerDirect, I found four Kodak cameras that worked: CX6445, CX7530, DX7440, and LS753.

The reviews of the DX7440 and LS753 on Imaging Resource and the dearth of reviews on the CX cameras convinced me that we were looking at a shootout between the DX7440 and the LS753.

Mandy and I compared the two. The LS753 is a 5 megapixel camera, but only has a 2.8x optical zoom. The DX7440 only has 4 megapixels, but a 4.0x optical zoom. We don't expect that we'll be printing out to many large (>5x7) photos, so the extra megapixel of resolution didn't seem all that important. I wanted more than the 2.8x optical zoom of the LS753.

So the DX7440, it was. It should be arriving this week. Expect to see some shots on Flickr by the weekend.

Solution to SICP Exercise 1.20

Solution to Exercise 1.20:

;;; Normal Order

; remainder count: 0
(gcd 206 40)

; rc: 0
(if (= 40 0) 
    206 
    (gcd 40 (remainder 206 40))) 

; rc: 0
(gcd 40 (remainder 206 40)) 

; rc: 0
(if (= (remainder 206 40) 0) 
    40 
    (gcd (remainder 206 40) 
         (remainder 40 (remainder 206 40))))

; rc: 1
(if (= 6 0) 
    40 
    (gcd (remainder 206 40) 
         (remainder 40 (remainder 206 40))))

; rc: 1
(gcd (remainder 206 40) 
     (remainder 40 (remainder 206 40)))

; rc: 1
(if (= (remainder 40 (remainder 206 40)) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40)) 
         (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40)))))

; rc: 2
(if (= (remainder 40 6) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40)) 
         (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40)))))

; rc: 3
(if (= 4 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40)) 
         (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40)))))

; rc: 3
(gcd (remainder 40 (remainder 206 40)) 
     (remainder (remainder 206 40) 
                (remainder 40 
                           (remainder 206 40))))

; rc: 3
(if (= (remainder (remainder 206 40) 
                  (remainder 40 
                             (remainder 206 40))) 
       0)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40))) 
         (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40))))))

; rc: 4
(if (= (remainder 6 
                  (remainder 40 
                             (remainder 206 40))) 
       0)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40))) 
         (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40))))))

; rc: 5
(if (= (remainder 6 
                  (remainder 40 
                             6)) 
       0)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40))) 
         (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40))))))

; rc: 6
(if (= (remainder 6 4) 0)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40))) 
         (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40))))))

; rc: 7
(if (= 2 0)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) 
                    (remainder 40 
                               (remainder 206 40))) 
         (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40))))))

; rc: 7
(gcd (remainder (remainder 206 40) 
                (remainder 40 
                           (remainder 206 40))) 
     (remainder (remainder 40 
                           (remainder 206 40)) 
                (remainder (remainder 206 40) 
                           (remainder 40 
                                      (remainder 206 40)))))

; rc: 7
(if (= (remainder (remainder 40 
                             (remainder 206 40)) 
                  (remainder (remainder 206 40) 
                             (remainder 40 
                                        (remainder 206 40)))) 
       0)
    (remainder (remainder 206 40) 
               (remainder 40 
                          (remainder 206 40)))
    (gcd (remainder (remainder 40 
                               (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40)))) 
         (remainder (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40))) 
                    (remainder (remainder 40 
                                          (remainder 206 40)) 
                               (remainder (remainder 206 40) 
                                          (remainder 40 
                                                     (remainder 206 40)))))))

; rc: 14 (there were 7 calls to remainder in the = form above)
(if (= 0 0)
    (remainder (remainder 206 40) 
               (remainder 40 
                          (remainder 206 40)))
    (gcd (remainder (remainder 40 
                               (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40)))) 
         (remainder (remainder (remainder 206 40) 
                               (remainder 40 
                                          (remainder 206 40))) 
                    (remainder (remainder 40 
                                          (remainder 206 40)) 
                               (remainder (remainder 206 40) 
                                          (remainder 40 
                                                     (remainder 206 40)))))))

; rc: 14
(remainder (remainder 206 40) 
           (remainder 40 
                      (remainder 206 40)))

; rc: 15
(remainder 6
           (remainder 40 
                      (remainder 206 40)))

; rc: 16
(remainder 6 (remainder 40 6))

; rc: 17
(remainder 6 4)

; rc: 18
2

For normal order, remainder is performed 18 times.

;;; Applicative Order

; rc: 0
(gcd 206 40)

; rc: 0
(if (= 40 0) 
    206 
    (gcd 40 (remainder 206 40))) 

; rc: 0
(gcd 40 (remainder 206 40))

; rc: 1
(gcd 40 6)

; rc: 1
(if (= 6 0) 
    40 
    (gcd 6 (remainder 40 6))) 

; rc: 1
(gcd 6 (remainder 40 6))

; rc: 2
(gcd 6 4)

; rc: 2
(if (= 4 0) 
    6 
    (gcd 4 (remainder 6 4))) 

; rc: 2
(gcd 4 (remainder 6 4))

; rc: 3
(gcd 4 2)

; rc: 3
(if (= 2 0) 
    4 
    (gcd 2 (remainder 4 2))) 

; rc: 3
(gcd 2 (remainder 4 2))

; rc: 4
(gcd 2 0)

; rc: 4
(if (= 0 0) 
    2 
    (gcd 0 (remainder 2 0))) 

; rc: 4
2

For applicative order, remainder is only performed four times.

This just in...

Apparently Eclipse 3.1M7 is out. What's new?

Solution to SICP Exercise 1.19

Solution to Exercise 1.19:

T_qp is defined as:

a ← bq + aq + ap
b ← bp + aq

If we apply T_pq to itself, we get T²_pq:

a ← (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
b ← (bp + aq)p + (bq + aq + ap)q

With some manipulation, this can be rewritten as:

a ← b(2pq + q²) + a(2pq + q²) + a(p² + q²)
b ← b(p² + q²) + a(2pq + q²)

As we are looking for a transformation of the form

a ← bq′ + aq′ + ap′
b ← bp′ + aq′

It should be fairly obvious that

p′ = p² + q²
q′ = 2pq + q²

Now we can modify our program:

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (sum-of-squares p q)     ; compute p'
                   (+ (* 2 p q) (square q)) ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

(define (square x)
  (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

27,000 Concurrent Erlang Poker Games

In the past six weeks, Joel Reymont has rewritten a large part of his online poker software engine in Erlang, with some impressive results:

I have a PowerBook G4 1.25Ghz with 512Mb of memory. Running 27K games consumes about 600Mb of memory and takes around 15 minutes per 10K games due to heavy swapping. I gave "top" a cursory look so this is a probably reason. Each game runs in about 0.02 to 0.07 seconds, depending on the number of games running.

Erlang has long been on my list of languages to learn, but I don't expect to get to it any time soon. SICP first, then CTM. If I haven't died of old age by then (given my current pace, I'd put the odds around 50:50), I might just take up Concurrent Programming in ERLANG.

FYI, Joel's engine was formerly programmed in Common Lisp. (via Chris Double)

Cosmic Radiation and the BSOD

Space is full of cosmic radiation. Computer chips that go into satellites and other space gear need special shielding to protect them from the single-event effects, or SEEs, of cosmic radiation, but here on Earth, chip designers haven't had to worry about it too much because the atmosphere reflects most of it away.

According to an article in EDN, with the increased densities of modern computer chips, SEEs are becoming the dominant reliability-failure mechanism here on Earth.

Paul Dodd, another foremost expert on SEEs and acting manager for the radiation-effects department at Sandia National Laboratories (Albuquerque, NM), says that commercial designs are also more frequently encountering SEEs but that designers are commonly missing or misidentifying them as other failures. "It could be happening on everyone's PC, but instead everyone curses Microsoft," says Dodd. "Software bugs probably cause a lot of those blue-screen problems, but you can trace some of them back to radiation effects." And designers cannot yet quantify the breadth of the problem because, as IC-design and EDA consultant Pallab Chatterjee points out, "It is something companies don't brag about."

As chip densities and clock speeds continue to increase, it seems chips will become more susceptible to SEEs. It will be interesting to see how this affects Moore's Law.

Marburg Outbreak in Angola

According to this New Scientist story, the Marburg virus outbreak in Angola that started in March has now spread into all age groups. Prior to this the virus was mainly infecting children. The virus has killed 271 of 311 reported cases.

Should I be surprised that this story isn't getting the same kind of coverage in the mainstream media that, say, the SARS outbreak received?

Challenging the Education Leviathan

Robert Nagle blogs about John Taylor Gatto's online book, An Underground History of American Education. From the prologue:

The new dumbness is particularly deadly to middle- and upper-middle-class kids already made shallow by multiple pressures to conform imposed by the outside world on their usually lightly rooted parents. When they come of age, they are certain they must know something because their degrees and licenses say they do. They remain so convinced until an unexpectedly brutal divorce, a corporate downsizing in midlife, or panic attacks of meaninglessness upset the precarious balance of their incomplete humanity, their stillborn adult lives. Alan Bullock, the English historian, said Evil was a state of incompetence. If true, our school adventure has filled the twentieth century with evil.

The way he rails against the public education system, you might never guess Gatto was once New York State Teacher of the Year.

Miniature Motors

New Scale Technologies makes miniature piezoelectric motors:

Piezoelectric actuators in the SQUIGGLE motor ultrasonically vibrate a threaded nut, producing an orbital motion. The nut vibration directly rotates a mating threaded screw to create precise linear motion — with no parasitic drag, no backlash, and very high stiffness. The motor holds its position with the power off.

This simple, robust piezo motor generates no magnetic fields, is vacuum compatible, and can be made from non-ferrous metals for use in MRI, scanning electron microscopy and focused ion microscopy applications.

Combine some of these with a miniature low-power DSP, and you have the makings of one tiny robot. What on earth you'd want a miniature robot for is beyond me, but it comforts me to know its possible.

Asynchronous Digital Design by Fulcrum

Fulcrum Microsystems developed a clockless semiconductor design methodology. Which allows them to design processors that run much faster than clocked chips and with lower power.

Back in 1994, near the end of the digital design course I took in university, the professor introduced the class to asynchronous design. Our professor showed us some tricks for solving simple problem with asynchronous logic, but told us that the technique wasn't feasible for large scale design at the time, because it was terribly complicated with race conditions. It seems Fulcrum has solved the problem, and even designed some rather complex chips with it.

They raised $20 million on Monday.

Is Hiring Obsolete?

Paul Graham has posted the talk he gave a PARC last week, entitled Hiring is Obsolete, where he encourages undergrads and grad students to start up companies with the aim of being bought out/hired by a big company:

When companies buy startups, they're effectively fusing recruiting and product development. And I think that's more efficient than doing the two separately, because you always get people who are really committed to what they're working on.

Plus this method yields teams of developers who already work well together. Any conflicts between them have been ironed out under the very hot iron of running a startup. By the time the acquirer gets them, they're finishing one another's sentences. That's valuable in software, because so many bugs occur at the boundaries between different people's code.

Paul has hinted at this strategy in some of his other essays. I think it is an intriguing idea, though I question how committed the startup's team will be to the big company after the buy out. In my experience (I've been involved in two buy-outs in my life), the founders are just as likely to bail once their golden handcuffs evaporate as stick around.

Anyways, it's an excellent read, as usual.

Dan Moniz attended the talk and blogged about it. Larry had some interesting comments on talk's abstract.

AquaOne Device Stops Toilet Leaks

TI's MSP430 microprocessor has found its way into a novel and practical application: a leak detector for toilets. The device, by AquaOne, consists of a shut-off valve and two water level sensors, one for the tank, to detect slow leaks, and one for the bowl that detects overflows. Both sensors report back to the shut-off valve, which houses the controller, which can cut off the water supply if there is a problem.

Musical Memory Trick

Mind Hacks reader, Matt Doar outlines a trick to use the brain's natural ability to encode context as an aid for hacking. He listens to a particular CD repeatedly when and only when he is working on a particular piece of code, thereby creating an association between the music and his memory of the code. Neat idea.

Waterloo Construction Safety Violations

Michael writes about Louisette Lanteigne's watchdog site, where she is posting photos of purported safety violations at a local construction site. She has come under some legal pressure from the builder, Activa Holdings Inc, to take down the site. There's no indication whether Activa is going to investigate the alleged safety problems. They have threatened further legal action, though.

Update (2005-11-14): Activa has filed suit. Read more about it here

The PR Debate

Startups should hire PR firms: for and against.

What's Wrong With Me?

Mandy thought I might be suffering from Hyperlexia. I show all the signs:

• Learn expressive language in a peculiar way, echo or memorize the sentence structure without understanding the meaning (echolalia), reverse pronouns
  
• Rarely initiates conversations
• An intense need to keep routines, difficulty with transitions, ritualistic behavior
• Auditory, olfactory and/or tactile sensitivity
• Self-stimulatory behavior
• specific, unusual fears
• Normal development until 18-24 months, then regression
• strong auditory and visual memory
• Difficulty answering "Wh--" questions, such as "what," "where," "who," and "why"
• Think in concrete and literal terms, difficulty with abstract concepts
• Listen selectively, appear to be deaf

But it turns out I'm just an anti-social jerk. Thanks, Mind Hacks.

Who is John Galt?

Apparently Frank Schmidt and Matthias Heiden are. Their company, EnOcean, develops radio switches and sensors that require no batteries. They harvest energy from the environment.

The smallest changes in temperature, vibration, pressure, light or motion all produce energy that can be harvested and used to send a signal.

The principle of energy harvesting is not new (self winding watches have a history dating back hundreds of years), even the concept of using energy from the immediate environment to power wireless sensors has been done before (using outdoor solar panels on a sunny day). EnOcean’s radical breakthrough is to reduce the energy required to send a signal to an incredibly small amount. This change in energy requirements means that EnOcean sensors operate where other technologies cannot. A simple example is when our sensors are solar powered they can operate indoors, in a low light environment.

EnOcean just raised $13 million.

Nutty Political Idea

The problem: My vote in a national election is practically worthless. Whoever is elected the MP for my region will be expected to vote with his party, whose agenda is driven mainly (entirely?) by corporations and special interest groups who can afford to pay full-time lobbyist to schmooze with party leaders. At best, my vote chooses which lobbyist will hold sway. Nobody in government is listening to me.

One nutty solution: A new political party; one without a platform. Instead it has a process, a process that ensures that the will of the people it represents is heard and the influence of big money is eliminated. Think of it as a government within a government.

In this new party, any MPs from the party would be bound not by party leadership, but by the will of their constituents. How? Individual constituents would be able to vote on every bill presented to parliament in an online referendum. Party MPs would vote according to the results of the referendums in their region.

Bills could be proposed by anybody anywhere in the country. Like bills in parliament, individuals would vote on proposals in online referendums. The ones that passed the referendum would be presented by a party MP to parliament.

How's that for nutty?

[Note to self] This post is destined for Crank o' the Day for sure.

School Libraries Not Buying Many Books

According to a Globe and Mail story, a StatsCan survey of school libraries shows that the median amount that libraries spend on books and magazines is about $2000 per year.

“Given current costs, this would cover the purchase of one encyclopedia series,” the government agency said.

That seems awfully low to me.

Aurilink Blows Smoke

In their latest press release, Aurilink Inc. claims that their new amplifier makes customized digital hearing aids obsolete:

Aurilink, Inc. has developed a “ready-to-wear” sound amplifier for individuals who want and need occasional hearing assistance due to mild hearing loss. Such assistance was previously only available with expensive custom hearing aids, but preliminary studies have shown that the Aurilink Sound Magnifier is equal or superior to the most advanced DSP (digital signal processing) hearing instruments currently available.

As part of the team that develops and produces some of the world's most advanced DSP platforms for hearing instruments, I'm skeptical, to say the least.

Hearing aids are very similar to glasses. Just as people have different kinds of vision problems — near-sighted, far-sighted, and astigmatism — and to varying degrees, they also experience different kinds and varying degrees of hearing loss. A custom hearing aid doesn't just make everything louder, it amplifies the specific frequencies where the wearer has suffered loss. That's what makes them customized. Beyond that, high-end digital hearing aids offer other useful features, such as noise suppression, which can filter out the background chatter in a crowded room without affecting the voice of the person to whom the wearer is listening. The difference between a custom hearing aid and what Aurilink is selling is akin to the difference between prescription glasses from an optometrist and a the $10 reading glasses you can buy at the local drug store.

Indeed, Aurilink's CEO admits it:

“We like to think of the Sound Magnifiers as reading glasses for your ears,” said Otis A. Whitcomb, President and CEO of Aurilink.

That's not to say that I think their product is useless. Far from it. Reading glasses are a vast improvement over no glasses at all. Aurilink's products offer a similar value. I'm sure it's an excellent product for what it does (even if it is built on our competitor's platform, which is only a guess on my part), but “equal or superior to the most advanced DSP [...] hearing instruments currently available?” Come on! Who are you kidding?

Canada Added to Piracy Watch List

According to The Globe and Mail, the U.S. has put Canada on a special watch list as part of its annual report on intellectual property rights. We share this honour with such illustrious nations as Ukraine, Belize, Latvia, Lithuania, Taiwan and Thailand.

“It is imperative that Canada improve its enforcement system so that it can stop the extensive trade in counterfeit and pirated products, as well as curb the amount of transshipped and transiting goods in Canada,” according to the report by the office of the U.S. Trade Representative.

The report also urged Canada to pass legislation to give its customs officers greater power to seize suspected pirated and counterfeit goods.

Welcome to the Axis of Piracy, folks.

Key to Successful Team Building

Luís Nunes Amaral at Northwestern University and his team have discovered one of the keys to building a successful team, according to a New Scientist story. After analysing the production teams responsible for Broadway musicals between 1877 and 1990, and scientific research teams from 1955 to 2004, they found that successful teams have mix of new and experienced collaborators:

The found they could predict success largely looking at just two parameters - the likelihood of a newcomer being in the team, and the likelihood of a collaboration being repeated. "We were very surprised because it worked. We were able to reproduce what was going on very nicely," Amaral told New Scientist.

The researchers rated the success of scientific teams by examining the impact of the journals they published their work in, spanning ecology, astronomy, social psychology and economics.

"The teams publishing in good journals were built in a different way," he says. Research teams publishing in lower impact journals tended to repeat collaborations again and again. The most successful teams did work with the same colleagues too, but only 75% of the time, he says.

One more reason it makes sense to hire co-op students.

When I worked at TI, we kept a small army of co-op students on staff every term. At one point, nearly half the engineering staff was students. Besides being cheap labour, they always brought a lot of fresh ideas with them. It made for a very energetic and fun workplace. I wondered at the time if it made the team more productive. I suspected it did, but it's nice to see some research to back it up.

Solution to SICP Exercise 1.18

Solution to Exercise 1.18:

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

(define (even? n)
  (= (remainder n 2) 0))

(define (it-fast-mult a b)
  (iter 0 a b))

(define (iter total a b)
  (cond ((or (= a 0) (= b 0)) 0)
        ((= b 1) (+ total a))
        ((even? b) (iter total (double a) (halve b)))
        (else (iter (+ total a) a (- b 1)))))

Solution to SICP Exercise 1.17

Solution to Exercise 1.17:

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

(define (even? n)
  (= (remainder n 2) 0))

(define (fast-mult a b)
  (cond ((or (= a 0) (= b 0)) 0)
        ((= b 1) a)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

Solution to SICP Exercise 1.16

Solution to Exercise 1.16:

(define (even? n)
  (= (remainder n 2) 0))

(define (square x)
  (* x x))

(define (it-fast-expt b n)
  (iter 1 b n))

(define (iter a b n)
  (cond ((= n 0) a)
        ((even? n) (iter a (square b) (/ n 2)))
        (else (iter (* a b) b (- n 1)))))

Solution to SICP Exercise 1.15

Solution to Exercise 1.15:

Part a. Here's the process of (sine 12.15).

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))
...

There are clearly 5 applications of the p procedure.

Part b. We can see from the process above that the p procedure is applied for every power of 3.0 in angle. The order of growth in the number of steps is therefore Θ(log₃n). Because the p procedures accumulate for every power of three, the growth of process in space is also Θ(log₃n).