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

101–110 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#101

Post by stathibus »

yalogin wrote: post #93

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.

Re: Finding the average of two unsigned integers without overflow

#102

Post by Dylan16807 »

xaduha wrote: post #87
jws wrote: post #55

Earlier quoted context omitted.

Your compiler will take care of that. Leave the division for the humans to read.

I'm in a camp that thinks compilers should also take care of the original unsigned average(unsigned a, unsigned b) { return (a + b) / 2; } At the end of the day it's all just text. There are plenty of steps before any of it does anything at all.

What should happen if you store "a+b" in an intermediate value?

Re: Finding the average of two unsigned integers without overflow

#103

Post by [deleted] »

b112 wrote: post #78
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/

But in as it is non-obvious, as to why it is non-obvious, criteria met.

[deleted]

Re: Finding the average of two unsigned integers without overflow

#104

Post by Dylan16807 »

cma wrote: post #100
Dylan16807 wrote: post #97

Earlier quoted context omitted.

> The USPTO is a lot different now, a quarter-century later. Please be more specific or link something that explains how they've improved.

Back then you couldn't early challenge a patent and prevent it from being issued, and once it was issued you couldn't challenge it without violating it and entering trial. Now you can do both.

Early challenging sounds helpful, but that's also outsourcing the work and it could put more coders at risk of treble damages further down the line from some patent they glanced at and forgot about.

Re: Finding the average of two unsigned integers without overflow

#105

Post by Agentlien »

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/

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.

Re: Finding the average of two unsigned integers without overflow

#106

Post by Dylan16807 »

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.

It makes very little sense as a circuit, because you'd just put in a 33 or 65 bit adder.

Re: Finding the average of two unsigned integers without overflow

#107

Post by speedgoose »

thayne wrote: post #68
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.

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

I wonder how many US companies use ffmpeg without knowing about their patent situation. Using ffmpeg on Europe or USA is not the same.

https://ffmpeg.org/legal.html

Re: Finding the average of two unsigned integers without overflow

#108

Post by cphoover »

johnhenry wrote: post #98

I saw the title and thought to just do "(a / 2) + (b / 2)" and a do a little bit of fudging if a or b is odd. After reading the article, learning that unsigned average(unsigned a, unsigned b) { return (a / 2) + (b / 2) + (a & b & 1); } was once patented actually made me a bit sad for our entire system of patents.

Why is math patentable? seems crazy to me

Re: Finding the average of two unsigned integers without overflow

#109

Post by xbmcuser »

LudwigNagasena wrote: post #94
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?…

Quite “amazing” that googleblog layout breaks on iOS. It’s literally impossible to see half of the text without the reader mode.

Yeah iOS is becoming the new IE. No matter how much people complain about google's chrome domination they at least try to keep up with the standards. iOS browser does not and they even lock the devices to their browser so you can't even choose a browser with a different engine
Post reply on HN