Earlier quoted context omitted.
Big integer by default is a terrible idea. Just look at Python 3.
Python 2 was bigint by default. Not even going to deconstruct your argument past that
I didn't say it wasn't...?
Nearly All Binary Searches and Mergesorts Are Broken (2006)
21–30 of 95 posts
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#22I 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.
It is worth a lot to be good at assembly these days. It's a big piece of how my team makes a living. As one of my older colleagues puts it: there are fewer relevant jobs, but those jobs pay significantly more money, and you can only hold one job at a time.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#23The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
The bug isn't in the language, you just disagree with some of the goals. It was designed for the compiler to be small and easy to write, with data types and operations that map directly to operations that most CPUs can perform.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#24Earlier quoted context omitted.
Are you mocking the parent poster? Why?
Nah, I thought it was a good point. It's easy to forget that we either change or become obsolete. It's one thing to know it abstractly, but it's hard to make any lifestyle changes, especially if it involves switching to a job in a completely new domain. http://thecodist.com/article/the_programming_steamroller_wai... is a good essay on this. EDIT: previous discussion: https://news.ycombinator.com/item?id=7204515
grep for "fundamentals" | "first principles" in that article.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#25I 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 current hotness is AI/machine learning/deep learning. Maybe after that it will be something like "quantum programming"?
Just my guess.
http://www.newsweek.com/2017/04/21/quantum-computing-ibm-580...
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#26Earlier quoted context omitted.
Agreed completely; the right fix is that anything indexing an array should be an unsigned size_t (or equivalent for your language of choice).
Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.
If "this bug" is the ability to sort >2^30 elements on a 64-bit machine, this bug IS addressed by changing the index type.
Of course sorting 2^63 elements would require the different calculation.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#27The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
Erlang has arbitrary length integers by default, and I've found it to be incredibly liberating.
I thought Erlang didn't even have random access. Might not be the best fit for an in-place quicksort.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#28I 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…
There was definitely a recent boom in fintech / high-frequency trading.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#29Earlier quoted context omitted.
Nah, I thought it was a good point. It's easy to forget that we either change or become obsolete. It's one thing to know it abstractly, but it's hard to make any lifestyle changes, especially if it involves switching to a job in a completely new domain. http://thecodist.com/article/the_programming_steamroller_wai... is a good essay on this. EDIT: previous discussion: https://news.ycombinator.com/item?id=7204515
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 fundamental level the job of a programmer is little different now than it was in any of those eras. I have no doubt that a competent programmer from then, if picked up and plopped in front of a MacBook in 2017 could do a little reading up and perform proficiently in most programming jobs today. Probably more proficient because 1. they've seen it all before including the bugs and pitfalls and 2. I'd argue programming is much easier today than it ever has been.
EDIT: I swear I did not read the top comment in the (newly) linked HN discussion of that article before I wrote my response. I agree completely.
Re: Nearly All Binary Searches and Mergesorts Are Broken (2006)
#30> int mid = low + ((high - low) / 2);
That may fix things in the case of searching a sorted array, but binary search can be used more generally than that. I think that fix might not work for some of the more general applications of binary search.
For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) 0, and you want to find an n in (a,b), if such n exists, such that f(n) = 0. Binary search on [a, b] is a reasonable approach.
If a 0, then that mid computation could overflow on the subtraction.