Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding the average of two unsigned integers without overflow

devblogs.microsoft.com

Post reply on HN
Print view View original

61–70 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#61

Post by hackthefender »

errcorrectcode wrote: post #39

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) https://patentdefenses.klarquist.com/obviousness-sec-103/

> It goes to show how broken the USPTO is...

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.

Re: Finding the average of two unsigned integers without overflow

#62

Post by IgorPartola »

rrss wrote: post #47
staticassertion wrote: post #37

Earlier 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.

Story time. I worked for a company who did prior art on something that was frankly fucking to obvious and is now ubiquitous (but as far as I know we did it first). At one point a patent troll sued us. Our clients were on our side and one of them (a very prestigious law school that rhymes with Barvard), offered their resources to help us fight the troll. The C level management decided to not risk it and just paid the troll. We were a 20 person company at the time and it wasn’t worth it I guess.

Re: Finding the average of two unsigned integers without overflow

#63

Post by teaearlgraycold »

worewood wrote: post #49

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" Software patents are absolutely disgusting.

As if anyone would ever get prosecuted for that, though.

Given its simplicity this makes me wonder if a compiler has ever transformed legal original IP code into patented code.

Re: Finding the average of two unsigned integers without overflow

#65

Post by umeshunni »

worewood wrote: post #49

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" Software patents are absolutely disgusting.

It's not the solution that's patented, but it's the implementation in a single CPU cycle in hardware.

Re: Finding the average of two unsigned integers without overflow

#66

Post by staticassertion »

tialaramex wrote: post #48
staticassertion wrote: post #38

Earlier quoted context omitted.

I'm not a lawyer, so I'm confused. If you patent a hardware implementation of a software algorithm, on the basis that the implementation is novel, how would you stop me from writing that algorithm irrespective of how it executes?

Where in each claim do you see their proposed "hardware implementation" - the novel device you suppose they've invented - that we might distinguish from, for example, every modern microcomputer ? What I see is a description of the algorithm because of course the intent is to patent the algorithm and not some special hardware implementation nobody will manufacture because it's patented. If you have some novel arrangem…

You don't have to invent a device to file a patent for it. They describe the device, the patent is for the device, the novelty is the construction of the device.

I honestly doubt that they could sue you for infringing on this.

Re: Finding the average of two unsigned integers without overflow

#67

Post by hackthefender »

jws wrote: post #54
worewood wrote: post #49

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" 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”.

> Clearly we have both had miraculous enlightenment because legally this is “not obvious”.

To be precise, legally it is "not obvious back in 1996." There is a lot of stuff that is obvious today that wasn't 25 years ago. That said, this one in particular probably would have been invalidated as obvious if it was ever litigated (and it was not). Also, the USPTO has reined in software patents a lot in recent years (but always people advocating for more or less).

Re: Finding the average of two unsigned integers without overflow

#68

Post by thayne »

lilyball wrote: post #14
nmilo wrote: post #7

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); } There's no way that should be patentable.

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.

> Algorithms aren't patentable

In the US, unfortunately,they can be (although not all algorithms are patentable). For example algorithms used in many media formats are patented.

Re: Finding the average of two unsigned integers without overflow

#69

Post by ziml77 »

justinpombrio wrote: post #23
ridiculous_fish wrote: post #3

The "SWAR" approach `(a & b) + (a ^ b) / 2` looks bizarre but can be understood. Adding two bits produces a sum and a carry: 0 + 0 = 0, carry 0 1 + 0 = 1, carry 0 0 + 1 = 1, carry 0 1 + 1 = 0, carry 1 So the sum is XOR, and the carry is bitwise AND. We can rewrite x + y as (x ^ y) + (x & y)*2 Distribute the divide, and you get (x ^ y)/2 + (x & y) which is the mystery expression. (Note this distribution is safe only b…

Alternatively, a direct explanation: 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.

This explanation makes a ton more sense!

Re: Finding the average of two unsigned integers without overflow

#70

Post by TheDong »

lilyball wrote: post #14
nmilo wrote: post #7

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); } There's no way that should be patentable.

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.

Algorithms are not meant to be patentable, per alice[0], but that does not mean they are not patentable in practice. The theoretical intent of what is patentable certainly differs from what is enforcible as a patent in practice.

LZW compression[1] was patented, and Unisys actually had success extracting license fees with it[2]. In that sense, clearly an algorithm was "patented enough" that the patent was granted and used, even though the patent is literally just math. The MP3 patent is also just a mathematical algorithm which had even more legal success.

So, while technically algorithms are not patentable, in reality, the USPTO will grant patents for algorithms if you write enough legal gunk around them, and the difference doesn't really matter when a patent troll is sending threatening emails and your lawyers are demanding 20x the licensing fee to take the case.

[0]: https://en.wikipedia.org/wiki/Alice_Corp._v._CLS_Bank_Intern...

[1]: https://patents.google.com/patent/US4558302A/en

[2]: https://www.itweb.co.za/content/JBwErvn5oNOq6Db2

Post reply on HN