tough-to-explain Python
Terry Reedy
tjreedy at udel.edu
Thu Jul 9 23:07:34 EDT 2009
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. 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.
tjr
More information about the Python-list
mailing list