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

41–50 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#41

Post by rrss »

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.

I disagree. Not all the claims include the “single instruction cycle,” and IMO several of the claims are general enough that one could make a case that a sequence of instructions directing the operation of a general purpose data path would be covered by the claim. (Claim 3, for example).

this would require a lawsuit to find out, but this wording in the description suggests the authors’ intent with the claims was to patent this method of computing an average on any processor:

> A general purpose computer or processor with suitable circuitry can execute the invention in a single instruction cycle (as is preferred) or multiple instruction cycles.

Re: Finding the average of two unsigned integers without overflow

#43

Post by [deleted] »

AnotherGoodName wrote: post #36
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…

Sorry i'm confused and i asked elsewhere. How is the above SWAR? It looks like a regular set of instructions.

[deleted]

Re: Finding the average of two unsigned integers without overflow

#45

Post by benmmurphy »

justin66 wrote: post #2

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. https://ai.googleblog.com/2006/06/extra-extra-read-all-about... https://news.ycombinator.com/item?id=3530104 https://news.ycombinator.com/item?…

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.

Re: Finding the average of two unsigned integers without overflow

#46

Post by paulsmith »

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…

It's a half-adder in software!

Re: Finding the average of two unsigned integers without overflow

#47

Post by rrss »

staticassertion wrote: post #37
danuker wrote: post #26

Earlier quoted context omitted.

> no defense. I am not a lawyer, but I suspect prior art is a defense.

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.

Re: Finding the average of two unsigned integers without overflow

#48

Post by tialaramex »

staticassertion wrote: post #38
tialaramex wrote: post #35

Earlier quoted context omitted.

Several of these patent claims are for "an apparatus" because you're not allowed to patent ideas - but any realisation of the algorithm will necessarily be "an apparatus" so the effect is that in fact you can claim algorithms and that's exactly what this is doing.

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 arrangement of gears and levers to propose, or some recipe of doping material A with chemical B and then doing so-and-such - that's a classical hardware patent, but the whole point of these "an apparatus" patents is that they aren't trying to describe a novel device anybody invented, they're describing the algorithm the patent is for the algorithm and phrases like "an apparatus" are just a wafer thin excuse for this to be waved through by people whose salary is paid for by the endless flood of such software patents.

As a parallel comment is explaining there hasn't for many years been any substantial difference between what seems to be very much "hardware" and what common folk think of as "software".

The patent application even spells it out, explaining that "A general purpose computer [...] can execute the invention in a single instruction cycle [...]". What "invention" do you suppose is being "executed" here? Is the general purpose computer... making a special circuit? Maybe your laptop is now selling DVD players to Best Buy? No. Their "invention" is just the algorithm, they successfully patented the algorithm.

Nobody would "stop you writing that algorithm", but if they wanted to, and if you've got enough money for it to be worth taking your money, while that patent was valid they could sue you for infringing on their invention and unless you've got deep pockets and proof you invented it first, you are screwed.

Re: Finding the average of two unsigned integers without overflow

#50

Post by dlubarov »

nmilo wrote: post #22
lilyball wrote: post #14

Earlier quoted context omitted.

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.

Yeah you're right, it seems like the article is misleading. Still, unless I'm reading it wrong it seems like the patent is just describing the hardware translation of this algorithm, it's not really adding anything new. It's still dubious to me.

Yeah, isn't the translation to a circuit even more trivial than the algorithm itself? a / 2 and b / 2 just discard bits. a & b & 1 is just an and of the two low bits. Then we just route those values to an adder (with carry).
Post reply on HN