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 solution is a little more complex. But not by much.
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 can have your entire company's activity combed through with a microscope if they find a sympathetic court), and blast you with enough charges and threaten sequential jail time so that you cannot reasonably do anything other than plead guilty and forfeit your right to a fair trial [2].
And for what it's worth, that "play by the rules as we want or we will destroy you" tactic can even hit multi-billion dollar companies like Epic Games. It's one thing if society decides to regulate business practices by the democratic process of lawmaking... but the fact that Apple can get away banning perfectly legal activities such as adult content, vaping [3] or using a non-Apple payment processor from hundreds of millions of people is just insane, not to mention incredibly damaging to the concept of democracy.
[1]: https://kottke.org/13/06/you-commit-three-felonies-a-day
[2]: https://innocenceproject.org/guilty-pleas-on-the-rise-crimin...
[3]: https://www.macrumors.com/2020/06/01/pax-vape-management-web...
I would not be so certain about that one.
Many countries are thinking of outright "meat taxes", health scores (similar to smoking warnings in the desired nudging effect) or extending CO² taxes onto agriculture: meat production causes about 14% of global CO² emissions [1], and outlawing/disincentivizing meat consumption is a very easy, very fast and incredibly effective way of cutting down on CO², methane and dung emissions. Not to mention the indirect emissions from land burning (especially in Brazil) or the societal cost of overconsumption of meat (e.g. obesity and heart issues).
Personally, I'm in the "omnivore" camp but recognize that the way how we deal with meat products has to be massively reformed. We need to cut waste and curb consumption, the sooner the better.
[1]: https://www.theguardian.com/environment/2021/sep/13/meat-gre...
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 one could do with bit operations to avoid it. But, still being tired, I decided I didn't want to actually spend time thinking on the problem and I'd already spent a minute on it.
Actually I was curious to see if GCC would be smart enough to automatically choose what's the best optimization depending on the underlying architecture, but it doesn't appear to be the case.
For x86_64 (with -O3 or -Os):
avg_64bits:
.LFB0:
.cfi_startproc
movl %edi, %edi
movl %esi, %esi
leaq (%rdi,%rsi), %rax
shrq %rax
ret
.cfi_endproc
avg_patented_do_not_steal:
.LFB1:
.cfi_startproc
movl %edi, %eax
movl %esi, %edx
andl %esi, %edi
shrl %eax
shrl %edx
andl $1, %edi
addl %edx, %eax
addl %edi, %eax
ret
For ARM32 (-O3 and -Os):
avg_64bits:
push {fp, lr}
movs r3, #0
adds fp, r1, r0
adc ip, r3, #0
mov r0, fp
mov r1, ip
movs r1, r1, lsr #1
mov r0, r0, rrx
pop {fp, pc}
avg_patented_do_not_steal:
and r3, r1, #1
ands r3, r3, r0
add r0, r3, r0, lsr #1
add r0, r0, r1, lsr #1
bx lr
My code, for reference:
uint32_t avg_64bits(uint32_t a, uint32_t b) {
uint64_t la = a;
uint64_t lb = b;
return (la + lb) / 2;
}
uint32_t avg_patented_do_not_steal(uint32_t a, uint32_t b) {
return (a / 2) + (b / 2) + (a & b & 1);
}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 whether the shift had been applied to negative or positive numbers.
Except for following a tradition generated by a random initial choice, programming would have been in many cases easier if the convention for the division of signed numbers would have been to always generate positive remainders, instead of generating remainders with the same sign as the quotient.
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.
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.
the patented solution immediately came to mind
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.
And it's from 1996.
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.
The only difference between this patent and say a media codec is how long it would take to reinvent it. It might take you 200 years to come up with something as good as h.265, but there's no magic to it. There's a problem, somebody came up with a solution, somebody else could do it again given enough time to work on it. This is true for everything that's ever been patented.
The point of patents is to compensate for value of the work needed to reinvent, and so the real problem here is that value is less than any sane minimum. The value is less than the patent examiner's time to evaluate it! But court rulings have said it doesn't matter how insignificant a patent is, as long as it does anything at all it's "useful", which leads to these kinds of worthless patents.
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 express it as:
avg = [x>>1 + y>>1, x>>1 + y>>1 + 1][x&y&1]
The patented expression is computable in an obvious way by a single ordinary adder and a single AND gate connected to the carry input of the adder, without any other devices (the shifts and the "& 1" are done by appropriate connections).
Any ordinary N-bit adder computes the sum of 3 input operands, 2 which are N-bit, and a third which is an 1-bit carry.
If a significant fraction of people come up with it on the spot, it's obvious. And they did.
Keep in mind this solution was to support MPEG-1 video encoding in the olden days when state of the art processors were 100 MHz and 800 nm process. Doing this in 1 cycle while reusing already existing function units seems like a clever solution to me -- not patent-worthy, not difficult, but clever.
If so then the technique in the post isn't actually patented.
If that C code would get threatened, then the 1 cycle thing is a red herring.
Also "Doing this in 1 cycle while reusing already existing function units"? In hardware you can use a normal adder without any special technique...
Any logic designer, who is not completely incompetent, when seeing the expression
(a / 2) + (b / 2) + (a & b & 1);
will notice that this is a 1-cycle operation, because it is just an ordinary single addition.
In hardware the divisions are made just by connecting the bits of the operands in the right places. Likewise, the "& 1" is done by connecting the LSB's of the operands to a single AND gate and the resulting bit is connected to the carry of the adder, so no extra hardware devices beyond a single adder are needed. This is really absolutely trivial for any logic designer.
The questions at any hiring interview, even for beginners, would be much more complex than how to implement this expression.
It is absolutely certain that such a patent should have never been granted, because both the formula and its implementation are obvious for any professional in the field.
Our experiences and training has changed dramatically over the past 26 years.
The patent issued in 1996 and wasn't revisited since then (because never asserted in litigation). The USPTO is a lot different now, a quarter-century later.
Not true. See https://en.wikipedia.org/wiki/Reexamination It's even easier today than a decade ago, though the Wikipedia article doesn't explain that aspect very well. (I wouldn't be able to explain it, either. I think it has to do with reduced ability for a patent owner to drag out review, including dragging it into court.) Probably not nearly easy enough, though.
Please be more specific or link something that explains how they've improved.