Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nearly All Binary Searches and Mergesorts are Broken (2006)

googleresearch.blogspot.co.uk

Post reply on HN
Print view View original

11–20 of 47 posts

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#11

Post by chj »

smsm42 wrote: post #10
koverstreet wrote: post #8

Earlier quoted context omitted.

Yup. More annoyingly, for a binary search over an array (i.e. something that can fit in memory) their code is still wrong - they should be using size_t.

That's what I immediately wondered - why it's int and not size_t? Well, I guess in Java engine there could be technical reasons why it is int, but in general case of implementation you'd probably assume it's size_t and then only one of the fixes works.

Yes, best fix:

   int mid = low + (high - low) / 2;

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#14

Post by zvrba »

yetanotherphd wrote: post #2

I would guess that nearly all code, period, is vulnerable to integer overflow issues. I don't think it makes sense to worry about this except in very special cases.

> I would guess that nearly all code, period, is vulnerable to integer overflow issues.

Lack of checked integer arithmetic in some form is what I think is Java's biggest failure. Next to it is a lack of unsigned less/greater-than operator; it cannot be emulated easily with signed arithmetic. [There is unsigned right shift.]

(.Net _does_ have checked arithmetic; at least as an option.)

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#15

Post by MaulingMonkey »

koverstreet wrote: post #8
kagebe wrote: post #7

In my opinion, the main take-away here is that the proofs were, obviously, no proofs. If you program with modulo arithmetic you have to do your proofs with modulo arithmetic. If you use IEEE floating point, say goodbye to your theorems about real arithmetic. If you forget/omit a single fact about your target platform/machine/api (whatever axioms you found your reasoning on) in your proof, it may be worth nothing.

Yup. More annoyingly, for a binary search over an array (i.e. something that can fit in memory) their code is still wrong - they should be using size_t.

On top of that, this 'fix' from the article, even if it were corrected to use size_t instead of unsigned int...

  In C and C++ (where you don't have the >>> operator), you can do this:
  6:             mid = ((unsigned int)low + (unsigned int)high)) >> 1;
Has the same bug as the original snippet, just in unsigned space. Now, granted, binary searching a >2GB byte array in a 32-bit process is an unlikely use case... but it is technically feasible!

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#16

Post by greenlakejake »

Off topic(since it's not about C/Java), but Python has a long integer type which won't over/underflow unless you run out of memory.

% python

Python 2.7.5 (default, Aug 25 2013, 00:04:04)

[GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.0.68)] on darwin

Type "help", "copyright", "credits" or "license" for more information.

>>> i = long(9999999999999999999999999999999)

>>> i

9999999999999999999999999999999L

>>>

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#17

Post by crntaylor »

I don't agree with this statement

  "It is not sufficient merely to prove a program correct;
   you have to test it too."
It is sufficient to prove a program correct - as long as your proof is not faulty! The problem in this case was not that the program had a bug despite being proved correct. The problem was that the 'proof' was not a proof at all.

Machine ints are not mathematical integers. Floats are not real numbers. You can't prove things about programs that use ints/floats without taking these things into account.

Of course, the question of how one knows that a proof is correct is still left open - but that's a metatheoretical argument that it might be best to leave aside. I suspect that most faulty proofs are faulty for pedestrian reasons (incorrect type assumptions, failing to deal with null/NaN etc) rather than high-falutin' concerns about the validity of first-order logic.

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#18

Post by masklinn »

vbit wrote: post #6
AndrewBissell wrote: post #4

Earlier quoted context omitted.

Having an array with more than about 1.2 billion elements is all that it would have taken to break the old binary search, and that's not all that uncommon anymore. Pure JavaScript code isn't vulnerable to integer overflow by virtue of not having any integer types, and I believe errors like this were the reason for leaving them out of the language.

JavaScript numbers are just floats and susceptible to precision loss as well as overflow to Infinity, aren't they? In fact, if incremented repeatedly, 64-bit floats lose precision before 64-bit ints overflow.

> 64-bit floats lose precision before 64-bit ints overflow.

More precisely, a 64 bit IEEE 754 ("double precision") has 53 bits worth of "integer"[0], which allows for 15 digits (and almost, but not quite, 16: it can encode 15.95 decimal digits)

[0] even though only 52 bits are allocated to the fraction, because the fraction part has an implicit 53rd bit set to 1 outside of special values

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#19

Post by masklinn »

greenlakejake wrote: post #16

Off topic(since it's not about C/Java), but Python has a long integer type which won't over/underflow unless you run out of memory. % python Python 2.7.5 (default, Aug 25 2013, 00:04:04) [GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.0.68)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>> i = long(9999999999999999999999999999999) >>> i 9999999999999999999999999999999L >>>

> Python has a long integer type which won't over/underflow unless you run out of memory.

IIRC, so do Erlang, Ruby or Haskell (when using `Integer`), FWIW. And Java has BigInteger (though that one's a pain to use).

But there's a cost to their existence (they need to check for overflow at every operation), and a cost to going above machine word size. Also, now you've got "integers" which can take arbitrary amounts of memory and integer operations in O(n)

Still, definitely a plus on the correctness side.

There's also the option of type-encoded value ranges as in Pascal or Ada.

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#20

Post by edanm »

One of the uncommon times a sensational headline is actually correct!

I love this bug - it's been my go-to example of how there are bugs in every piece of code, no matter how supposedly common. A bug in Java's implementatino of Binary Search - one of the most popular languages, and one of the most used algorithms - and still a bug managed to lay in wait for 9 years.

Post reply on HN