steven at REMOVE.THIS.cybersource.com.au
Fri Jul 10 05:41:43 CEST 2009
On Thu, 09 Jul 2009 23:07:34 -0400, Terry Reedy wrote:
> Steven D'Aprano wrote:
>> And speaking of binary search:
>> I was shocked to learn that the binary search program that Bentley
>> PROVED CORRECT and SUBSEQUENTLY TESTED [emphasis added] in Chapter 5 of
>> "Programming Pearls" contains a bug. Once I tell you what the it is,
>> you will understand why it escaped detection for two decades. [end
>> or http://tinyurl.com/nco6yv
> The actual report is at
> The is the so called bug:
> "In Programming Pearls Bentley says that the analogous line "sets m to
> the average of l and u, truncated down to the nearest integer." On the
> face of it, this assertion might appear correct, but it fails for large
> values of the int variables low and high. Specifically, it fails if the
> sum of low and high is greater than the maximum positive int value (231
> - 1). The sum overflows to a negative value, and the value stays
> negative when divided by two. In C this causes an array index out of
> bounds with unpredictable results. In Java, it throws
> The is *not* a bug is Bentley program.
Wow. That's an impressive set of typos :)
> It is a bug in bad, buggy, insane
> integer arithmetic implementations. low + high should either return the
> right answer, as it will in Python, or raise an overflow error.
Is binary search *supposed* to raise an overflow error if given more than
2**30 elements? If not, then you're solving a different problem: it's
just like binary search, but it only works up to a maximum number of
elements. Now perhaps that's a legitimate problem to solve, but unless
you make the change in behaviour clear up front, your code has failed to
live up to specifications and therefore is buggy.
Is there something special about OverflowError that is "better" than
I don't have "Programming Pearls", and unfortunately the section on
binary search is not online:
but there's no reason to imagine that the book will assume -- or even
state as a requirement for binary search -- that addition will never
overflow. Far from it: it seems to me that the author is very aware of
real world constraints, and in the early 1980s, BigInt types were not
something you took as a given.
Of course *binary search* as an algorithm is not broken. The bug was that
"Programming Pearls" neglected to take into account overflow when you
have more than 2**30 items. One way to take that into account is to
insist on using a language like Python where addition can never overflow.
But that's not the code presented in "Programming Pearls".
More information about the Python-list