tjreedy at udel.edu
Fri Jul 10 19:48:58 EDT 2009
I V wrote:
> 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.
> But it was Bentley himself who used the C int type, so it hardly seems
> unreasonable to blame him.
The original program that he verified was in pseudocode equivalent to
the following (not tested) Python. The odd spec is due to Bentley using
1-based arrays. From the 1986 book Programming Pearls
def binsearch(x, t):
"If t is in sorted x[1:n], return its index; otherwise 0"
L,U = 1, len(x)-1
if L > U: return 0
m = (L+U)/2
if x[m] < t: L = m+1
elif x[m] == t: return m
elif x[m] > t: U = m-1
He then translated into an unspecified dialect of BASIC, but it is
consistent with Microsoft GW-BASIC. If so, L and U were float variables,
while the largest possible array size for x was 32767. So as near as I
can tell with that dialect, there was no possible problem with L+U
overflowing or wrapping. Other dialects, I am not sure.
So I revise my statement to "I consider it wrong to blame the Bentley
that wrote the original program" ;-).
If he later translated to C and fell into the residue class trap, then
that reinforces my contention that using residue classes as ints is
Terry Jan Reedy
More information about the Python-list