21 ms·

Finding the average of two unsigned integers without overflow

448 points by mlex 5y ago

everyone 5y ago
I find it mind boggling that something as simple as this can actually be patented. unsigned average(unsigned a, unsigned b) { return (a / 2) + (b / 2) + (a & b & 1); } That makes the patent system seem broken to me.
justin66 5y ago
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-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about... https://news.ycombinator.com/item?id=3530104 https://news.ycombinator.com/item?id=3530104 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=9857392 https://news.ycombinator.com/item?id=9857392 https://news.ycombinator.com/item?id=12147703 https://news.ycombinator.com/item?id=12147703 https://news.ycombinator.com/item?id=621557 https://news.ycombinator.com/item?id=621557 https://news.ycombinator.com/item?id=7594625 https://news.ycombinator.com/item?id=7594625 https://news.ycombinator.com/item?id=9113001 https://news.ycombinator.com/item?id=9113001 https://news.ycombinator.com/item?id=16890739 https://news.ycombinator.com/item?id=16890739 If doomscrolling all that isn't enough to make you fear for mankind's future I'm pretty sure there's an Ulrich Drepper glibc bug report rejection related to this topic (or several) that you can google... On topic: Raymond's post has some other great stuff. SWAR!
- dataflow 5y ago
  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, or even addable for that matter. The introduction of that requirement is therefore a bug (at least in my eyes). The easiest way to see this is to replace integers with pointers. Then adding two pointers isn't even a well-defined operation in the general case, let alone dividing them by two. Whereas subtracting them and moving half the distance is actually quite well-defined, and we can see it behaves better too. I would probably go so far as to claim that this is not an isolated example of where thinking about problems more abstractly helps us come up with solutions that have non-obvious benefits.
  - ghusbands 5y ago
    Subtraction, division and addition is one of the common answers that is still wrong, unless you also want to do a comparison, first, and that is generally high cost. Read https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63303 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63303 to see many problems around pointer differencing.
    - adrian_b 5y ago
      A comparison never costs more than an addition or a subtraction. If you would use a conditional jump, that would have a high cost. However the maximum or minimum should always be computed without conditional jumps and many CPUs have special instructions for max and min, which are not more expensive than additions or subtractions. On CPUs without max & min instructions, computing max or min requires 2 instructions (compare + conditional copy). 2 instructions vs. 1 instruction increases the program size but not necessarily the execution time, if the instructions can be overlapped with others. Due to the complex architecture of modern CPUs, it is impossible to determine the cost of a simple sequence of instructions in the general case. For each particular CPU, a different but equivalent sequence of instructions can be the best and longer sequences of instructions may happen to be executed in less time, if they can be better overlapped on a certain CPU.
      - ghusbands 5y ago
        The obvious form of the code with a comparison still produces a conditional branch on latest gcc [1]. It's extremely doubtful that you'll find a version that uses any comparison that consistently performs as quickly as any version that uses a little bit-twiddling, no matter what modern CPU you're talking about. Many of your statements are misleading in context. Implying that you can't know or deduce things about the cost of a simple sequence of instructions is very odd. All software and people that work on optimization do it all the time. And remember that the context is a suggestion that pointer types and pointer-subtraction is the answer to a question about integers, so getting into detail about instruction sequences isn't really going to help, as the basic idea is flawed. [1] https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:34,endLineNumber:22,positionColumn:34,positionLineNumber:22,selectionStartColumn:34,selectionStartLineNumber:22,startColumn:34,startLineNumber:22),source:'volatile+long+double+x%3B%0Atypedef+unsigned+int+uint%3B%0A%0Auint+badmid(uint+a,+uint+b)+%7B%0A++++return+(a+%2B+b)+/+2%3B%0A%7D%0A%0Auint+cmpmid(uint+a,+uint+b)+%7B%0A++++if+(a+%3E+b)+%7B%0A++++++++return+b+%2B+(a+-+b)+/+2%3B%0A++++%7D%0A++++else+%7B%0A++++++++return+a+%2B+(b+-+a)+/+2%3B%0A++++%7D%0A%7D%0A%0Auint+bitmid(uint+a,+uint+b)+%7B%0A++++return+(a%3E%3E1)+%2B+(b%3E%3E1)+%2B+(1%26a%26b)%3B%0A%7D%0A%0Auint+bit2mid(uint+a,+uint+b)+%7B%0A++++return+(a+%26+b)+%2B+(a+%5E+b)+/+2%3B%0A%7D'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:gsnapshot,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-O3',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1,tree:'1'),l:'5',n:'0',o:'x86-64+gcc+(trunk)+(C%2B%2B,+Editor+%231,+Compiler+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(file...
- benmmurphy 5y ago
  The Java solution is simpler because they are finding the average of 2 positive signed integers. So if you add 2 31 bit positive signed integers the result will fit in 32 bits and then you can just do an unsigned right shift to get the average.
