Re: small correction to the Vienna Proposal
Chenyi Hu writes today:
>> I'd prefer m = 0.5 * (l + u) rather than m = l + 0.5*(u - l) because of
>>
>> 1. Avoiding the loss of significance in performing u-l for narrow intervals
>> 2. One less arithmetic operation.
Chenyi's alternative suffers from premature overflow when l and u are
greater than half the maximum representable number. The proposed form
l + 0.5*(u - l) is safe.
A similar bug existed for more than a decade in the integer index
computation in the binary search function Java library. The bug is
also present in many textbooks that describe the algorithm. The Java
library bug finally got detected, reported, and fixed, when memories
got large enough that l + u overflowed in 32-bit integer arithmetic.
See the report at
Synopsis: (coll) binarySearch() fails for size larger than 1<<30
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5045582
Computation with finite range and precision is often subtle!
-------------------------------------------------------------------------------
- Nelson H. F. Beebe Tel: +1 801 581 5254 -
- University of Utah FAX: +1 801 581 4148 -
- Department of Mathematics, 110 LCB Internet e-mail: beebe@xxxxxxxxxxxxx -
- 155 S 1400 E RM 233 beebe@xxxxxxx beebe@xxxxxxxxxxxx -
- Salt Lake City, UT 84112-0090, USA URL: http://www.math.utah.edu/~beebe/ -
-------------------------------------------------------------------------------