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
--
http://mail.python.org/mailman/listinfo/python-list
