Roger Hui <[EMAIL PROTECTED]> wrote: > The machine integer overflow problem is responsible > for "nearly all binary searches .. are broken", > including the one in "Programming Pearls" by > Jon Bently: > > http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html > > When you look at x+y and you know that x and y are > non-negative, it is very difficult to be alert to > the fact that x+y can be negative!
Several years ago, I encountered a similar problem in C when using the quicksort library function; it had a tendency to produce incorrect results on arrays where the number of elements fit within a machine word, but the number of elements * sizeof (element) did not. After looking at the library source code, it was sufficient to replace something like (start - end) / size by ((long) start - end) / size to fix the problem. I also noticed that in DOS, doing "dir /on" to obtain a sorted directory listing produced exactly the same kind of anomalous behavior on large directories as was produced by the broken quicksort, so it's likely that this problem was common among C library authors. -- Mark D. Niemiec <[EMAIL PROTECTED]> ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
