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

131–140 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#131

Post by bonzini »

cphoover wrote: post #108
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

What is patentable is "this circuit to compute the average" where the circuit is an adder that drops the bottom bit from the addends, instead ANDing the two bottom bits and using the result as a carry-in.

Though actually it shouldn't be patented because it's an obvious implementation of a math formula (and math is not patentable).

Re: Finding the average of two unsigned integers without overflow

#132

Post by not2b »

staticassertion wrote: post #34
not2b wrote: post #27

Earlier quoted context omitted.

In practice it makes no difference, because digital logic designers haven't used schematic capture in a very long time. They most commonly write Verilog (or SystemVerilog, which is a superset), and it looks a lot like C: logic [31:0] a, b, average; assign average = (a >> 1) + (b >> 1) + (a & b & 32'd1);

Sorry, I don't understand what you mean. It makes no difference to whom? It definitely makes a difference to someone writing that code, since that code is not patented.

What I mean is that the circuit diagram is a way to sneak it past a patent examiner, but the software/hardware distinction is completely artificial as both are designed in much the same way.

Re: Finding the average of two unsigned integers without overflow

#134

Post by Beldin »

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.

Re: Finding the average of two unsigned integers without overflow

#135

Post by d_tr »

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.

The fact that patents require time and money makes this even more pathetic and appalling.

Re: Finding the average of two unsigned integers without overflow

#136

Post by dathinab »

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.

Re: Finding the average of two unsigned integers without overflow

#137

Post by grishka »

zanethomas wrote: post #83
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/

100% correct the patented solution immediately came to mind

It almost did for me. I thought that you should be able to divide each number by 2 (or shift one bit) before adding, but that would lose a 1 if both numbers have 1 in their least significant bit. The part with "a & b & 1" fixes that exact issue and is obvious to me in hindsight.

Re: Finding the average of two unsigned integers without overflow

#138

Post by wildmanx »

grishka wrote: post #137
zanethomas wrote: post #83

Earlier quoted context omitted.

100% correct the patented solution immediately came to mind

It almost did for me. I thought that you should be able to divide each number by 2 (or shift one bit) before adding, but that would lose a 1 if both numbers have 1 in their least significant bit. The part with "a & b & 1" fixes that exact issue and is obvious to me in hindsight.

> and is obvious to me in hindsight.

Everything is. That's kinda hindsight's thing.

Not so say that a few people in this thread probably saw this solution right away, but the "this was all obvious" crowd in this thread is a little too large for my taste. Be real, guys.

Re: Finding the average of two unsigned integers without overflow

#139

Post by danbruc »

vbezhenar wrote: post #116
Agentlien wrote: post #105

Earlier quoted context omitted.

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

x / 2 === x >> 1, it's fast.

For unsigned or positive x. Yes, the article is about unsigned integers, but some might see this for the first time and not be aware of this restriction. -3 / 2 == -1 but -3 >> 1 == -2.

Re: Finding the average of two unsigned integers without overflow

#140

Post by wildmanx »

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…

Thanks for this explanation.

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

Post reply on HN