- smaddox 5y ago
  > I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. I haven't seen the mentioned proof, but if said proof is not formal and mechanized and/or does not consider all possibilities, including overflow, then should we really consider it to be a proof of correctness? It might prove some desirable properties, but I don't think we should leave it at that. I certainly don't think we should claim that "It is not sufficient merely to prove a program correct; you have to test it too." When it comes to software programs, I believe proofs can and should be exhaustive. That does not necessarily mean you need to exhaustively test every input, but it does mean you need to prove correctness for every input, including inputs that might result in overflow or undefined behavior. Otherwise, we should not consider it a proof of correctness.
  - wildmanx 5y ago
    It was a formal proof, but one based on a false assumption, namely that x+y for two ints x and y is an int and a well-defined operation. It's not. The trust in the significance of a proof is limited by the trust in the statement to be proven. The statement to be proven was "If XYZ assumptions about the statements in the underlying language hold, then the result of that function is the result of a binary search". The proof is correct. Just that XYZ contained something incorrect. There is no free lunch. Even if we prove all our software formally correct, we still need to "program" the specifications, with all that comes with it. They can contain bugs, need to be debugged, revisited, etc. The above is an excellent example of this.
- LudwigNagasena 5y ago
  Quite “amazing” that googleblog layout breaks on iOS. It’s literally impossible to see half of the text without the reader mode.
  - xbmcuser 5y ago
    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
    - deckard1 5y ago
      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.
ridiculous_fish 5y ago
The "SWAR" approach `(a & b) + (a ^ b) / 2` looks bizarre but can be understood. Adding two bits produces a sum and a carry: 0 + 0 = 0, carry 0 1 + 0 = 1, carry 0 0 + 1 = 1, carry 0 1 + 1 = 0, carry 1 So the sum is XOR, and the carry is bitwise AND. We can rewrite x + y as (x ^ y) + (x & y)*2 Distribute the divide, and you get (x ^ y)/2 + (x & y) which is the mystery expression. (Note this distribution is safe only because (x & y)*2 is even.)
- justinpombrio 5y ago
  Alternatively, a direct explanation: a & b is the bits they have in common. If they both have a bit x, you should keep it, because the average of x and x is x. a ^ b is the bits that only one of them have. You should halve these bits, because the average of x and 0 is x/2.
  - ziml77 5y ago
    This explanation makes a ton more sense!
    - wildmanx 5y ago
      But it has lots of assumptions/prerequisites about taking the mean baked-in. It happens to work for this particular case, but in general you don't get far with such hand-wavy reasoning since you just get confused with which assumptions hold and which don't. The original explanation was the actual SIMD approach, which is really cool. You can extend it right away to other problems.
      - ggrrhh_ta 5y ago
        The explanation seems to work even in base 10. Let's do the average of 85 and 95. The leftmost digit of both is equal, so we leave it: X5 The "xor"/2 is the sum of the non equal digits divided by 2 (respecting their powers): (8+9)10 = (17)10 = 85 Now, we add them: 5 + 85 = 90 (which is the average of 85 and 95). Let's take now 87 and 89: The rightmost digits are equal: 8X We do the 'xor'/2 for the left most: (7+9)/2 = 8 8X + 8 = 88 Let me know if there are some examples for which it would fail (I only spent a minute to test if the explanation extends to other bases).
kingcharles 5y ago
Some unreal solutions here that show how amazing mathematics can be. Especially that Google patented method that only just recently expired. Props for including the assembler breakdown for every major CPU architecture.
- readthenotes1 5y ago
  It was a Samsung patent. Only the document was hosted by Google
- ijidak 5y ago
  I had to lol when I saw there was a patent for that. Divide both operands by 2 was my first idea before loading the page. (I like to try that sometimes before reading the articles.) I didn't think about the carry bit, but it seems like that would be a logical solution after 5 minutes of extra thinking. I'm not sure how that's patentable. That's insane to me. But maybe there is more too it. I didn't read the patent itself.
  - staticassertion 5y ago
    https://patents.google.com/patent/US6007232A/en https://patents.google.com/patent/US6007232A/en The patent is for a circuit design to perform that algorithm in a single cycle. The algorithm was never patented, nor could it be.
    - not2b 5y ago
      In practice it makes no difference, because digital logic designers haven't used schematic capture in a very long time. They most commonly write Verilog (or SystemVerilog, which is a superset), and it looks a lot like C: logic [31:0] a, b, average; assign average = (a >> 1) + (b >> 1) + (a & b & 32'd1);
      - staticassertion 5y ago
        Sorry, I don't understand what you mean. It makes no difference to whom? It definitely makes a difference to someone writing that code, since that code is not patented.
nmilo 5y ago
There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016: unsigned average(unsigned a, unsigned b) { return (a / 2) + (b / 2) + (a & b & 1); } There's no way that should be patentable.
- version_five 5y ago
  Yeah, when I read the article title, this is how I thought I would do it. Anything that obvious is not patentable in principle, but in practice, Samsung could still destroy any small business it wanted to by taking them to court over it. The patent system is awful
  - deleted 5y ago
    [deleted]
- throwaway22032 5y ago
  That's utterly hilarious. I've never come across this problem before, I read the headline and that solution came into my head immediately before I'd even clicked. I don't think I'm clever, surely half of HN feels the same way. Software patents are comical.
  - staticassertion 5y ago
    The article is in error. It isn't patented.
- coutego 5y ago
  Exactly. I saw the title, thought "I wonder what other way there is to do this than the obvious one of pre-dividing by 2" and then opened the article and saw that the trivial way to do it was covered by a patent. Wow! Just wow...
  - amelius 5y ago
    Well, we're the ones allowing the patent scam to continue ...
