Re:Nearly All Binary Searches and Mergesorts are Broken (2006)
by donaq on Tuesday February 16, 2010 @09:22PM
(#1130641)
This seems more like a limitation of the language implementation than a program bug to me.
[ Parent
| on HN ]
Re:Nearly All Binary Searches and Mergesorts are Broken (2006)
by sparky on Tuesday February 16, 2010 @10:25PM
(#1130752)
If the behavior is according to the language spec, it's not an implementation thing. Perhaps you meant language spec instead of implementation, but even in that case it seems like a poor idea to require all arithmetic to be arbitrary-precision, no?
Re:Nearly All Binary Searches and Mergesorts are Broken (2006)
by donaq on Wednesday February 17, 2010 @12:02AM
(#1130892)
You're right on both counts, and it is indeed a poor idea unless we can figure out a way to efficiently implement arbitrary precision arithmetic in hardware. I was just quibbling that the implementation of the binary search wasn't strictly wrong. :)
Having said that, I do think that such pitfalls might be easily avoided if a check for the values being operated on were built into the language implementation. That way, we can all write simpler code without having to take into account the min/max values for types specific to the language.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006)
by sparky on Wednesday February 17, 2010 @12:25AM
(#1130925)
It would be nice, but the overhead would likely be unacceptable, since most code is dominated by integer arithmetic of one form or another. There was a StackOverflow question here http://stackoverflow.com/questions/199333/best-way-to-detect... that has some good suggestions. As for hardware support, many (but not all) architectures have some support for trapping or jumping to a specified address on integer overflow. The problem is compiler support. It has been a long time since a mainstream compiler for a mainstream architecture has supported it. GCC still has a -ftrapv flag, but it appears not to work anymore.
There's a cool paper on a static analysis tool to detect possible overflows here: http://www.isoc.org/isoc/conferences/ndss/09/pdf/17.pdf They used it to find real bugs in open source projects.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006)
by ubernostrum on Wednesday February 17, 2010 @08:51AM
(#1131489)
This seems more like an artifact of 1970s programming to me; the fact that allegedly-modern languages still offer numeric types which differ only by the range of numbers they can represent is just plain nasty, and makes me happy that I use a language which doesn't make me worry about this when I want to work with numeric types.