tough-to-explain Python

Terry Reedy tjreedy at udel.edu
Sat Jul 11 01:48:58 CEST 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
    while True:
       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 
error prone.

Terry Jan Reedy




More information about the Python-list mailing list