AnotherGoodName 5y ago
I noticed the following is in the middle of the article with no context that no one else is mentioning: unsigned average(unsigned a, unsigned b) { return (a & b) + (a ^ b) / 2; } A quick sanity check of this 23 & 21 = 21 23 ^ 21 = 2 21 + 2 / 2 = 22 (order of operations) I wonder why this is there. It seems the best solution but no one else is mentioning it. It also has no context near it. Nor is it stated correctly. It's just there on it's own.
- 829588225 5y ago
  23 ^ 21 = 2
  - AnotherGoodName 5y ago
    Sorry, edited the above. This is straight up right then which is weird. It's just there in the middle of the article with no context. In the middle of the SWAR method.
    - shannongreen 5y ago
      It is the SWAR method. Another comment explains it well, it basically treats each bit position as a 2-bit adder.
- jlynn 5y ago
  The average of 23 and 21 is indeed 22.
  - AnotherGoodName 5y ago
    Oh right, sorry i'll edit this. It works straight up then. Weird it's there with no context.
- deleted 5y ago
  [deleted]
classichasclass 5y ago
He hinted at this obliquely, but the PowerPC family of bit rotate instructions (ridicl, rlwinm, rlwimi, etc.), although intimidating in the general case, allows shifting, rotation, insertion, masking and more. There are many alternative mnemonics to try to reduce the cognitive complexity but all of these just assemble to them with particular parameters.
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 ago
  Agreed. 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 ago
    Isn'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 ago
      I 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
leptoniscool 5y ago
This seems fundamental, surprised elementary operations hasn't been made a part of every major language/framework.
- mzs 5y ago
  >Bonus chatter: C++20 adds a std::midpoint function that calculates the average of two values (rounding toward a).
avmich 5y ago
Does this all work with BCD encoding?
worewood 5y ago
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.
- jws 5y ago
  Absolutely the same thing I did. I even had the low bit logic worked out by the time I scrolled the article down and saw the patented line. Clearly we have both had miraculous enlightenment because legally this is “not obvious”.
  - hackthefender 5y ago
    > 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 always people advocating for more or less).
    - doctor_eval 5y ago
      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.
      - unnah 5y ago
        And back in 1996, programmers were much more familiar with bit-twiddling than today.
    - ______-_-______ 5y ago
      It's not even computer science, it's literally just math. (a+b)/2 = a/2 + b/2. They were teaching that in pre-algebra in middle schools well before 1996.
bufferoverflow 5y ago
Isn't it better to do (a>>1) + (b>>1) + (a&b&1) No division needed.
- jws 5y ago
  Your compiler will take care of that. Leave the division for the humans to read.
  - xaduha 5y ago
    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.
    - Dylan16807 5y ago
      What should happen if you store "a+b" in an intermediate value?
      - xaduha 5y ago
        If it is used and there's no way around it, then show a compilation warning that there might be overflow. If it can be resolved without being directly used, then it should be optimized away.
    - jws 5y ago
      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.
- 8jy89hui 5y ago
  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.
favorited 5y ago
Marshall Clow gave a pretty excellent CppCon talk covering these exact problems, called "std::midpoint? How Hard Could it Be?" https://www.youtube.com/watch?v=sBtAGxBh-XI https://www.youtube.com/watch?v=sBtAGxBh-XI
- rrss 5y ago
  yes, this is linked from the article
blobbers 5y ago
This guy hacks.
Subsentient 5y ago
Eh. I just cast both to a bigger integer type where possible, which in practice, is almost always. So if I'm averaging two uint32_ts, I just cast them to uint64_t beforehand. Or in Rust, with its lovely native support for 128-bit integers, I cast a 64-bit integer to 128-bit.
benlivengood 5y ago
Before reading the article: In x86 assembly, add ax, bx ; rcr ax, 1 works. I guess technically that is with overflow, but using overflow bits as intended. EDIT: it's included in the collection of methods in the article as expected.
- jart 5y ago
  That's lovely. I missed it when reading the article. It's also the winner on AMD Zen architecture based on MCA analysis. unsigned midpoint(unsigned a, unsigned b) { asm("add\t%1,%0\n\t" "rcr\t%0" : "+r"(a) : "r"(b)); return a; } Although `(a & b) + (a ^ b) / 2` is probably the more conservative choice.
yalogin 5y ago
I cannot believe that solution was allowed to be patented. How crappy is our patent process? Most engineers writing code would come up with that solution first.
- stathibus 5y ago
  Every patent attorney I've ever worked with has emphasized that engineers are not equipped to determine if an idea is obvious and should let the PTO decide. They say this because they know the USPTO strategy is to just hand out patents after putting in some bare minimum effort to review, and postpone the real review process to the unlikely day that someone chooses to challenge it in court and can pay private firms to do their job for them. The winners in this arrangement are the government, the big law firms, and the large corporations that can afford them.
