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

41–47 of 47 posts

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

#41

Post by astrodust »

crntaylor wrote: post #28
stiff wrote: post #24

Earlier quoted context omitted.

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

A theory, no matter how well defined, will never, ever, precisely match reality.

Testing is not optional. Why are you implying you can proof your way around this? A "proof" is useful for some problems, but I'll take very rigorous real-world tests over a proof any day.

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

#42

Post by graycat »

I read far enough into that to see the code that could cause overflow and quit reading.

I've programmed various cases of binary search, merge sort, etc. for decades and in all cases wrote code with indexing that could never overflow. If some silly academic make-work, prof-scam, busy-work, nonsense code could overflow, so be it.

Heck, I even worry ahout

do i = 1 to n

wondering if the code is written to exit the loop when i = n + 1 tests larger than n, which in case n is the largest integer could never happen.

The title here "nearly all" is to me total BS. Take your insult of my code and stuff it. Capiche?

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

#44

Post by yetanotherphd »

jgoodwin wrote: post #5

A bit off topic, but most of statistics also breaks. If you go back to _Mathematical Statistics_ by RA Fisher, early in the last century, and look at his arguments about binning 'big data' into histograms, he has a nice little construction that uses the notion of an 'angle' running through the data set, does a Fourier Series expansion, keeps the 'DC' term from the cosine series, and waves his hand about second order…

I am a PhD statistician and I can't understand your comment.

What statistic is being calculated for the N=1 Trillion dataset? And what is the way of calculating that would be off by 10%?

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

#45

Post by yetanotherphd »

AndrewBissell wrote: post #4
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.

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.

But any system with such a large array would almost certainly be 64 bit by now.

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

#46

Post by yetanotherphd »

jadyoyster wrote: post #33
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.

How so? From [1] it would seem that Lisps (idiomatic ones at least), Python, Perl, Haskell and Ruby are all free from the possibility of integer overflow. That definitely doesn't sound like "nearly all code". [1] https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

In that case the language fixes the issue so the code is irrelevant.

In languages where integer overflow is possible, my point still holds.

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

#47

Post by kagebe »

byerley wrote: post #22
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.

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

Well, then I restate: "Those proofs were not proofs of the theorems they/Bloch wanted to prove." The point being: Proving is not just about your proof, but also about writing meaningful Theorems, or as it is more commonly called when programming: specification.

The implementer is not free of proving her implementation correct, given that the original algorithm was proven correct on some theoretical computational model. Bloch argues that, since the original proof is not sufficient, the implementer needs to test. I'd add, that if the implementer would adapt/redevelop the proof for her implementation, she might forgo testing. Of course, this is practically impossible for many execution environments.

Post reply on HN