Live data from Hacker News

Finding the average of two unsigned integers without overflow

devblogs.microsoft.com

121–130 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#121

Earlier quoted context omitted.

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

this isn't an iOS issue. That blog post is broken on Firefox Android as well, and in Chrome dev tools. There is a display inline-block messing it up. The newer blog posts display fine.

Re: Finding the average of two unsigned integers without overflow

#122

Just by reading the headline, before opening the article, I thought of the patented solution in my head. "Just halve before adding, it can be off by one but some boolean logic might do it" Software patents are absolutely disgusting.

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

So the compiler developers had to pay fees? Or Intel and AMD?

Re: Finding the average of two unsigned integers without overflow

#123

Earlier quoted context omitted.

> Clearly we have both had miraculous enlightenment because legally this is “not obvious”. To be precise, legally it is "not obvious back in 1996." There is a lot of stuff that is obvious today that wasn't 25 years ago. That said, this one in particular probably would have been invalidated as obvious if it was ever litigated (and it was not). Also, the USPTO has reined in software patents a lot in recent years (but a…

Seriously, I could have done this in 1996 and so could anyone. I reckon I could probably have worked this out in 1986. It’s not like binary arithmetic has changed significantly in the last 20 years.

And back in 1996, programmers were much more familiar with bit-twiddling than today.

Re: Finding the average of two unsigned integers without overflow

#124
post #80

Earlier quoted context omitted.

Why not just (a >> 1) + (b >> 1) + (a & 1) & (b & 1)

"just"? That's 2 additions, 2 shifts, and 2-3 bitwise operations, while the other method is 1 addition, 1 shift, and 2 bitwise operations.

I would think optimizing compilers can optimize this expression to the one in the article, but I tried it on godbolt and they don't.

Re: Finding the average of two unsigned integers without overflow

#126
post #87
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.

For C at least, the spec says that unsigned addition is modulo 2^64 (or 32 or 16 or whatever) so, imagine you had an 8 bit unsigned, 128+128 gives you 0. Divided by 2 is 0. That’s the right answer by the language specification. The trick is to get 128.

Re: Finding the average of two unsigned integers without overflow

#127

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

Re: Finding the average of two unsigned integers without overflow

#128

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/

And what is the intention to make the patent? The second way is actually more useful, not limited to unsigned ints.

Re: Finding the average of two unsigned integers without overflow

#129

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…

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

There's also the overhead of getting the numbers in and out of memory. Loading and storing one word is obviously going to be way better than loading 4 bytes individually.

It seems to me like the vectored approach would be better for algorithms that require iterating through a large dataset in memory. The scalar approach would be better for algorithms that have a bunch of dependent calculations. Perhaps that's an obvious conclusion!

That's pretty neat though. For the large dataset scenario, perhaps you could get a significant speedup on relatively simple architectures such as cortex-m microcontrollers. I suspect that sufficiently modern high end CPUs/compilers wouldn't benefit so much from it, though? All the pipelining, superscaling and caching and whatnot could sufficiently mask the latencies of the memory accesses to the point of being irrelevant. Also, a sufficiently clever compiler could implement the loop with actual SIMD instructions and achieve significantly higher performance than the manual in-register optimization.

This would be a fun way to compute a basic 8-bit checksum on a binary blob in a microcontroller... Not that it would be practically useful because any non-trivially sized blob would be better served with at least a Fletcher checksum if not a full CRC, both of which seemingly lack the necessary associativity.

Re: Finding the average of two unsigned integers without overflow

#130
post #110

This was a lot more thorough and in-depth than I expected it to be. But that's Raymond Chen for you. One of the reasons I love Python is that integers never overflow, so this becomes a trivial problem.

Rounding in Python is interesting though: https://www.askpython.com/python/built-in-methods/python-rou... "Also, if the number is of the form x.5, then, the values will be rounded up if the roundup value is an even number. Otherwise, it will be rounded down. For example, 2.5 will be rounded to 2, since 2 is the nearest even number, and 3.5 will be rounded to 4."

Round half to even is well known outside Python. It's sometimes called bankers' rounding.
Post reply on HN