johnhenry 5y ago
I saw the title and thought to just do "(a / 2) + (b / 2)" and a do a little bit of fudging if a or b is odd. After reading the article, learning that unsigned average(unsigned a, unsigned b) { return (a / 2) + (b / 2) + (a & b & 1); } was once patented actually made me a bit sad for our entire system of patents.
- cphoover 5y ago
  Why is math patentable? seems crazy to me
  - bonzini 5y ago
    What is patentable is "this circuit to compute the average" where the circuit is an adder that drops the bottom bit from the addends, instead ANDing the two bottom bits and using the result as a carry-in. Though actually it shouldn't be patented because it's an obvious implementation of a math formula (and math is not patentable).
mark-r 5y ago
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.
- nickm12 5y ago
  Raymond Chen is a treasure.
- erwincoumans 5y ago
  Rounding in Python is interesting though: https://www.askpython.com/python/built-in-methods/python-round 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."
  - scatters 5y ago
    Round half to even is well known outside Python. It's sometimes called bankers' rounding.
  - mark-r 5y ago
    Yes it is. But nobody said anything about rounding!
    - deleted 5y ago
      [deleted]
rustybolt 5y ago
> 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.
- kuboble 5y ago
  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.
  - ghusbands 5y ago
    It was obvious in 1996, too. It is and was the most obvious solution for a programmer fully aware of the problem and wanting to avoid comparisons.
  - SkeuomorphicBee 5y ago
    If a phone is the first solution that comes to mind for a person that never saw or heard of a phone in their life, then that indicates phone was a bad patent.
  - wongarsu 5y ago
    If the average expert in the field immediately comes up with the same or a very similar solution then it obviously isn't non-obvious, which is one of the tests for patentability. In the case of the phone you already know the patented solution, which obviously makes it impossible for you to judge its obviousness. That presumable wasn't the case with GP and the presented problem.
- d_tr 5y ago
  The fact that patents require time and money makes this even more pathetic and appalling.
unwind 5y ago
Very cool. I was surprised that the article didn't mention the need for this in binary search, and the famous problems [1] that occured due to naive attempts. [1]: https://en.m.wikipedia.org/wiki/Binary_search_algorithm https://en.m.wikipedia.org/wiki/Binary_search_algorithm
phs318u 5y ago
I got a pang of nostalgia seeing the Alpha AXP instructions.
Beldin 5y ago
Since this discussion is all about patents: my 2 cents on improving the patent system. Consider a term project of an undergraduate CS course, where the goal is spelled out, but the method is left for discovery. Methods developed within any such project immediately invalidate patents. They're apparently obvious to folks learning to become "skilled in the art". Yes, in practice, reaching a legal threshold would be hard (are you sure the students didn't read the patent or any description directly resulting from it?). But I'd definitely run a "patent invalidation course" - if I had confidence that the results would actually affect patents.
dathinab 5y ago
how is turning (a+b)/2 into a/2 + b/2 + a&b&1 even patentable? Turning (a+b)/2 into a/2 + b/2 is basic obvious math. If you do it and to any basic testing you will realize you are getting of by one errors, locking at them can then make it obvious that when they appear and hence how to fix them. Sure a proof is more complex, but then you can just trivially test it for all smaller-bit numbers over all possible inputs, hence making proofs unnecessary (for that numbers). This is a solution a not yet graduated bachelor student can find in less then a day. Having granted a patent for this should lead to disciplinary measurements against the person granting the patent tbh.
hollowturtle 5y ago
Wait, what? How can a patent right be applied on a one line of code that eventually is compiled down to machine code? Sounds ridicolous to me
Findecanor 5y ago
As an asm geek, I wasn't surprised to read that taking advantage of the carry flag yielded the most efficient code for some processors. I recalled that some ISAs also have special SIMD instructions specifically for unsigned average, so I looked them up: * x86 SSE/AVX/AVX2 have (V)PAVGB and (V)PAVGW, for 8-bit and 16-bit unsigned integers. These are "rounding" instruction though: adding 1 to the sum before the shift. * ARM "Neon" has signed and unsigned "Halving Addition". 8,16 or 32 bit integers. Rounding or truncating. * RISC-V's new Vector Extension has instructions for both signed and unsigned "Averaging Addition". Rounding mode and integer size are modal. * The on-the-way-out MIPS MSA set has instruction for signed, unsigned, rounded and truncated average, all integer widths. Some ISAs also have "halving subtraction", but the purpose is not as obvious.
ncmncm 5y ago
> gcc doesn’t have a rotation intrinsic, so I couldn’t try it there 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.
- adrian_b 5y ago
  They recognize how to do a rotation of an unsigned integer value, but they do not recognize how to do the rotation of that value concatenated with the carry bit, which is needed here.
user-the-name 5y ago
"unsigned long long"? It's 2022. stdint.h is old enough to drink, and is probably married with a kid on the way. Just include it already?
MaxBarraclough 5y ago
Reminds me of a Stack Overflow thread, Shortest way to calculate difference between two numbers? [0] Multiple answers ignored the possibility of overflow. [0] https://stackoverflow.com/q/10589559/ https://stackoverflow.com/q/10589559/
dpacmittal 5y ago
You could also do (a + (b-a)/2) where a is the smaller number.
dralley 5y ago
> I find it amusing that the PowerPC, patron saint of ridiculous instructions, has an instruction whose name almost literally proclaims its ridiculousness: rldicl. (It stands for “rotate left doubleword by immediate and clear left”.) I suspect the POWER team has a good sense of humor. There's also the EIEIO instruction https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-in-order-execution-io-instruction https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-...
deleted 5y ago
[deleted]

