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! ----- Original Message ----- From: Roger Hui <[EMAIL PROTECTED]> Date: Friday, November 17, 2006 8:03 am Subject: Re: [Jprogramming] Oddities with /: > I have found and fixed the bug for the next release. > Thanks for finding and reporting this error. > > The error is in a calculation that involves the > vector length and the maximum value, to decide which > sort algorithm to use. The example you found has > the right combination to cause machine integer > overflow. > > > > ----- Original Message ----- > From: Henry Rich <[EMAIL PROTECTED]> > Date: Friday, November 17, 2006 2:10 am > Subject: RE: [Jprogramming] Oddities with /: > > > I get similar behavior. I had to change the vector length > > a little bit to get it to fail: > > > > $ /:~vec=.?998005$1993426-~2^31 > > 998005 > > $ /:~vec=.?1098005$1993426-~2^31 > > |limit error > > | $ /:~vec=.?1098005$1993426-~2^31 > > > > The error seems to have something to do with the data: > > $ /:~vec=.?1098005$1993426-~2^30 > > 1098005 > > > > or even > > > > $ /:~vec=.?2098005$1993426-~2^30 > > 2098005 > > > > Henry Rich > > > > > > > -----Original Message----- > > > From: [EMAIL PROTECTED] > > > [EMAIL PROTECTED] On Behalf Of Roger Hui > > > Sent: Friday, November 17, 2006 1:56 AM > > > To: Programming forum > > > Subject: Re: [Jprogramming] Oddities with /: > > > > > > I can not reproduce the error in J601b. Did you > > > generate your examples in a brand new session? > > > > > > > > > > > > ----- Original Message ----- > > > From: Devon McCormick <[EMAIL PROTECTED]> > > > Date: Thursday, November 16, 2006 6:49 pm > > > Subject: [Jprogramming] Oddities with /: > > > > > > > The numbers below are right on the edge of failure. > > > > > > > > $ /:~vec=.?998005$1993426-~2^31 NB. This fails; > > > > |limit error > > > > | $ /:~vec=.?998005$1993426-~2^31 > > > > > > > > $ /:~vec=.?998005$1993427-~2^31 NB. but this (1 less) is OK; > > > > 998005 > > > > > > > > $ /:~vec=.?998006$1993427-~2^31 NB. but this (1 more > > element) > > > > fails.|limit error > > > > | $ /:~vec=.?998006$1993427-~2^31 > > > > > > > > $vec{~/:vec NB. However, this is > > > > equivalent to the > > > > above. > > > > 998006 > > > > > > > > (9!:12 '');9!:14 '' > > > > +-+---------------------+ > > > > |6|j601/2006-09-04/09:20| > > > > +-+---------------------+ ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
