News for hackers. Stuff that matters.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by kybernetikos on Thursday July 09, 2015 @07:36PM (#9861417)
I'm sure I did a bunch of assembly programming on a CPU that had a flag telling you if the last calculation overflowed or not. Branch if overflow was a straightforward opcode.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by mark-r on Friday July 10, 2015 @12:18PM (#9864830)
Yes, but adding the branch instruction itself is the killer. If the processor had some kind of trap to set for overflow, there would be no extra instructions and no timing overhead when there wasn't an overflow.
Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by hga on Thursday July 09, 2015 @08:13PM (#9861576)
Indeed. I'm not sure how far back this goes, but definitely to the PDP-11, and looks like the IBM 360.