Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding the average of two unsigned integers without overflow

devblogs.microsoft.com

Post reply on HN
Print view View original

171–180 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#171

Post by pclmulqdq »

upofadown wrote: post #168
jagger27 wrote: post #85

Earlier quoted context omitted.

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

But 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…

We have eliminated most software patents: see Alice Corp vs CLS bank.

The only thing this patent covers is the physical circuit implementation, not the math.

Re: Finding the average of two unsigned integers without overflow

#172

Post by adrian_b »

danbruc wrote: post #139
vbezhenar wrote: post #116

Earlier quoted context omitted.

x / 2 === x >> 1, it's fast.

For unsigned or positive x. Yes, the article is about unsigned integers, but some might see this for the first time and not be aware of this restriction. -3 / 2 == -1 but -3 >> 1 == -2.

You can use the appropriate right shift with signed integers as easy as with unsigned integers, you just have to handle in the right way the correction due to the bit shifted out.

The fact that the right shift for a negative integer gives the floor function of the result just makes the correction easier than if you had used division with truncation towards zero.

The shifted out bit is always positive, regardless whether the shift had been applied to negative or positive numbers.

Except for following a tradition generated by a random initial choice, programming would have been in many cases easier if the convention for the division of signed numbers would have been to always generate positive remainders, instead of generating remainders with the same sign as the quotient.

Re: Finding the average of two unsigned integers without overflow

#173

Post by adrian_b »

ghusbands wrote: post #157
dataflow wrote: post #5

Earlier quoted context omitted.

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,…

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 to see many problems around pointer differencing.

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.

Re: Finding the average of two unsigned integers without overflow

#174

Post by ggrrhh_ta »

wildmanx wrote: post #141
ziml77 wrote: post #69

Earlier quoted context omitted.

This explanation makes a ton more sense!

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.

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

Re: Finding the average of two unsigned integers without overflow

#175

Post by nikanj »

Ygg2 wrote: post #155
errcorrectcode wrote: post #39

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/

> 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-pate... https://patents.google.com/patent/US5443036A/en https://patents.google.com/patent/US6360693 Apple steals the cake though. By patenting a geometric shape.

I bet you broke this patent as a kid https://patents.google.com/patent/US6368227B1/en

Re: Finding the average of two unsigned integers without overflow

#176

Post by simias »

Agentlien wrote: post #120
vbezhenar wrote: post #116

Earlier quoted context omitted.

x / 2 === x >> 1, it's fast.

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

On 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);
    }

Re: Finding the average of two unsigned integers without overflow

#177

Post by mark-r »

erwincoumans wrote: post #114
mark-r wrote: post #110

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.

Rounding in Python is interesting though: 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."

Yes it is. But nobody said anything about rounding!

Re: Finding the average of two unsigned integers without overflow

#178

Post by danbruc »

adrian_b wrote: post #172
danbruc wrote: post #139

Earlier quoted context omitted.

For unsigned or positive x. Yes, the article is about unsigned integers, but some might see this for the first time and not be aware of this restriction. -3 / 2 == -1 but -3 >> 1 == -2.

You can use the appropriate right shift with signed integers as easy as with unsigned integers, you just have to handle in the right way the correction due to the bit shifted out. The fact that the right shift for a negative integer gives the floor function of the result just makes the correction easier than if you had used division with truncation towards zero. The shifted out bit is always positive, regardless whet…

With positive remainders you get wired quotient behavior. Why should 10/3 and -10/-3 yield different results? Besides that, the choice is not universal, different languages use different conventions.

Re: Finding the average of two unsigned integers without overflow

#180

Post by vbezhenar »

danbruc wrote: post #139
vbezhenar wrote: post #116

Earlier quoted context omitted.

x / 2 === x >> 1, it's fast.

For unsigned or positive x. Yes, the article is about unsigned integers, but some might see this for the first time and not be aware of this restriction. -3 / 2 == -1 but -3 >> 1 == -2.

Interesting thing is that `(a >> 1) + (b >> 1) + (a & b & 1)` works correctly for signed integers (if `>>` works like in Java, filling most significant bit with ones for negative numbers). With division you'll need to write different expressions depending on operand signs. E.g. (-3) / 2 + (-5) / 2 + ((-3) & (-5) & 1) = (-1) + (-2) + 1 = -2. But ((-3) >> 1) + ((-5) >> 1) + ((-3) & (-5) & 1) = (-2) + (-3) + 1 = -4.
Post reply on HN