41–50 of 51 posts
This seems more like a limitation of the language implementation than a program bug to me.
I remember reading this (back in 2006?) and looking at the versions of Binary Search and Merge Sort that I had recently written for the Data Structures & Algorithms class that I teach. I found that my versions did not have this bug, despite the fact that I had not given any thought to it. The reason my code did not have the bug is that I represented the range to be processed, not as low & high subscripts, but rather…
I remember reading this (back in 2006?) and looking at the versions of Binary Search and Merge Sort that I had recently written for the Data Structures & Algorithms class that I teach. I found that my versions did not have this bug, despite the fact that I had not given any thought to it. The reason my code did not have the bug is that I represented the range to be processed, not as low & high subscripts, but rather…
How does that avoid the problem? Assuming you used a signed integer for size and the list is large enough, there is a sign roll over on size. If size becomes less than -2 then low + size/2 is less than low (on the first pass of a binary search you now have an invalid iterator for mid). Assuming you used unsigned integers size can still not be the correct value if a rollover has occurred though this time mid will alwa…
If you subtracted two 64bit pointers and stored the result in an int32 though, then you would have problems.
I remember reading this (back in 2006?) and looking at the versions of Binary Search and Merge Sort that I had recently written for the Data Structures & Algorithms class that I teach. I found that my versions did not have this bug, despite the fact that I had not given any thought to it. The reason my code did not have the bug is that I represented the range to be processed, not as low & high subscripts, but rather…
Maybe something about torsors?
It's not binary searches and merge sorts that are broken, it's the INT data type that is "broken" (and I put "broken" in scare quotes because they aren't really broken, they just don't do what you want in most cases). People tacitly assume that INTs model the integers, but they don't. They model the integers modulo 2^N for some value of N. If you code as if INTs were integers and you hit the 2^N limit you will lose.…
A more correct title is "most binary search implementations have a bug" but that isn't catchy enough. When I first saw an article about it, it was actually in the context of how hard it is to write correct code. That should be the take away.
It's a little disappointing to me that the HN community is more interested in the concrete example than the meta topic itself.
The fact is with code, if you don't try it, it doesn't work. We all know this is true; when code works "the first time" we tell the story to our friends. I debugged a string-move routine ported from linux to a RISC processor with a requirement for aligned word-moves. It had 11 bugs in like, 20 lines of code. Because it hadn't been tried on that architecture before. Its not a bug if the code worked where originally de…
I remember reading this (back in 2006?) and looking at the versions of Binary Search and Merge Sort that I had recently written for the Data Structures & Algorithms class that I teach. I found that my versions did not have this bug, despite the fact that I had not given any thought to it. The reason my code did not have the bug is that I represented the range to be processed, not as low & high subscripts, but rather…
How does that avoid the problem? Assuming you used a signed integer for size and the list is large enough, there is a sign roll over on size. If size becomes less than -2 then low + size/2 is less than low (on the first pass of a binary search you now have an invalid iterator for mid). Assuming you used unsigned integers size can still not be the correct value if a rollover has occurred though this time mid will alwa…
By "integer", I did not mean "int". size was a std::size_t.
This, of course, is why you always use size_t for array indices. (unsigned int blows up on amd64, too: a 4GB array of chars is huge but not impossibly large).
That wouldn't have helped in this case, since the issue was an overflow in the (high+low) / 2 calculation. Wouldn't using size_t just make the problem less likely to happen (requiring an even larger array to show up)?
But that's system-specific; it's not defined to fix this, so sorry for spreading the misinformation.
I remember reading this (back in 2006?) and looking at the versions of Binary Search and Merge Sort that I had recently written for the Data Structures & Algorithms class that I teach. I found that my versions did not have this bug, despite the fact that I had not given any thought to it. The reason my code did not have the bug is that I represented the range to be processed, not as low & high subscripts, but rather…
regardless of how they are represented, are not things that should be added together. Maybe something about torsors? http://math.ucr.edu/home/baez/torsors.html
(Nice article. Thanks for the link.)