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