Having 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)
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.
This is bizarre. I wonder how many of us saw that title, thought "That's a really simple problem, surely?" came up with a solution and then were shocked when their coffee-lacking brain actually came up with the patented solution?
I mean... ignoring the bitwise arithmentic (which this only obvious to people used to doing binary operations) this is the kind of maths that an 11yo could do.
That said, the patented solution is a little more complex. But not by much.
Which makes me curious: what other patents have we violated in our day-to-day without even knowing it?
I just want to second this with my own experience just now:
I looked at the title while still waking up.
At first I thought of the low + (high - low) / 2 method. I then figured maybe it was better to simply predivide both numbers before adding and just correcting for the lowest bit (how was that ever patented?!).
However, I didn't like having to perform two divisions so I thought there was probably something clever one could do with bit operations to avoid it. But, still being tired, I decided I didn't want to actually spend time thinking on the problem and I'd already spent a minute on it.
The patent is more sophisticated than what the article implies - it's a single clock cycle method, which no compiler I've ever seen will do given the code presented in the article.
The patent issued in 1996 and wasn't revisited since then (because never asserted in litigation). The USPTO is a lot different now, a quarter-century later.
What sets this post apart from the rest is that it actually provides useful information for everybody, after all those other posts of type "but that's obvious, I looked at it for 1 minute, saw half the solution, was too lazy for the rest and in hindsight it's all obvious. What a ridiculous patent system."
Not to say that the patent system is problematic...
Just 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"
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”.
See 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.
If doomscrolling all that isn't enough to make you fear for mankind's future I'm pretty sure there's an Ulrich Drepper glibc bug report rejection related to this topic (or several) that you can google...
On topic: Raymond's post has some other great stuff. SWAR!
I want to reply to one of the comments you linked to, which is this:
> I would argue that the bug is not in the algorithm -- the bug is in languages that don't detect integer overflow by default.
Concretely, this is true enough. But abstractly, not so much: the algorithm is actually "buggy" if you abstract the problem a little. Namely, finding a midpoint of two operands does not require that the operands be numbers, or even addable for that matter. The introduction of that requirement is therefore a bug (at least in my eyes). The easiest way to see this is to replace integers with pointers. Then adding two pointers isn't even a well-defined operation in the general case, let alone dividing them by two. Whereas subtracting them and moving half the distance is actually quite well-defined, and we can see it behaves better too.
I would probably go so far as to claim that this is not an isolated example of where thinking about problems more abstractly helps us come up with solutions that have non-obvious benefits.
> 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.
The Java solution is simpler because they are finding the average of 2 positive signed integers. So if you add 2 31 bit positive signed integers the result will fit in 32 bits and then you can just do an unsigned right shift to get the average.
There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016:
unsigned average(unsigned a, unsigned b)
{
return (a / 2) + (b / 2) + (a & b & 1);
}
It shouldn't be, but the world of software patents is truly bizarre. I have several patents in my name that are completely meaningless to the point of being satirical (stuff like "system to show a list of options and dispatch and action to a web server", "validating information submitted in a web form and returning errors"). Each is 40+ pages of filing, complete with diagrams, and all of them approved. And we need to do it otherwise someone will sue us with an equally bogus patent and we will have no defense.
Algorithms aren't patentable. What's patented here is a specific circuit that implements this algorithm in order to calculate the average in a single instruction cycle.
I've never come across this problem before, I read the headline and that solution came into my head immediately before I'd even clicked. I don't think I'm clever, surely half of HN feels the same way.
Yeah, when I read the article title, this is how I thought I would do it. Anything that obvious is not patentable in principle, but in practice, Samsung could still destroy any small business it wanted to by taking them to court over it. The patent system is awful
Exactly. I saw the title, thought "I wonder what other way there is to do this than the obvious one of pre-dividing by 2" and then opened the article and saw that the trivial way to do it was covered by a patent.
It is crazy. Can we get a computer program to spit out thousands of obvious simple programs, get FOSS to use them in various places for prior art to avoid this happening.
That's not a solid argument on its own. Today if you want to talk to someone then using a phone might be the first solution you can think of.
That doesn't indicate phone was a bad patent in a past.
> I find it amusing that the PowerPC, patron saint of ridiculous instructions, has an instruction whose name almost literally proclaims its ridiculousness: rldicl. (It stands for “rotate left doubleword by immediate and clear left”.)
Before reading the article: In x86 assembly, add ax, bx ; rcr ax, 1 works. I guess technically that is with overflow, but using overflow bits as intended.
EDIT: it's included in the collection of methods in the article as expected.
I noticed the following is in the middle of the article with no context that no one else is mentioning:
unsigned average(unsigned a, unsigned b)
{
return (a & b) + (a ^ b) / 2;
}
A quick sanity check of this
23 & 21 = 21
23 ^ 21 = 2
21 + 2 / 2 = 22 (order of operations)
I wonder why this is there. It seems the best solution but no one else is mentioning it. It also has no context near it. Nor is it stated correctly. It's just there on it's own.
I cannot believe that solution was allowed to be patented. How crappy is our patent process? Most engineers writing code would come up with that solution first.
Every patent attorney I've ever worked with has emphasized that engineers are not equipped to determine if an idea is obvious and should let the PTO decide.
They say this because they know the USPTO strategy is to just hand out patents after putting in some bare minimum effort to review, and postpone the real review process to the unlikely day that someone chooses to challenge it in court and can pay private firms to do their job for them.
The winners in this arrangement are the government, the big law firms, and the large corporations that can afford them.
He hinted at this obliquely, but the PowerPC family of bit rotate instructions (ridicl, rlwinm, rlwimi, etc.), although intimidating in the general case, allows shifting, rotation, insertion, masking and more. There are many alternative mnemonics to try to reduce the cognitive complexity but all of these just assemble to them with particular parameters.
As an asm geek, I wasn't surprised to read that taking advantage of the carry flag yielded the most efficient code for some processors.
I recalled that some ISAs also have special SIMD instructions specifically for unsigned average, so I looked them up:
* x86 SSE/AVX/AVX2 have (V)PAVGB and (V)PAVGW, for 8-bit and 16-bit unsigned integers. These are "rounding" instruction though: adding 1 to the sum before the shift.
* ARM "Neon" has signed and unsigned "Halving Addition". 8,16 or 32 bit integers. Rounding or truncating.
* RISC-V's new Vector Extension has instructions for both signed and unsigned "Averaging Addition". Rounding mode and integer size are modal.
* The on-the-way-out MIPS MSA set has instruction for signed, unsigned, rounded and truncated average, all integer widths.
Some ISAs also have "halving subtraction", but the purpose is not as obvious.
They recognize how to do a rotation of an unsigned integer value, but they do not recognize how to do the rotation of that value concatenated with the carry bit, which is needed here.
Reminds me of a Stack Overflow thread, Shortest way to calculate difference between two numbers? [0] Multiple answers ignored the possibility of overflow.
Eh. I just cast both to a bigger integer type where possible, which in practice, is almost always. So if I'm averaging two uint32_ts, I just cast them to uint64_t beforehand. Or in Rust, with its lovely native support for 128-bit integers, I cast a 64-bit integer to 128-bit.
"Also, if the number is of the form x.5, then, the values will be rounded up if the roundup value is an even number. Otherwise, it will be rounded down.
For example, 2.5 will be rounded to 2, since 2 is the nearest even number, and 3.5 will be rounded to 4."
Since this discussion is all about patents: my 2 cents on improving the patent system.
Consider a term project of an undergraduate CS course, where the goal is spelled out, but the method is left for discovery.
Methods developed within any such project immediately invalidate patents. They're apparently obvious to folks learning to become "skilled in the art".
Yes, in practice, reaching a legal threshold would be hard (are you sure the students didn't read the patent or any description directly resulting from it?). But I'd definitely run a "patent invalidation course" - if I had confidence that the results would actually affect patents.
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.
how is turning (a+b)/2 into a/2 + b/2 + a&b&1 even patentable?
Turning (a+b)/2 into a/2 + b/2 is basic obvious math.
If you do it and to any basic testing you will realize you are
getting of by one errors, locking at them can then make it
obvious that when they appear and hence how to fix them.
Sure a proof is more complex, but then you can just trivially
test it for all smaller-bit numbers over all possible inputs,
hence making proofs unnecessary (for that numbers).
This is a solution a not yet graduated bachelor student can find
in less then a day.
Having granted a patent for this should lead to disciplinary
measurements against the person granting the patent tbh.
errcorrectcode|4 years ago
https://patentdefenses.klarquist.com/obviousness-sec-103/
phkahler|4 years ago
undecisive|4 years ago
I mean... ignoring the bitwise arithmentic (which this only obvious to people used to doing binary operations) this is the kind of maths that an 11yo could do.
That said, the patented solution is a little more complex. But not by much.
Which makes me curious: what other patents have we violated in our day-to-day without even knowing it?
Agentlien|4 years ago
I looked at the title while still waking up.
At first I thought of the low + (high - low) / 2 method. I then figured maybe it was better to simply predivide both numbers before adding and just correcting for the lowest bit (how was that ever patented?!).
However, I didn't like having to perform two divisions so I thought there was probably something clever one could do with bit operations to avoid it. But, still being tired, I decided I didn't want to actually spend time thinking on the problem and I'd already spent a minute on it.
Ygg2|4 years ago
Emphasis on supposed.
The granted patents include: laser used to exercise cat, and mobile wood based dog game (log used to play fetch).
https://abovethelaw.com/2017/10/8-of-my-favorite-stupid-pate...
https://patents.google.com/patent/US5443036A/en
https://patents.google.com/patent/US6360693
Apple steals the cake though. By patenting a geometric shape.
zanethomas|4 years ago
the patented solution immediately came to mind
tapirl|4 years ago
ChrisLomont|4 years ago
And it's from 1996.
roberthahn|4 years ago
Our experiences and training has changed dramatically over the past 26 years.
b112|4 years ago
hackthefender|4 years ago
The patent issued in 1996 and wasn't revisited since then (because never asserted in litigation). The USPTO is a lot different now, a quarter-century later.
ridiculous_fish|4 years ago
Adding two bits produces a sum and a carry:
So the sum is XOR, and the carry is bitwise AND. We can rewrite x + y as (x ^ y) + (x & y)*2Distribute the divide, and you get (x ^ y)/2 + (x & y) which is the mystery expression.
(Note this distribution is safe only because (x & y)*2 is even.)
justinpombrio|4 years ago
a & b is the bits they have in common. If they both have a bit x, you should keep it, because the average of x and x is x.
a ^ b is the bits that only one of them have. You should halve these bits, because the average of x and 0 is x/2.
paulsmith|4 years ago
wildmanx|4 years ago
What sets this post apart from the rest is that it actually provides useful information for everybody, after all those other posts of type "but that's obvious, I looked at it for 1 minute, saw half the solution, was too lazy for the rest and in hindsight it's all obvious. What a ridiculous patent system."
Not to say that the patent system is problematic...
AnotherGoodName|4 years ago
How is the above SWAR? It looks like a regular set of instructions.
dheera|4 years ago
worewood|4 years ago
Software patents are absolutely disgusting.
jws|4 years ago
umeshunni|4 years ago
teaearlgraycold|4 years ago
Given its simplicity this makes me wonder if a compiler has ever transformed legal original IP code into patented code.
justin66|4 years ago
https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
https://news.ycombinator.com/item?id=3530104
https://news.ycombinator.com/item?id=1130463
https://news.ycombinator.com/item?id=14906429
https://news.ycombinator.com/item?id=6799336
https://news.ycombinator.com/item?id=9857392
https://news.ycombinator.com/item?id=12147703
https://news.ycombinator.com/item?id=621557
https://news.ycombinator.com/item?id=7594625
https://news.ycombinator.com/item?id=9113001
https://news.ycombinator.com/item?id=16890739
If doomscrolling all that isn't enough to make you fear for mankind's future I'm pretty sure there's an Ulrich Drepper glibc bug report rejection related to this topic (or several) that you can google...
On topic: Raymond's post has some other great stuff. SWAR!
dataflow|4 years ago
> I would argue that the bug is not in the algorithm -- the bug is in languages that don't detect integer overflow by default.
Concretely, this is true enough. But abstractly, not so much: the algorithm is actually "buggy" if you abstract the problem a little. Namely, finding a midpoint of two operands does not require that the operands be numbers, or even addable for that matter. The introduction of that requirement is therefore a bug (at least in my eyes). The easiest way to see this is to replace integers with pointers. Then adding two pointers isn't even a well-defined operation in the general case, let alone dividing them by two. Whereas subtracting them and moving half the distance is actually quite well-defined, and we can see it behaves better too.
I would probably go so far as to claim that this is not an isolated example of where thinking about problems more abstractly helps us come up with solutions that have non-obvious benefits.
smaddox|4 years ago
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.
benmmurphy|4 years ago
LudwigNagasena|4 years ago
johnhenry|4 years ago
After reading the article, learning that
was once patented actually made me a bit sad for our entire system of patents.cphoover|4 years ago
nmilo|4 years ago
paxys|4 years ago
lilyball|4 years ago
throwaway22032|4 years ago
I've never come across this problem before, I read the headline and that solution came into my head immediately before I'd even clicked. I don't think I'm clever, surely half of HN feels the same way.
Software patents are comical.
version_five|4 years ago
TYPE_FASTER|4 years ago
coutego|4 years ago
Wow! Just wow...
c-linkage|4 years ago
quickthrower2|4 years ago
StayTrue|4 years ago
unknown|4 years ago
[deleted]
rustybolt|4 years ago
That's completely retarded; it's literally the first solution I think of when I hear this problem.
kuboble|4 years ago
d_tr|4 years ago
dralley|4 years ago
I suspect the POWER team has a good sense of humor. There's also the EIEIO instruction https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-...
benlivengood|4 years ago
EDIT: it's included in the collection of methods in the article as expected.
jart|4 years ago
AnotherGoodName|4 years ago
23 & 21 = 21
23 ^ 21 = 2
21 + 2 / 2 = 22 (order of operations)
I wonder why this is there. It seems the best solution but no one else is mentioning it. It also has no context near it. Nor is it stated correctly. It's just there on it's own.
unknown|4 years ago
[deleted]
jlynn|4 years ago
829588225|4 years ago
yalogin|4 years ago
stathibus|4 years ago
They say this because they know the USPTO strategy is to just hand out patents after putting in some bare minimum effort to review, and postpone the real review process to the unlikely day that someone chooses to challenge it in court and can pay private firms to do their job for them.
The winners in this arrangement are the government, the big law firms, and the large corporations that can afford them.
classichasclass|4 years ago
leptoniscool|4 years ago
mzs|4 years ago
Findecanor|4 years ago
* x86 SSE/AVX/AVX2 have (V)PAVGB and (V)PAVGW, for 8-bit and 16-bit unsigned integers. These are "rounding" instruction though: adding 1 to the sum before the shift.
* ARM "Neon" has signed and unsigned "Halving Addition". 8,16 or 32 bit integers. Rounding or truncating.
* RISC-V's new Vector Extension has instructions for both signed and unsigned "Averaging Addition". Rounding mode and integer size are modal.
* The on-the-way-out MIPS MSA set has instruction for signed, unsigned, rounded and truncated average, all integer widths.
Some ISAs also have "halving subtraction", but the purpose is not as obvious.
unwind|4 years ago
I was surprised that the article didn't mention the need for this in binary search, and the famous problems [1] that occured due to naive attempts.
[1]: https://en.m.wikipedia.org/wiki/Binary_search_algorithm
ncmncm|4 years ago
Gcc and Clang both recognize the pattern of shifts and OR that reproduce a rotation, and substitute the actual instruction, no intrinsic needed.
I bet MSVC does too.
adrian_b|4 years ago
user-the-name|4 years ago
It's 2022. stdint.h is old enough to drink, and is probably married with a kid on the way. Just include it already?
MaxBarraclough|4 years ago
[0] https://stackoverflow.com/q/10589559/
unknown|4 years ago
[deleted]
favorited|4 years ago
rrss|4 years ago
Subsentient|4 years ago
everyone|4 years ago
mark-r|4 years ago
One of the reasons I love Python is that integers never overflow, so this becomes a trivial problem.
erwincoumans|4 years ago
https://www.askpython.com/python/built-in-methods/python-rou...
"Also, if the number is of the form x.5, then, the values will be rounded up if the roundup value is an even number. Otherwise, it will be rounded down.
For example, 2.5 will be rounded to 2, since 2 is the nearest even number, and 3.5 will be rounded to 4."
nickm12|4 years ago
Beldin|4 years ago
Consider a term project of an undergraduate CS course, where the goal is spelled out, but the method is left for discovery.
Methods developed within any such project immediately invalidate patents. They're apparently obvious to folks learning to become "skilled in the art".
Yes, in practice, reaching a legal threshold would be hard (are you sure the students didn't read the patent or any description directly resulting from it?). But I'd definitely run a "patent invalidation course" - if I had confidence that the results would actually affect patents.
hollowturtle|4 years ago
bufferoverflow|4 years ago
jws|4 years ago
8jy89hui|4 years ago
dpacmittal|4 years ago
dathinab|4 years ago
Turning (a+b)/2 into a/2 + b/2 is basic obvious math.
If you do it and to any basic testing you will realize you are getting of by one errors, locking at them can then make it obvious that when they appear and hence how to fix them.
Sure a proof is more complex, but then you can just trivially test it for all smaller-bit numbers over all possible inputs, hence making proofs unnecessary (for that numbers).
This is a solution a not yet graduated bachelor student can find in less then a day.
Having granted a patent for this should lead to disciplinary measurements against the person granting the patent tbh.
phs318u|4 years ago
avmich|4 years ago
blobbers|4 years ago
kingcharles|4 years ago
Props for including the assembler breakdown for every major CPU architecture.
readthenotes1|4 years ago
ijidak|4 years ago
Divide both operands by 2 was my first idea before loading the page. (I like to try that sometimes before reading the articles.)
I didn't think about the carry bit, but it seems like that would be a logical solution after 5 minutes of extra thinking.
I'm not sure how that's patentable.
That's insane to me.
But maybe there is more too it.
I didn't read the patent itself.