Live data from Hacker News

Nearly All Binary Searches and Mergesorts are Broken (2006)

googleresearch.blogspot.co.uk

21–30 of 47 posts

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

#21

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.…

Not that it detracts from your point, but the phrase is a reference to a famous Knuth quote:

http://www-cs-faculty.stanford.edu/~knuth/faq.html (see the last question)

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

#22
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.

As a theory guy I'd argue you're looking at it backwards.

The proofs are fine in that the correctness logically follows given the appropriate assumptions. In this particular example, it's implicitly assumed that integer overflow isn't a concern. Ideally, something like that should be explicitly stated, but let's be honest, Algorithms and Math in general have to be shorthand heavy - the alternative is painful and often not human readable.

It's always been the responsibility of the implementer to dive deep enough into the theory to grasp all the omitted assumptions. A less gratuitous headline might read - "Common implementation pitfalls: Integer Overflow"

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

#23
post #20

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.

I see that as a limitation. "works only with data sizes up to half of MAXINT" is not a very surprising limitation of

     int mid = (low + high) / 2;

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

#24

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.…

Computers are now complicated enough for Computer Science to have turned to some extent into an empirical science - it is impossible for a single person to have in their head everything that goes in a typical computer, operating system, compiler and so forth, so one is often forced to resort to experiment to find things out, it's no longer a theory where you can just reason things out, maybe it never was one in fact, because many simple imperative programs are so complex to reason about.

In empirical sciences, you not only have to have a mathematically valid theory, but you also have to check if the theory fits reality by making predictions and experimentally checking them with the real world. It's the same now in Computer Science, there are so many places where theoretical assumptions might deviate from reality that having a proof is not enough. In fact, you have to have those assumptions to make things mathematically tractable. Imagine mathematicians or computer scientists re-proving real analysis theorems using floating point arithmetic...

In other words, your vision of proofs being enough as long as all the assumptions are part of the theory, seems utopian to me. In fact, even some of the most devoted advocates of correctness proofs have admitted this:

http://www.gwern.net/docs/1996-hoare.pdf

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

#25

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.…

I do agree with the quoted statement. I have a lot of experience with machine-verified proofs (in a language called Coq). Even though Coq guarantees that an accepted proof is correct, you still can't necessarily trust it, because your formal model of the program may be not accurate enough, or your statement of correctness is improperly stated.

In this case, it seems like their proof was correct with respect to their model, but their model did not match up with reality. No amount of formalization will ever be able to solve this problem completely. I think the role of testing in this context is to make sure your formalization of the problem says what you meant to say about the world that you meant to refer to. Input/output examples (aka, tests) are a great way of convincing yourself of this.

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

#26

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.…

>It is sufficient to prove a program correct - as long as your proof is not faulty!

This is unquestionable truth. Proof:

Proposition A(X): X is true in theory

Proposition B : For all X such that A(X), X is true in practice

Theoretically, there is no difference between theory and practice. ... (1)

Theoretically, statement B is true. [using (1)] ... (2)

Therefore, B is true in practice. [using (1) and (2)]

QED.

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

#27

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.

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 technica…

Yeah. That "fix" immediately jumped out at me in the sense of WTF??? All he did was double the max size of the array before his code fails again!

That so-called "fixed" code just couldn't do anything useful in a 32-bit address space. A billion 32-bit ints completely fills up the address space by itself. As you note, perhaps it could "technically" be possible to search a billion 8-bit bytes, but that's not what's being passed in to the function.

And if he's running in a 64-bit address space (otherwise how could he pass in an array of a billion ints), then he should be using 64-bit integer arithmetic. (I don't know enough about Java to know how feasible it is to do that).

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

#28
post #24

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.…

Computers are now complicated enough for Computer Science to have turned to some extent into an empirical science - it is impossible for a single person to have in their head everything that goes in a typical computer, operating system, compiler and so forth, so one is often forced to resort to experiment to find things out, it's no longer a theory where you can just reason things out, maybe it never was one in fact,…

> Imagine mathematicians or computer scientists re-proving real analysis theorems using floating point arithmetic...

Mathematicians and computer scientists do prove theorems about floating point arithmetic! For example, the most widely-cited floating point reference contains no fewer than fifteen theorems about floating point:

http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.ht...

Or here's a presentation about representing functions with their Taylor expansions using floating point arithmetic, providing strong error bounds on the result of adding or multiplying two functions represented in this way:

http://perso.ens-lyon.fr/nathalie.revol/talks/ICIAM07.pdf

I agree that many proofs in computer science are harder than proofs in mathematics, because you can't deal with idealizations - you always have to think about the machine. But unlike empirical sciences, we have access to the design of the machine. We know what many of the axioms are. Formal reasoning is valid for a far larger part of computer science than for the natural sciences.

I'm not going to argue that proofs are a panacea for every situation. But I also don't categorically reject them in the domains where they can be usefully applied.

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

#29
post #20

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.

I was also thinking this was a stereotypical HN sensational headline blog post. Apart from being strangely correct, it somehow makes me want to code something in Java today.

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

#30

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.…

I would change it to "It is not sufficient merely to prove AN ALGORITHM IS correct; You have to test your implementation as well" ...
Post reply on HN