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
Finding the average of two unsigned integers without overflow
121–130 of 220 posts
Re: Finding the average of two unsigned integers without overflow
#122Just 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.
Re: Finding the average of two unsigned integers without overflow
#123Earlier 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.
Re: Finding the average of two unsigned integers without overflow
#124Earlier 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.
Re: Finding the average of two unsigned integers without overflow
#125This 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.
Re: Finding the average of two unsigned integers without overflow
#126Earlier 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.
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.
Re: Finding the average of two unsigned integers without overflow
#128Having 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/
Re: Finding the average of two unsigned integers without overflow
#129Earlier 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…
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
#130This 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."