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

181–190 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#181

Post by Retric »

mschuster91 wrote: post #169
undecisive wrote: post #150

Earlier quoted context omitted.

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

Freedom means some people will do stuff you don’t like.

Re: Finding the average of two unsigned integers without overflow

#182

Post by rustybolt »

sgtnoodle wrote: post #129
rustybolt wrote: post #118

Earlier quoted context omitted.

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…

That's pretty neat. Is it actually any faster than just doing four 8-bit adds, though? Presumably it would take 4 logical instructions to do the vectored math, vs. 4 logical instructions to do the scalar additions. I suppose you're looking at a minimum of two registers for the vectored approach, vs. 8 for the scalar approach. Having the result available in separate registers makes them immediately available for use,…

> That's pretty neat. Is it actually any faster than just doing four 8-bit adds, though?

The operation itself is not necessarily faster (it could be faster due to pipelining, I think, and it would probably ne faster when storing 8 8-bit ints in a 64-bit int), but it can save the hassle and runtime of packing and unpacking into four variables.

Re: Finding the average of two unsigned integers without overflow

#184

Post by roberthahn »

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/

What is obvious today might not have been obvious in 1996.

Our experiences and training has changed dramatically over the past 26 years.

Re: Finding the average of two unsigned integers without overflow

#185

Post by adrian_b »

danbruc wrote: post #178
adrian_b wrote: post #172

Earlier quoted context omitted.

You can use the appropriate right shift with signed integers as easy as with unsigned integers, you just have to handle in the right way the correction due to the bit shifted out. The fact that the right shift for a negative integer gives the floor function of the result just makes the correction easier than if you had used division with truncation towards zero. The shifted out bit is always positive, regardless whet…

With positive remainders you get wired quotient behavior. Why should 10/3 and -10/-3 yield different results? Besides that, the choice is not universal, different languages use different conventions.

Why should 10/3 and -10/-3 yield the same result?

I do not see where this would be of any use.

On the other hand, if you want a quotient that has some meaningful relationship with the ratio between the dividend and the divisor, there are other more sensible definitions of the integer division than the one used in modern programming languages.

You can have either a result that is a floating point number even for integer dividend and divisor, like in Algol, or you can define the division to yield the quotient rounded to even (i.e. with a remainder that does not exceed half of the divisor).

In both cases 10/3 and -10/-3 would yield the same result and I can imagine cases when that would be useful.

For the current definition of the integer division, I do not care whether 10/3 and -10/-3 yield the same result. It does not simplify any algorithm that I am aware of, while having a remainder of a known sign simplifies some problems by eliminating some tests for sign.

Re: Finding the average of two unsigned integers without overflow

#186

Post by tremon »

tremon wrote: post #166
bsdetector wrote: post #164

Earlier quoted context omitted.

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…

And I just realized the hardware solution is incredibly sub-optimal. If you were to design this in specialized hardware, you'd use a single (N+1)-bit adder and just discard the least significant bit in the output, not duplicate the entire adder tree in silicon.

Re: Finding the average of two unsigned integers without overflow

#187

Post by pchangr »

Retric wrote: post #181
mschuster91 wrote: post #169

Earlier quoted context omitted.

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

Freedom means some people will do stuff you don’t like.

This will for now on be my preferred quote against “freedom at all cost” arguments.

Re: Finding the average of two unsigned integers without overflow

#188

Post by rrss »

pclmulqdq wrote: post #171
upofadown wrote: post #168

Earlier quoted context omitted.

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…

We have eliminated most software patents: see Alice Corp vs CLS bank. The only thing this patent covers is the physical circuit implementation, not the math.

> The only thing this patent covers is the physical circuit implementation

The claims in that patent are not limited to a physical circuit implementation.

The description includes a circuit diagram as one possible embodiment of the claimed invention, but the patent covers any implementation (and the description indicates it was intended to cover instructions running on general purpose processors).

Re: Finding the average of two unsigned integers without overflow

#189

Post by mschuster91 »

Retric wrote: post #181
mschuster91 wrote: post #169

Earlier quoted context omitted.

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

Freedom means some people will do stuff you don’t like.

And democracy means, at its core, to restrict the freedom of people committing actions that society has decided to be unlawful.

Re: Finding the average of two unsigned integers without overflow

#190

Post by danbruc »

adrian_b wrote: post #185
danbruc wrote: post #178

Earlier quoted context omitted.

With positive remainders you get wired quotient behavior. Why should 10/3 and -10/-3 yield different results? Besides that, the choice is not universal, different languages use different conventions.

Why should 10/3 and -10/-3 yield the same result? I do not see where this would be of any use. On the other hand, if you want a quotient that has some meaningful relationship with the ratio between the dividend and the divisor, there are other more sensible definitions of the integer division than the one used in modern programming languages. You can have either a result that is a floating point number even for integ…

I was not really thinking about application but the mathematics. It seems a reasonable decision to me that |a / b| = |a| / |b| and to not get results of different magnitude depending on sign changes only.
Post reply on HN