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)

research.googleblog.com

Post reply on HN
Print view View original

51–60 of 95 posts

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

#51

Post by throwaway91111 »

admax88q wrote: post #48
sillysaurus3 wrote: post #4

I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…

The problem is these sorts of things are trivia. They are things that sufficiently smart tooling should handle for us so people can spend time building higher level constructs and less time worrying about individual bits. A smart compiler should have caught (a + b) / 2 and fixed it to be correct, there's no way the overflow situation is what the programmer wanted.

"sufficiently smart tooling" has got to be one of the best jokes in programming.

On one hand, it is true that the tooling is possible. On the other hand, it remains an open problem.

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

#52

Post by rntz »

pishpash wrote: post #45
rntz wrote: post #40

Earlier quoted context omitted.

I'm tempted to suggest (low / 2) + (high / 2) but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop wor…

That won't get you the middle, these are integer divisions.

Yes, that's why I said: "but then I have to think about rounding error. Ugh." Because integer division rounds. (Or truncates, if you prefer.)

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

#54

Post by CamperBob2 »

Programmer: "The bug is in the choice of data type. Use unsigned ints to index arrays."

Computer scientist: "The bug is in the language. Signed integer overflow behavior should have been defined in such a way as to guarantee correct functionality in cases such as this."

Me: "Use int64s for this sort of thing. It's still broken, but I'll be retired or dead before anyone notices."

Engineer: "The bug is in the documentation. The program is correct but should have been specified for use with element counts no greater than INT_MAX / 2."

Mathematician: "A solution exists."

Manager: "Ship it."

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

#55

Post by sanderjd »

ryandrake wrote: post #29
sikan wrote: post #19

Earlier quoted context omitted.

That's an amazing article. Thanks for sharing.

Yes and no. My response to that article is "The more things change, the more they stay the same." There is no steam roller. The fundamentals are not changing. So much touted (even here on HN) as new and innovative are little more than re-hashed versions of what we were already using 5, 10, 20, 30 years ago, just prettier. Sure the syntax is always changing a little, and the frameworks and tools are evolving, but at a…

I really wonder about this. It seems true to me that it's easier now and anyone who could do it back when it was harder could do it now.

But then, I wonder if it just seems that way to me because I'm a product of "now", which makes me more proficient in how we do things now, which makes it seem easier. It's possible neither is easier, that they are just different, and for everyone, the other seems harder than the one they already know.

I'm not trying to argue that this is the case: I could see it being either way and I sincerely wonder which way it is.

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

#56

Post by [deleted] »

sova wrote: post #44
dsacco wrote: post #17

Earlier quoted context omitted.

It's still worth a lot to be good at systems programming. Outside of the HN bubble there are plenty of companies willing to pay extremely well for people who can do systems programming, particularly under high performance constraints.

Name 5 please

[deleted]

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

#57

Post by bradleyjg »

e12e wrote: post #32

I'm surprised about the suggested solution for java: int mid = (low + high) >>> 1; I suppose things like this is why the ">>>" (unsigned shift) operator exists - but it's a bit odd when the value it works on is considered signed by the language, and implemented as two-compliment signed in memory. What's interesting to me is that this allows the sum to overflow, and would fail with the ">>" operator as far as I can te…

I agree it would be very surprising to see that line in a java codebase. >>> seems more like an answer to a java trivia question than something you'd come across on a regular basis.

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

#58

Post by EpicEng »

sikan wrote: post #5
sillysaurus3 wrote: post #4

I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could i…

I wish it was worth a lot to be good at assembly these days. It seems like the huge salaries are for c++ devs. I spent like ten years getting really good at this stuff but nowadays it feels like being really good at trivial pursuit. Edit: Did not mean to "mock" the OP, just merely trying to showing that you can apply that thought to almost anything in the programming world by replacing the technology/language names.

Except it's a bad analogy. Rails is not the next step up from systems level programming, it's a completely different (and honestly far less difficult) domain. Most of those rails devs could never be good at the hard stuff.

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

#59

Post by pishpash »

rntz wrote: post #52
pishpash wrote: post #45

Earlier quoted context omitted.

That won't get you the middle, these are integer divisions.

Yes, that's why I said: "but then I have to think about rounding error. Ugh." Because integer division rounds. (Or truncates, if you prefer.)

Plus, an extra operation, at least compared to some of the shift-based fixes.

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

#60

Post by justin66 »

pishpash wrote: post #53

So what 'bout this? It's the latest glibc. https://fossies.org/dox/glibc-2.25/stdlib-bsearch_8h_source....

The problematic line is:

__idx = (__l + __u) / 2;

__idx, __l, and __u are all the same type and the addition of __l and __u could cause an overflow resulting in a nonsense value assigned to __idx.

Post reply on HN