tough-to-explain Python

[Piet van Oostrum]

>>>>> I V <ivlenin at gmail.com> (IV) wrote:

>IV> On Fri, 10 Jul 2009 16:27:12 -0400, Terry Reedy wrote:
>>> a bug, bug a limitation due to using limited-range numbers. If one uses
>>> residue classes instead of integers, and makes no adjustment, I consider
>>> it wrong to blame Bentley.

>IV> But it was Bentley himself who used the C int type, so it hardly seems 
>IV> unreasonable to blame him.

If you are on a 32-bit machine, and the array to be searched contains
ints, floats or doubles, the the array must be < 2^32 bytes in size, and
as each element is at least 4 bytes, the indices are less than 2^30, so
l+u < 2^31. Therefore there is no overflow at all. I think the Bentley
programs were formulated in terms of arrays of ints. So his
implementations were safe.

If you are on a 64-bit machine you shouldn't use int for the indices
anyway (supposing int is 32 bits) but longs and then the same reasoning
shows that there are no overflows. Only when you have an array of shorts
or bytes (chars) you get the problem.

In that case the alternative formulation l + (u-l)/2 is more
robust and therefore preferable.
-- 
Piet van Oostrum <piet at cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org