448 points by mlex 5y ago

I find it mind boggling that something as simple as this can actually be patented. unsigned average(unsigned a, unsigned b) { return (a / 2) + (b / 2) + (a & b & 1); } That makes the patent system seem broken to me.

justin66 5y ago

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-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about... https://news.ycombinator.com/item?id=3530104 https://news.ycombinator.com/item?id=3530104 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=9857392 https://news.ycombinator.com/item?id=9857392 https://news.ycombinator.com/item?id=12147703 https://news.ycombinator.com/item?id=12147703 https://news.ycombinator.com/item?id=621557 https://news.ycombinator.com/item?id=621557 https://news.ycombinator.com/item?id=7594625 https://news.ycombinator.com/item?id=7594625 https://news.ycombinator.com/item?id=9113001 https://news.ycombinator.com/item?id=9113001 https://news.ycombinator.com/item?id=16890739 https://news.ycombinator.com/item?id=16890739 If doomscrolling all that isn't enough to make you fear for mankind's future I'm pretty sure there's an Ulrich Drepper glibc bug report rejection related to this topic (or several) that you can google... On topic: Raymond's post has some other great stuff. SWAR!

dataflow 5y ago
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, or even addable for that matter. The introduction of that requirement is therefore a bug (at least in my eyes). The easiest way to see this is to replace integers with pointers. Then adding two pointers isn't even a well-defined operation in the general case, let alone dividing them by two. Whereas subtracting them and moving half the distance is actually quite well-defined, and we can see it behaves better too. I would probably go so far as to claim that this is not an isolated example of where thinking about problems more abstractly helps us come up with solutions that have non-obvious benefits.
- ghusbands 5y ago
  Subtraction, division and addition is one of the common answers that is still wrong, unless you also want to do a comparison, first, and that is generally high cost. Read https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63303 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63303 to see many problems around pointer differencing.
  - adrian_b 5y ago
    A comparison never costs more than an addition or a subtraction. If you would use a conditional jump, that would have a high cost. However the maximum or minimum should always be computed without conditional jumps and many CPUs have special instructions for max and min, which are not more expensive than additions or subtractions. On CPUs without max & min instructions, computing max or min requires 2 instructions (compare + conditional copy). 2 instructions vs. 1 instruction increases the program size but not necessarily the execution time, if the instructions can be overlapped with others. Due to the complex architecture of modern CPUs, it is impossible to determine the cost of a simple sequence of instructions in the general case. For each particular CPU, a different but equivalent sequence of instructions can be the best and longer sequences of instructions may happen to be executed in less time, if they can be better overlapped on a certain CPU.
    - ghusbands 5y ago
      The obvious form of the code with a comparison still produces a conditional branch on latest gcc [1]. It's extremely doubtful that you'll find a version that uses any comparison that consistently performs as quickly as any version that uses a little bit-twiddling, no matter what modern CPU you're talking about. Many of your statements are misleading in context. Implying that you can't know or deduce things about the cost of a simple sequence of instructions is very odd. All software and people that work on optimization do it all the time. And remember that the context is a suggestion that pointer types and pointer-subtraction is the answer to a question about integers, so getting into detail about instruction sequences isn't really going to help, as the basic idea is flawed. [1] https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:34,endLineNumber:22,positionColumn:34,positionLineNumber:22,selectionStartColumn:34,selectionStartLineNumber:22,startColumn:34,startLineNumber:22),source:'volatile+long+double+x%3B%0Atypedef+unsigned+int+uint%3B%0A%0Auint+badmid(uint+a,+uint+b)+%7B%0A++++return+(a+%2B+b)+/+2%3B%0A%7D%0A%0Auint+cmpmid(uint+a,+uint+b)+%7B%0A++++if+(a+%3E+b)+%7B%0A++++++++return+b+%2B+(a+-+b)+/+2%3B%0A++++%7D%0A++++else+%7B%0A++++++++return+a+%2B+(b+-+a)+/+2%3B%0A++++%7D%0A%7D%0A%0Auint+bitmid(uint+a,+uint+b)+%7B%0A++++return+(a%3E%3E1)+%2B+(b%3E%3E1)+%2B+(1%26a%26b)%3B%0A%7D%0A%0Auint+bit2mid(uint+a,+uint+b)+%7B%0A++++return+(a+%26+b)+%2B+(a+%5E+b)+/+2%3B%0A%7D'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:gsnapshot,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-O3',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1,tree:'1'),l:'5',n:'0',o:'x86-64+gcc+(trunk)+(C%2B%2B,+Editor+%231,+Compiler+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(file...
