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
--
http://mail.python.org/mailman/listinfo/python-list
