6 ms·
Having done computer architecture and bit twiddling x86 in the ye olden days, I immediately, independently converged on the patented solution (code / circuit /
by errcorrectcode 5y ago
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/ https://patentdefenses.klarquist.com/obviousness-sec-103/
- phkahler 5y agoAgreed. I spent about a minute before reading it and came up with the first solution, didn't feel like thinking through the puzzle of how not to care which one is larger, and then settled on the one with the 2016 expiration date. All within 1 to 2 minutes. I briefly considered XOR but didnt feel like remembering more about it - the solution was obvious when I saw it. How any of that was ever patentable is a crime.
- hackthefender 5y ago> It goes to show how broken the USPTO is... 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.
- nerdponx 5y agoIsn't there also a recourse process by which you can get a patent invalidated? You can't expect USPTO to hire an expert in every single possible field.
- thfuran 5y agoI think that's usually resolved in court. By which I mean, I don't think there's process beyond choosing to fight any suit brought against you and hoping you win in court.
- wahern 5y ago> I don't think there's process beyond choosing to fight any suit brought against you and hoping you win in court. Not true. See https://en.wikipedia.org/wiki/Reexamination 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.
- kwhitefoot 5y agoWhy not?
- Dylan16807 5y ago> The USPTO is a lot different now, a quarter-century later. Please be more specific or link something that explains how they've improved.
- cma 5y agoBack then you couldn't early challenge a patent and prevent it from being issued, and once it was issued you couldn't challenge it without violating it and entering trial. Now you can do both.
- Dylan16807 5y agoEarly challenging sounds helpful, but that's also outsourcing the work and it could put more coders at risk of treble damages further down the line from some patent they glanced at and forgot about.
- b112 5y agoBut in as it is non-obvious, as to why it is non-obvious, criteria met.
- deleted 5y ago[deleted]
- zanethomas 5y ago100% correct the patented solution immediately came to mind
- grishka 5y agoIt 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.
- wildmanx 5y ago> 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.
- ygra 5y agoI guess the part about overflow in the title primes most experienced developers to immediately think about a solution where the added numbers are restricted beforehand to avoid the overflow. From there the obvious answer is to halve them, which leaves the next problem when the numbers are odd. 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.
- Agentlien 5y agoI just want to second this with my own experience just now: 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.
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- vbezhenar 5y agox / 2 === x >> 1, it's fast.
- Agentlien 5y agoIt's fast, but I figured doing that on both sides before adding looked a bit inelegant and maybe it could be avoided by doing "something something bit operations" and then I dropped the thought and clicked the link.
- simias 5y agoOn a modern architecture given that most integers are usually u32 by default but the underlying CPU deals with 64bits natively, I'd just cast to u64 and call it a day. 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 Clearly just casting to 64bits seems to denser code 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 A lot more register spilling in the 64bit version since it decides to do a true 64bit add using two registers and an adc. 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); }
- tapirl 5y agoAnd what is the intention to make the patent? The second way is actually more useful, not limited to unsigned ints.
- Tuna-Fish 5y agoBut it requires you to know which one is larger. The patented way is faster if you are working with unsigned.
- undecisive 5y agoThis 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 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?
- mschuster91 5y ago> 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 https://kottke.org/13/06/you-commit-three-felonies-a-day [2]: https://innocenceproject.org/guilty-pleas-on-the-rise-criminal-trials-on-the-decline/ https://innocenceproject.org/guilty-pleas-on-the-rise-crimin... [3]: https://www.macrumors.com/2020/06/01/pax-vape-management-website-skirts-app-ban/ https://www.macrumors.com/2020/06/01/pax-vape-management-web...
- Retric 5y agoFreedom means some people will do stuff you don’t like.
- ChrisLomont 5y agoThe patent is more sophisticated than what the article implies - it's a single clock cycle method, which no compiler I've ever seen will do given the code presented in the article. And it's from 1996.
- bsdetector 5y agoThis 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. 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.
- tremon 5y agoand 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 express it as: avg = [x>>1 + y>>1, x>>1 + y>>1 + 1][x&y&1] Which isn't 1-cycle either without the specialized adder.
- adrian_b 5y agoThere is no need for a specialized adder. 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.
- Ygg2 5y ago> Patents are supposed to be nonobvious 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-patents/ https://abovethelaw.com/2017/10/8-of-my-favorite-stupid-pate... https://patents.google.com/patent/US5443036A/en https://patents.google.com/patent/US5443036A/en https://patents.google.com/patent/US6360693 https://patents.google.com/patent/US6360693 Apple steals the cake though. By patenting a geometric shape.
- nikanj 5y agoI bet you broke this patent as a kid https://patents.google.com/patent/US6368227B1/en https://patents.google.com/patent/US6368227B1/en
- roberthahn 5y agoWhat is obvious today might not have been obvious in 1996. Our experiences and training has changed dramatically over the past 26 years.
- scotty79 5y agoI can assure you I would have come up with the patented solution just as fast in 1996 when I was a teenager and dabbled in 6502 assembler on Atari computer. Because I solved it now on the basis of exactly the expeirience and knowledge I acquired back then.