benmmurphy 5y ago
The Java solution is simpler because they are finding the average of 2 positive signed integers. So if you add 2 31 bit positive signed integers the result will fit in 32 bits and then you can just do an unsigned right shift to get the average.
smaddox 5y ago
> I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. I haven't seen the mentioned proof, but if said proof is not formal and mechanized and/or does not consider all possibilities, including overflow, then should we really consider it to be a proof of correctness? It might prove some desirable properties, but I don't think we should leave it at that. I certainly don't think we should claim that "It is not sufficient merely to prove a program correct; you have to test it too." When it comes to software programs, I believe proofs can and should be exhaustive. That does not necessarily mean you need to exhaustively test every input, but it does mean you need to prove correctness for every input, including inputs that might result in overflow or undefined behavior. Otherwise, we should not consider it a proof of correctness.
- wildmanx 5y ago
  It was a formal proof, but one based on a false assumption, namely that x+y for two ints x and y is an int and a well-defined operation. It's not. The trust in the significance of a proof is limited by the trust in the statement to be proven. The statement to be proven was "If XYZ assumptions about the statements in the underlying language hold, then the result of that function is the result of a binary search". The proof is correct. Just that XYZ contained something incorrect. There is no free lunch. Even if we prove all our software formally correct, we still need to "program" the specifications, with all that comes with it. They can contain bugs, need to be debugged, revisited, etc. The above is an excellent example of this.
LudwigNagasena 5y ago
Quite “amazing” that googleblog layout breaks on iOS. It’s literally impossible to see half of the text without the reader mode.
- xbmcuser 5y ago
  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
  - deckard1 5y ago
    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.

ridiculous_fish 5y ago

The "SWAR" approach `(a & b) + (a ^ b) / 2` looks bizarre but can be understood. Adding two bits produces a sum and a carry: 0 + 0 = 0, carry 0 1 + 0 = 1, carry 0 0 + 1 = 1, carry 0 1 + 1 = 0, carry 1 So the sum is XOR, and the carry is bitwise AND. We can rewrite x + y as (x ^ y) + (x & y)*2 Distribute the divide, and you get (x ^ y)/2 + (x & y) which is the mystery expression. (Note this distribution is safe only because (x & y)*2 is even.)

justinpombrio 5y ago
Alternatively, a direct explanation: a & b is the bits they have in common. If they both have a bit x, you should keep it, because the average of x and x is x. a ^ b is the bits that only one of them have. You should halve these bits, because the average of x and 0 is x/2.
- ziml77 5y ago
  This explanation makes a ton more sense!
  - wildmanx 5y ago
    But it has lots of assumptions/prerequisites about taking the mean baked-in. It happens to work for this particular case, but in general you don't get far with such hand-wavy reasoning since you just get confused with which assumptions hold and which don't. The original explanation was the actual SIMD approach, which is really cool. You can extend it right away to other problems.
    - ggrrhh_ta 5y ago
      The explanation seems to work even in base 10. Let's do the average of 85 and 95. The leftmost digit of both is equal, so we leave it: X5 The "xor"/2 is the sum of the non equal digits divided by 2 (respecting their powers): (8+9)10 = (17)10 = 85 Now, we add them: 5 + 85 = 90 (which is the average of 85 and 95). Let's take now 87 and 89: The rightmost digits are equal: 8X We do the 'xor'/2 for the left most: (7+9)/2 = 8 8X + 8 = 88 Let me know if there are some examples for which it would fail (I only spent a minute to test if the explanation extends to other bases).

kingcharles 5y ago

Some unreal solutions here that show how amazing mathematics can be. Especially that Google patented method that only just recently expired. Props for including the assembler breakdown for every major CPU architecture.

readthenotes1 5y ago
It was a Samsung patent. Only the document was hosted by Google
ijidak 5y ago
I had to lol when I saw there was a patent for that. Divide both operands by 2 was my first idea before loading the page. (I like to try that sometimes before reading the articles.) I didn't think about the carry bit, but it seems like that would be a logical solution after 5 minutes of extra thinking. I'm not sure how that's patentable. That's insane to me. But maybe there is more too it. I didn't read the patent itself.
- staticassertion 5y ago
  https://patents.google.com/patent/US6007232A/en https://patents.google.com/patent/US6007232A/en The patent is for a circuit design to perform that algorithm in a single cycle. The algorithm was never patented, nor could it be.
  - not2b 5y ago
    In practice it makes no difference, because digital logic designers haven't used schematic capture in a very long time. They most commonly write Verilog (or SystemVerilog, which is a superset), and it looks a lot like C: logic [31:0] a, b, average; assign average = (a >> 1) + (b >> 1) + (a & b & 32'd1);
    - staticassertion 5y ago
      Sorry, I don't understand what you mean. It makes no difference to whom? It definitely makes a difference to someone writing that code, since that code is not patented.

nmilo 5y ago

There’s another algorithm that doesn’t depend on knowing which value is larger, the U.S. patent for which expired in 2016: unsigned average(unsigned a, unsigned b) { return (a / 2) + (b / 2) + (a & b & 1); } There's no way that should be patentable.

version_five 5y ago
Yeah, when I read the article title, this is how I thought I would do it. Anything that obvious is not patentable in principle, but in practice, Samsung could still destroy any small business it wanted to by taking them to court over it. The patent system is awful
- deleted 5y ago
  [deleted]
throwaway22032 5y ago
That's utterly hilarious. I've never come across this problem before, I read the headline and that solution came into my head immediately before I'd even clicked. I don't think I'm clever, surely half of HN feels the same way. Software patents are comical.
- staticassertion 5y ago
  The article is in error. It isn't patented.
coutego 5y ago
Exactly. I saw the title, thought "I wonder what other way there is to do this than the obvious one of pre-dividing by 2" and then opened the article and saw that the trivial way to do it was covered by a patent. Wow! Just wow...
- amelius 5y ago
  Well, we're the ones allowing the patent scam to continue ...

