50-year-old bug

Saturday 3 June 2006

I've dealt with chunks of code that seemed done, in that nothing had changed in them for a long time (years), and they were doing their job admirably. Then suddenly one day, a bug turns up in that code that seemed so finished.

Joshua Bloch has me topped: in Nearly All Binary Searches and Mergesorts are Broken, he identifies a bug in binary searches that has been around for 50 or so years. Like the archaeo-bugs I've dealt with, they arise because the old code is being used on a slightly new or unusual case. In the sort algorithms, it's arrays with billions of elements.

Comments

[gravatar]
Fredrik 1:09 PM on 3 Jun 2006

well, the bug he's identified is really a bug in C and in Java, not in binary sort in itself. real languages don't have those problems ;-)

[gravatar]
Nate 1:36 PM on 4 Jun 2006

Oh come on.... it's not a bug in C, it's improper use of the language. You might as well say arraylist[-1] isn't a bug in your code, it's a bug in the language. Of course it's a bug in your code.

I'm curious, what languages don't have a problem with adding maximum int values?

[gravatar]
Ned Batchelder 5:38 PM on 4 Jun 2006

Nate, you are right: the bug is in the code. And on this blog, didn't you know the answer to your question would be: Python doesn't have a problem adding maxint values. It simply begins using a long int representation that has unlimited precision:

>>> i = 1
>>> for exp in range(0,101,5):
... print "2^%d: %d" % (exp, i)
... i *= 32
...
2^0: 1
2^5: 32
2^10: 1024
2^15: 32768
2^20: 1048576
2^25: 33554432
2^30: 1073741824
2^35: 34359738368
2^40: 1099511627776
2^45: 35184372088832
2^50: 1125899906842624
2^55: 36028797018963968
2^60: 1152921504606846976
2^65: 36893488147419103232
2^70: 1180591620717411303424
2^75: 37778931862957161709568
2^80: 1208925819614629174706176
2^85: 38685626227668133590597632
2^90: 1237940039285380274899124224
2^95: 39614081257132168796771975168
2^100: 1267650600228229401496703205376

[gravatar]
Bob 11:50 PM on 4 Jun 2006

Integers expand to bignums in Lisp and Smalltalk as well.

[gravatar]
Sylvain Galineau 7:11 PM on 7 Jun 2006

People run binary search on billion-element arrays ? Wild.

Add a comment:

name
email
Ignore this:
not displayed and no spam.
Leave this empty:
www
not searched.
 
Name and either email or www are required.
Don't put anything here:
Leave this empty:
URLs auto-link and some tags are allowed: <a><b><i><p><br><pre>.