This seems fundamental, surprised elementary operations hasn't been made a part of every major language/framework.
>Bonus chatter: C++20 adds a std::midpoint function that calculates the average of two values (rounding toward a).
Finding the average of two unsigned integers without overflow
51–60 of 220 posts
Re: Finding the average of two unsigned integers without overflow
#52See also: "Nearly All Binary Searches and Mergesorts are Broken" by Joshua Bloch. The cluefulness or otherwise with which people often react to Bloch's excellent post is not something to ponder very closely if you want to retain any hope in the future of software engineering. https://ai.googleblog.com/2006/06/extra-extra-read-all-about... https://news.ycombinator.com/item?id=3530104 https://news.ycombinator.com/item?…
> I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug.
I haven't seen the mentioned proof, but if said proof is not formal and mechanized and/or does not consider all possibilities, including overflow, then should we really consider it to be a proof of correctness? It might prove some desirable properties, but I don't think we should leave it at that. I certainly don't think we should claim that "It is not sufficient merely to prove a program correct; you have to test it too."
When it comes to software programs, I believe proofs can and should be exhaustive. That does not necessarily mean you need to exhaustively test every input, but it does mean you need to prove correctness for every input, including inputs that might result in overflow or undefined behavior. Otherwise, we should not consider it a proof of correctness.
Re: Finding the average of two unsigned integers without overflow
#53Isn't it better to do
(a>>1) + (b>>1) + (a&b&1)
Re: Finding the average of two unsigned integers without overflow
#54Just by reading the headline, before opening the article, I thought of the patented solution in my head. "Just halve before adding, it can be off by one but some boolean logic might do it" Software patents are absolutely disgusting.
Absolutely the same thing I did. I even had the low bit logic worked out by the time I scrolled the article down and saw the patented line. Clearly we have both had miraculous enlightenment because legally this is “not obvious”.
Re: Finding the average of two unsigned integers without overflow
#55Isn't it better to do (a>>1) + (b>>1) + (a&b&1) No division needed.
Your compiler will take care of that. Leave the division for the humans to read.
Re: Finding the average of two unsigned integers without overflow
#56Earlier quoted context omitted.
It's more complicated than that. A patent troll will hold a patent for X and then claim you are violating that patent. You, the holder of Y, can then say "well you're violating Y so fuck right off". Or maybe there's another patent that could potentially indicate prior art, but it isn't your patent. Or you're just a really small player with a few patents in your portfolio trying to defend against a troll. Companies po…
the world would be better if more companies were able or daring enough to fight bullshit patents directly (with prior art, obviousness, etc defenses). but instead every company chooses to defend themselves by deluging the patent office with more crap, and collective abuse of the patent system to patent stuff even the “inventor” thinks is obvious becomes accepted totally normal behavior.
"The world would be a lot better if independently did xyz" can be applied to pretty much anything. Except tragedy of the commons is a real thing, and this is why you need governments to step in and regulate.
Re: Finding the average of two unsigned integers without overflow
#57Isn't it better to do (a>>1) + (b>>1) + (a&b&1) No division needed.
Not really. It is harder for most programmers to read (a>>1) than the simpler (a/2) and in most modern programming languages the compiler will notice the division by a power of two and compile to bit shift operations in both cases.
Re: Finding the average of two unsigned integers without overflow
#58Marshall Clow gave a pretty excellent CppCon talk covering these exact problems, called "std::midpoint? How Hard Could it Be?" https://www.youtube.com/watch?v=sBtAGxBh-XI
Re: Finding the average of two unsigned integers without overflow
#59Having done computer architecture and bit twiddling x86 in the ye olden days, I immediately, independently converged on the patented solution (code / circuit / Verilog, more or less the same thing). It goes to show how broken the USPTO is because it's obvious to anyone in the field. Patents are supposed to be nonobvious. (35 USC 103) https://patentdefenses.klarquist.com/obviousness-sec-103/
Agreed. I spent about a minute before reading it and came up with the first solution, didn't feel like thinking through the puzzle of how not to care which one is larger, and then settled on the one with the 2016 expiration date. All within 1 to 2 minutes. I briefly considered XOR but didnt feel like remembering more about it - the solution was obvious when I saw it. How any of that was ever patentable is a crime.
Re: Finding the average of two unsigned integers without overflow
#60Earlier quoted context omitted.
the world would be better if more companies were able or daring enough to fight bullshit patents directly (with prior art, obviousness, etc defenses). but instead every company chooses to defend themselves by deluging the patent office with more crap, and collective abuse of the patent system to patent stuff even the “inventor” thinks is obvious becomes accepted totally normal behavior.
"The world would be a lot better if independently did xyz" can be applied to pretty much anything. Except tragedy of the commons is a real thing, and this is why you need governments to step in and regulate.
yes, you are right. meaningful voluntary collective change is unlikely.
however, i believe that individuals should respect the commons, and don’t believe in the tragedy of the commons as an excuse for individual actions that contribute to the problem.
(insert starfish on the beach story)