AnotherGoodName 5y ago

I noticed the following is in the middle of the article with no context that no one else is mentioning: unsigned average(unsigned a, unsigned b) { return (a & b) + (a ^ b) / 2; } A quick sanity check of this 23 & 21 = 21 23 ^ 21 = 2 21 + 2 / 2 = 22 (order of operations) I wonder why this is there. It seems the best solution but no one else is mentioning it. It also has no context near it. Nor is it stated correctly. It's just there on it's own.

829588225 5y ago
23 ^ 21 = 2
- AnotherGoodName 5y ago
  Sorry, edited the above. This is straight up right then which is weird. It's just there in the middle of the article with no context. In the middle of the SWAR method.
  - shannongreen 5y ago
    It is the SWAR method. Another comment explains it well, it basically treats each bit position as a 2-bit adder.
jlynn 5y ago
The average of 23 and 21 is indeed 22.
- AnotherGoodName 5y ago
  Oh right, sorry i'll edit this. It works straight up then. Weird it's there with no context.
deleted 5y ago
[deleted]

classichasclass 5y ago

He hinted at this obliquely, but the PowerPC family of bit rotate instructions (ridicl, rlwinm, rlwimi, etc.), although intimidating in the general case, allows shifting, rotation, insertion, masking and more. There are many alternative mnemonics to try to reduce the cognitive complexity but all of these just assemble to them with particular parameters.

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 ago
Agreed. 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 ago
  Isn'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 ago
    I 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

leptoniscool 5y ago

This seems fundamental, surprised elementary operations hasn't been made a part of every major language/framework.

mzs 5y ago
>Bonus chatter: C++20 adds a std::midpoint function that calculates the average of two values (rounding toward a).

avmich 5y ago

Does this all work with BCD encoding?

worewood 5y ago

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.

jws 5y ago
Absolutely the same thing I did. I even had the low bit logic worked out by the time I scrolled the article down and saw the patented line. Clearly we have both had miraculous enlightenment because legally this is “not obvious”.
- hackthefender 5y ago
  > 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 always people advocating for more or less).
  - doctor_eval 5y ago
    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.
    - unnah 5y ago
      And back in 1996, programmers were much more familiar with bit-twiddling than today.
  - ______-_-______ 5y ago
    It's not even computer science, it's literally just math. (a+b)/2 = a/2 + b/2. They were teaching that in pre-algebra in middle schools well before 1996.

bufferoverflow 5y ago

Isn't it better to do (a>>1) + (b>>1) + (a&b&1) No division needed.

jws 5y ago
Your compiler will take care of that. Leave the division for the humans to read.
- xaduha 5y ago
  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.
  - Dylan16807 5y ago
    What should happen if you store "a+b" in an intermediate value?
    - xaduha 5y ago
      If it is used and there's no way around it, then show a compilation warning that there might be overflow. If it can be resolved without being directly used, then it should be optimized away.
  - jws 5y ago
    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.
8jy89hui 5y ago
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.

favorited 5y ago

Marshall Clow gave a pretty excellent CppCon talk covering these exact problems, called "std::midpoint? How Hard Could it Be?" https://www.youtube.com/watch?v=sBtAGxBh-XI https://www.youtube.com/watch?v=sBtAGxBh-XI

rrss 5y ago
yes, this is linked from the article

blobbers 5y ago

This guy hacks.

Subsentient 5y ago

Eh. I just cast both to a bigger integer type where possible, which in practice, is almost always. So if I'm averaging two uint32_ts, I just cast them to uint64_t beforehand. Or in Rust, with its lovely native support for 128-bit integers, I cast a 64-bit integer to 128-bit.

benlivengood 5y ago

Before reading the article: In x86 assembly, add ax, bx ; rcr ax, 1 works. I guess technically that is with overflow, but using overflow bits as intended. EDIT: it's included in the collection of methods in the article as expected.

jart 5y ago
That's lovely. I missed it when reading the article. It's also the winner on AMD Zen architecture based on MCA analysis. unsigned midpoint(unsigned a, unsigned b) { asm("add\t%1,%0\n\t" "rcr\t%0" : "+r"(a) : "r"(b)); return a; } Although `(a & b) + (a ^ b) / 2` is probably the more conservative choice.

yalogin 5y ago

I cannot believe that solution was allowed to be patented. How crappy is our patent process? Most engineers writing code would come up with that solution first.

stathibus 5y ago
Every patent attorney I've ever worked with has emphasized that engineers are not equipped to determine if an idea is obvious and should let the PTO decide. They say this because they know the USPTO strategy is to just hand out patents after putting in some bare minimum effort to review, and postpone the real review process to the unlikely day that someone chooses to challenge it in court and can pay private firms to do their job for them. The winners in this arrangement are the government, the big law firms, and the large corporations that can afford them.

johnhenry 5y ago

I saw the title and thought to just do "(a / 2) + (b / 2)" and a do a little bit of fudging if a or b is odd. After reading the article, learning that unsigned average(unsigned a, unsigned b) { return (a / 2) + (b / 2) + (a & b & 1); } was once patented actually made me a bit sad for our entire system of patents.

