disabling unary "-" for unsigned types

[Robert Jacques]

On Tue, 16 Feb 2010 10:53:40 -0500, dsimcha <dsimcha at yahoo.com> wrote:

> == Quote from Daniel Keep (daniel.keep.lists at 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)