Joshua Bloch, of Google Labs, reports on his chance discovery of a software bug that affects practically every binary search and mergesort function in the world. The problem came to light when a Java application failed, and the failure was traced to part of the Java kernel Bloch originally programmed. The bug was reported to Sun Microsystems, and hence made its way back to Bloch.
Bloch had based the implementation on his PhD tutor Jon Bentley’s. Presumably, everyone Bentley taught will have made the same mistake, as will everyone who used his book Programming Pearls. But there’s more. The first binary search dates back to 1946, and it’s got the bug. It was never a problem, because it works for arrays smaller than a billion, which have only recently existed.
Back in 1946, the great Maurice Wilkes had just become the head of the Cambridge Maths Lab, later renamed the Computer Lab. Wilkes was working on EDSAC, the first computer with a stored program and also the first with an operating system, the so-called basic orders, which was being developed almost in parallel with LEO, the first commercially useful computer.
Wilkes famously remarked that “I can remember the exact instant when I realized that a large part of my life from then on was going to be spent in finding mistakes in my own programs.” He wasn’t wrong..