151–160 of 220 posts
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.
It makes very little sense as a circuit, because you'd just put in a 33 or 65 bit adder.
Gcc and Clang both recognize the pattern of shifts and OR that reproduce a rotation, and substitute the actual instruction, no intrinsic needed.
I bet MSVC does too.
Earlier quoted context omitted.
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.
If you're not aware that numbers can overflow (and you probably don't tend to think about that for every single + you type, I guess), then the proper solution is less obvious.
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 it's from 1996.
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/
Emphasis on supposed.
The granted patents include: laser used to exercise cat, and mobile wood based dog game (log used to play fetch).
https://abovethelaw.com/2017/10/8-of-my-favorite-stupid-pate...
https://patents.google.com/patent/US5443036A/en
https://patents.google.com/patent/US6360693
Apple steals the cake though. By patenting a geometric shape.
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.
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?…
I want to reply to one of the comments you linked to, which is this: > I would argue that the bug is not in the algorithm -- the bug is in languages that don't detect integer overflow by default. Concretely, this is true enough. But abstractly, not so much: the algorithm is actually "buggy" if you abstract the problem a little. Namely, finding a midpoint of two operands does not require that the operands be numbers,…
Read https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63303 to see many problems around pointer differencing.
> 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.
Isn't it better to do (a>>1) + (b>>1) + (a&b&1) No division needed.
Not really. It is harder for most programmers to read (a>>1) than the simpler (a/2) and in most modern programming languages the compiler will notice the division by a power of two and compile to bit shift operations in both cases.
Really depends on where you're coming from. Anyone who has dipped their toes in embedded programming will immediately know they are equivalent, and many will correct /2 to a bitshift, because that's what you want to happen.
I get that bit twiddling is obscure outside of low level programming, but bit shifts really is kindergarten stuff in this domain.
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,…