cphoover 5y ago
Why is math patentable? seems crazy to me
- bonzini 5y ago
  What is patentable is "this circuit to compute the average" where the circuit is an adder that drops the bottom bit from the addends, instead ANDing the two bottom bits and using the result as a carry-in. Though actually it shouldn't be patented because it's an obvious implementation of a math formula (and math is not patentable).

mark-r 5y ago

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.

nickm12 5y ago
Raymond Chen is a treasure.
erwincoumans 5y ago
Rounding in Python is interesting though: https://www.askpython.com/python/built-in-methods/python-round 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."
- scatters 5y ago
  Round half to even is well known outside Python. It's sometimes called bankers' rounding.
- mark-r 5y ago
  Yes it is. But nobody said anything about rounding!
  - deleted 5y ago
    [deleted]

rustybolt 5y ago

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

kuboble 5y ago
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.
- ghusbands 5y ago
  It was obvious in 1996, too. It is and was the most obvious solution for a programmer fully aware of the problem and wanting to avoid comparisons.
- SkeuomorphicBee 5y ago
  If a phone is the first solution that comes to mind for a person that never saw or heard of a phone in their life, then that indicates phone was a bad patent.
- wongarsu 5y ago
  If the average expert in the field immediately comes up with the same or a very similar solution then it obviously isn't non-obvious, which is one of the tests for patentability. In the case of the phone you already know the patented solution, which obviously makes it impossible for you to judge its obviousness. That presumable wasn't the case with GP and the presented problem.
d_tr 5y ago
The fact that patents require time and money makes this even more pathetic and appalling.

unwind 5y ago

Very cool. I was surprised that the article didn't mention the need for this in binary search, and the famous problems [1] that occured due to naive attempts. [1]: https://en.m.wikipedia.org/wiki/Binary_search_algorithm https://en.m.wikipedia.org/wiki/Binary_search_algorithm

phs318u 5y ago

I got a pang of nostalgia seeing the Alpha AXP instructions.

Beldin 5y ago

Since this discussion is all about patents: my 2 cents on improving the patent system. Consider a term project of an undergraduate CS course, where the goal is spelled out, but the method is left for discovery. Methods developed within any such project immediately invalidate patents. They're apparently obvious to folks learning to become "skilled in the art". Yes, in practice, reaching a legal threshold would be hard (are you sure the students didn't read the patent or any description directly resulting from it?). But I'd definitely run a "patent invalidation course" - if I had confidence that the results would actually affect patents.

dathinab 5y ago

how is turning (a+b)/2 into a/2 + b/2 + a&b&1 even patentable? Turning (a+b)/2 into a/2 + b/2 is basic obvious math. If you do it and to any basic testing you will realize you are getting of by one errors, locking at them can then make it obvious that when they appear and hence how to fix them. Sure a proof is more complex, but then you can just trivially test it for all smaller-bit numbers over all possible inputs, hence making proofs unnecessary (for that numbers). This is a solution a not yet graduated bachelor student can find in less then a day. Having granted a patent for this should lead to disciplinary measurements against the person granting the patent tbh.

hollowturtle 5y ago

Wait, what? How can a patent right be applied on a one line of code that eventually is compiled down to machine code? Sounds ridicolous to me

Findecanor 5y ago

As an asm geek, I wasn't surprised to read that taking advantage of the carry flag yielded the most efficient code for some processors. I recalled that some ISAs also have special SIMD instructions specifically for unsigned average, so I looked them up: * x86 SSE/AVX/AVX2 have (V)PAVGB and (V)PAVGW, for 8-bit and 16-bit unsigned integers. These are "rounding" instruction though: adding 1 to the sum before the shift. * ARM "Neon" has signed and unsigned "Halving Addition". 8,16 or 32 bit integers. Rounding or truncating. * RISC-V's new Vector Extension has instructions for both signed and unsigned "Averaging Addition". Rounding mode and integer size are modal. * The on-the-way-out MIPS MSA set has instruction for signed, unsigned, rounded and truncated average, all integer widths. Some ISAs also have "halving subtraction", but the purpose is not as obvious.

ncmncm 5y ago

> gcc doesn’t have a rotation intrinsic, so I couldn’t try it there 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.

adrian_b 5y ago
They recognize how to do a rotation of an unsigned integer value, but they do not recognize how to do the rotation of that value concatenated with the carry bit, which is needed here.

user-the-name 5y ago

"unsigned long long"? It's 2022. stdint.h is old enough to drink, and is probably married with a kid on the way. Just include it already?

MaxBarraclough 5y ago

Reminds me of a Stack Overflow thread, Shortest way to calculate difference between two numbers? [0] Multiple answers ignored the possibility of overflow. [0] https://stackoverflow.com/q/10589559/ https://stackoverflow.com/q/10589559/

dpacmittal 5y ago

You could also do (a + (b-a)/2) where a is the smaller number.

dralley 5y ago

> I find it amusing that the PowerPC, patron saint of ridiculous instructions, has an instruction whose name almost literally proclaims its ridiculousness: rldicl. (It stands for “rotate left doubleword by immediate and clear left”.) I suspect the POWER team has a good sense of humor. There's also the EIEIO instruction https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-in-order-execution-io-instruction https://www.ibm.com/docs/en/aix/7.2?topic=set-eieio-enforce-...

deleted 5y ago

[deleted]