On Tue, 16 Feb 2010 10:53:40 -0500, dsimcha <dsim...@yahoo.com> wrote:
== Quote from Daniel Keep (daniel.keep.li...@gmail.com)'s article
Ellery Newcomer wrote:
> On 02/15/2010 09:15 PM, Steven Schveighoffer wrote:
>>
>> For example, there is no possible way a person unfamiliar with
computers
>> (and most programmers who have not run into this) would believe that
>>
>> b = 5;
>> a = -b;
>>
>
> Tell any math major that fixnum arithmetic is really just arithmetic
> modulo 2^32 and they would believe you, even if they had never heard
of
> computers
>
>> would result in a being some large positive number. It's just totally
>> unexpected, and totally avoidable.
>>
>> -Steve
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
> Fast forward to 2006. I was shocked to learn that the binary search
> program that Bentley proved correct and subsequently tested in Chapter
> 5 of Programming Pearls contains a bug. Once I tell you what it is,
> you will understand why it escaped detection for two decades. Lest you
> think I'm picking on Bentley, let me tell you how I discovered the
> bug: The version of binary search that I wrote for the JDK contained
> the same bug. It was reported to Sun recently when it broke someone's
> program, after lying in wait for nine years or so.
>
> ...
>
> The bug is in this line:
>
> 6: int mid = (low + high) / 2;
>
> ...
>
> In Programming Pearls, Bentley says "While the first binary search was
> published in 1946, the first binary search that works correctly for
> all values of n did not appear until 1962." The truth is, very few
> correct versions have ever been published, at least in mainstream
> programming languages.
It's fun to note that one of the fixes the author proposes in the
article was actually shown to itself be wrong... nearly two years later.
Clearly, knowing that computers use two's complement fixed-width integer
arithmetic is insufficient to write correct code. To believe otherwise
is to believe that humans are infallible.
In which case, I have literature on the Invisible Pink Unicorn [1] that
might interest you...
[1] http://en.wikipedia.org/wiki/Invisible_Pink_Unicorn
I **HATE** this example because it's a classic example of extreme
nitpicking. On
most modern computers, (void*).sizeof == size_t.sizeof. Furthermore,
usually half
your address space is reserved for kernel use. Therefore, this bug
would only
show up when you're searching an array of bytes **and** very close to
exhausting
available address space (i.e. when you probably have bigger problems
anyhow). I
have intentionally written binary searches like this even though I'm
aware of this
bug because it's more readable and efficient than doing it "right" and
would only
fail in corner cases too extreme to be worth considering.
Actually, this bug is more common than that; overflow can happen on arrays
of length uint.max/2 and that's to say nothing of using 64-bit code. Also,
the std.algorithm binary search routines use a different algorithm that
appears to be safe to use. (Though they won't compile in 64-bit mode due
to a minor bug)
