7 ms·
Finding the average of two unsigned integers without overflow
- blobbers 5y agoThis guy hacks.
- yalogin 5y agoI 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 agoEvery 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.
- everyone 5y agoI 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.
- 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?
- justin66 5y agoSee 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 agoI 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 agoSubtraction, 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 agoA 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.
- ridiculous_fish 5y agoThe "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.)
- AnotherGoodName 5y agoSorry i'm confused and i asked elsewhere. How is the above SWAR? It looks like a regular set of instructions.
- deleted 5y ago[deleted]
- eru 5y agoWikipedia says: "It also refers to the use of SIMD with general-purpose registers and instructions that were not meant to do it at the time, by way of various novel software tricks." https://en.wikipedia.org/wiki/SWAR https://en.wikipedia.org/wiki/SWAR Maybe that's the way it's meant? Compilers might be smart enough to pick up the idiom used in the example and compile them to something done in parallel?
- rustybolt 5y agoIf 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 propagating.
- sgtnoodle 5y agoThat'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, 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.
- kingcharles 5y agoSome 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 agoIt was a Samsung patent. Only the document was hosted by Google
- ijidak 5y agoI 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 agohttps://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.
- tialaramex 5y agoSeveral of these patent claims are for "an apparatus" because you're not allowed to patent ideas - but any realisation of the algorithm will necessarily be "an apparatus" so the effect is that in fact you can claim algorithms and that's exactly what this is doing.
- staticassertion 5y agoI'm not a lawyer, so I'm confused. If you patent a hardware implementation of a software algorithm, on the basis that the implementation is novel, how would you stop me from writing that algorithm irrespective of how it executes?
- nmilo 5y agoThere’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.
- coutego 5y agoExactly. 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 agoWell, we're the ones allowing the patent scam to continue ...
- version_five 5y agoYeah, 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 agoThat'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 agoThe article is in error. It isn't patented.
- AnotherGoodName 5y agoI 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.
- jlynn 5y agoThe average of 23 and 21 is indeed 22.
- AnotherGoodName 5y agoOh right, sorry i'll edit this. It works straight up then. Weird it's there with no context.
- deleted 5y ago[deleted]
- 829588225 5y ago23 ^ 21 = 2
- AnotherGoodName 5y agoSorry, 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 agoIt is the SWAR method. Another comment explains it well, it basically treats each bit position as a 2-bit adder.
- classichasclass 5y agoHe 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 agoHaving 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.
- leptoniscool 5y agoThis 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 agoDoes this all work with BCD encoding?
- worewood 5y agoJust 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.
- teaearlgraycold 5y agoAs if anyone would ever get prosecuted for that, though. Given its simplicity this makes me wonder if a compiler has ever transformed legal original IP code into patented code.
- enneff 5y agoThat’s not really how software patents are (ab)used. Just having the patent and a vaguely credible claim that someone is using the patented technology is enough to encumber them with enough legal issues that many people will settle instead of fight it.
- umeshunni 5y agoIt's not the solution that's patented, but it's the implementation in a single CPU cycle in hardware.
- jagger27 5y agoThat’s a pretty important distinction. If someone in the 1800s invented a mechanical calculator that could do this operation in a single crank, I don’t think anyone would upset about that patent.
- upofadown 5y agoBut then the patent would not be on the logic but the mechanical implementation. The obviousness would need to be judged on that basis. The method can be implemented using straightforward combinational logic so the single crank/cycle is a given after you have come up with the obvious method. Back before software patents were a thing, the "math" was not patentable. Eliminating software patents will be a return to the previous status quo.
- bufferoverflow 5y agoIsn't it better to do (a>>1) + (b>>1) + (a&b&1) No division needed.
- jws 5y agoYour compiler will take care of that. Leave the division for the humans to read.
- xaduha 5y agoI'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.
- jws 5y agoFor 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.
- Dylan16807 5y agoWhat should happen if you store "a+b" in an intermediate value?
- xaduha 5y agoIf 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.
- 8jy89hui 5y agoNot 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 agoMarshall 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 agoyes, this is linked from the article
- Subsentient 5y agoEh. 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 agoBefore 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 agoThat'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.
- johnhenry 5y agoI 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 agoWhy is math patentable? seems crazy to me
- bonzini 5y agoWhat 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 agoThis 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.
- erwincoumans 5y agoRounding 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."
- nickm12 5y agoRaymond Chen is a treasure.
- 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 agoThat'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 agoIt 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 agoIf 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 agoIf 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 agoThe fact that patents require time and money makes this even more pathetic and appalling.
- unwind 5y agoVery 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 agoI got a pang of nostalgia seeing the Alpha AXP instructions.
- Beldin 5y agoSince 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 agohow 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 agoWait, 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 agoAs 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 agoThey 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.
- MaxBarraclough 5y agoReminds 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 agoYou 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]