tough-to-explain Python

[Steven D'Aprano]

On Thu, 09 Jul 2009 23:07:34 -0400, Terry Reedy wrote:

> Steven D'Aprano wrote:
> 
>> And speaking of binary search:
>> 
>> [quote]
>> 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
>> quote]
>> 
>> http://northernplanets.blogspot.com/2006/07/nearly-all-binary-searches-
are-broken.html
>> 
>> or http://tinyurl.com/nco6yv
> 
> The actual report is at
> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-
it-nearly.html
> 
> 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
> ArrayIndexOutOfBoundsException."
> 
> 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 
ArrayIndexOutOfBoundsException?

I don't have "Programming Pearls", and unfortunately the section on 
binary search is not online:

http://netlib.bell-labs.com/cm/cs/pearls/sketch04.html

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".


-- 
Steven