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

161–170 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#161

Post by SkeuomorphicBee »

kuboble wrote: post #127
rustybolt wrote: post #115

> There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016. That's completely retarded; it's literally the first solution I think of when I hear this problem.

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.

If a phone is the first solution that comes to mind for a person that never saw or heard of a phone in their life, then that indicates phone was a bad patent.

Re: Finding the average of two unsigned integers without overflow

#162

Post by [deleted] »

rustybolt wrote: post #118
AnotherGoodName wrote: post #36

Earlier quoted context omitted.

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

If you, for example, want to do addition of four 8-bit integers within a 32-bit register, you have to use similar techniques to stop the carry from propagating. For example, when x and y are 32-bit integers holding 4 8-bit integers, you can do z = (x ^ y) + (x & y) & 0x7f7f7f7f; Now z holds four 8-bit integers which hold the sum (modulo 256) of the integers of x and y. The bit mask is to stop the carry from propagati…

[deleted]

Re: Finding the average of two unsigned integers without overflow

#164

Post by bsdetector »

ChrisLomont wrote: post #154
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/

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. And it's from 1996.

This thread is full of people who challenged themselves to solve it and then failed to come up with the 'obvious' 1-cycle solution. It's clearly non-obvious, as this thread shows.

The actual patent system failure here is the patent is not useful -- it's not valuable. If you needed this solution, you could sit down and derive it in less than an hour. That's not because it's obvious, but because the scope is so small.

The only difference between this patent and say a media codec is how long it would take to reinvent it. It might take you 200 years to come up with something as good as h.265, but there's no magic to it. There's a problem, somebody came up with a solution, somebody else could do it again given enough time to work on it. This is true for everything that's ever been patented.

The point of patents is to compensate for value of the work needed to reinvent, and so the real problem here is that value is less than any sane minimum. The value is less than the patent examiner's time to evaluate it! But court rulings have said it doesn't matter how insignificant a patent is, as long as it does anything at all it's "useful", which leads to these kinds of worthless patents.

Re: Finding the average of two unsigned integers without overflow

#166

Post by tremon »

bsdetector wrote: post #164
ChrisLomont wrote: post #154

Earlier quoted context omitted.

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. And it's from 1996.

This thread is full of people who challenged themselves to solve it and then failed to come up with the 'obvious' 1-cycle solution. It's clearly non-obvious, as this thread shows. The actual patent system failure here is the patent is not useful -- it's not valuable. If you needed this solution, you could sit down and derive it in less than an hour. That's not because it's obvious, but because the scope is so small.…

and then failed to come up with the 'obvious' 1-cycle solution

That's unfair, as the commenters here are providing a software solution. The patent is about a hardware solution which involves two parallel adder circuits. It implements in hardware exactly what the software solution does, but you can't express it in software because there is no operand that expresses "implement this addition twice please". You'd have to express it as:

  avg = [x>>1 + y>>1, x>>1 + y>>1 + 1][x&y&1]
Which isn't 1-cycle either without the specialized adder.

Re: Finding the average of two unsigned integers without overflow

#167

Post by nonsequitur »

rustybolt wrote: post #118
AnotherGoodName wrote: post #36

Earlier quoted context omitted.

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

If you, for example, want to do addition of four 8-bit integers within a 32-bit register, you have to use similar techniques to stop the carry from propagating. For example, when x and y are 32-bit integers holding 4 8-bit integers, you can do z = (x ^ y) + (x & y) & 0x7f7f7f7f; Now z holds four 8-bit integers which hold the sum (modulo 256) of the integers of x and y. The bit mask is to stop the carry from propagati…

This doesn't work because you're not left-shifting (doubling) the carry. But when adding the shifted carry to (x ^ y) we're back to potentially overflowing the highest bits. The solution is to add the highest and the lower bits separately:

  lower = 0x7f7f7f7f;
  highest = ~lower;
  z = ((x & lower) + (y & lower)) ^ ((x ^ y) & highest);
Note this only improves performance for larger container integers.

Re: Finding the average of two unsigned integers without overflow

#168

Post by upofadown »

jagger27 wrote: post #85
umeshunni wrote: post #65

Earlier quoted context omitted.

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

That’s a pretty important distinction. If someone in the 1800s invented a mechanical calculator that could do this operation in a single crank, I don’t think anyone would upset about that patent.

But then the patent would not be on the logic but the mechanical implementation. The obviousness would need to be judged on that basis. The method can be implemented using straightforward combinational logic so the single crank/cycle is a given after you have come up with the obvious method.

Back before software patents were a thing, the "math" was not patentable. Eliminating software patents will be a return to the previous status quo.

Re: Finding the average of two unsigned integers without overflow

#169

Post by mschuster91 »

undecisive wrote: post #150
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/

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 soluti…

> Which makes me curious: what other patents have we violated in our day-to-day without even knowing it?

Patents are like the criminal code - always remember "Three Felonies a Day" [1]. The system is set up so that if you are one of the 99%, the 1% can come in and bust you at will if you become too much of an annoyance/threat. They will find something if they just keep digging deep enough (not to mention that they can have your entire company's activity combed through with a microscope if they find a sympathetic court), and blast you with enough charges and threaten sequential jail time so that you cannot reasonably do anything other than plead guilty and forfeit your right to a fair trial [2].

And for what it's worth, that "play by the rules as we want or we will destroy you" tactic can even hit multi-billion dollar companies like Epic Games. It's one thing if society decides to regulate business practices by the democratic process of lawmaking... but the fact that Apple can get away banning perfectly legal activities such as adult content, vaping [3] or using a non-Apple payment processor from hundreds of millions of people is just insane, not to mention incredibly damaging to the concept of democracy.

[1]: https://kottke.org/13/06/you-commit-three-felonies-a-day

[2]: https://innocenceproject.org/guilty-pleas-on-the-rise-crimin...

[3]: https://www.macrumors.com/2020/06/01/pax-vape-management-web...

Re: Finding the average of two unsigned integers without overflow

#170

Post by wongarsu »

kuboble wrote: post #127
rustybolt wrote: post #115

> There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016. That's completely retarded; it's literally the first solution I think of when I hear this problem.

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.

If the average expert in the field immediately comes up with the same or a very similar solution then it obviously isn't non-obvious, which is one of the tests for patentability.

In the case of the phone you already know the patented solution, which obviously makes it impossible for you to judge its obviousness. That presumable wasn't the case with GP and the presented problem.

Post reply on HN