Nearly All Binary Searches and Mergesorts are Broken (2006)
googleresearch.blogspot.co.uk
Nearly All Binary Searches and Mergesorts are Broken (2006)
1–10 of 47 posts
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#2I 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.
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#3Previous discussions :
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#4I 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.
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#5A 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 effects. He does estimate them for the sine-like series, and finds for a data set of size N=1 Trillion it might be a 10% effect.
The only remnant of this whole proceeding in modern lore (and even Ph.D. statisticians may not have heard of it) is Sheppard's correction for equal class-interval histograms:
http://mathworld.wolfram.com/SheppardsCorrection.html
But of course when your datasets start to be 1 billion rows routinely, 10% effects a mere 3 orders of magnitude away in the size of the dataset should start to make you nervous.
Moral: once you get a billion data points of anything or so, it's time to redo the Maths, very very carefully.
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#6I 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.
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.
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#7In 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.
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#8In 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.
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#9Earlier 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.
Oh yes, floating point numbers have ALL SORTS of other issues. I was just stating the JS rationale for leaving ints out of the language, not saying I find it particularly convincing at all.
Re: Nearly All Binary Searches and Mergesorts are Broken (2006)
#10In 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.
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.