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

191–200 of 220 posts

Re: Finding the average of two unsigned integers without overflow

#191

Post by lukifer »

Retric wrote: post #181
mschuster91 wrote: post #169

Earlier quoted context omitted.

> Which makes me curious: what other patents have we violated in our day-to-day without even knowing it? Patents are like the criminal code - always remember "Three Felonies a Day" [1]. The system is set up so that if you are one of the 99%, the 1% can come in and bust you at will if you become too much of an annoyance/threat. They will find something if they just keep digging deep enough (not to mention that they ca…

Freedom means some people will do stuff you don’t like.

It also means you are not necessarily entitled to rents for your “discoveries”.

Re: Finding the average of two unsigned integers without overflow

#192

Post by djmips »

djmips wrote: post #160
sgtnoodle wrote: post #129

Earlier quoted context omitted.

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

This technique was useful on a 68000 in a 4 voice software PCM sampled instrument music player running on interrupts on the Atari ST back in the day.

Found the game where I worked. Default hardware bleeps and bloops in first version https://www.youtube.com/watch?v=RGOdHT29Jpc

Four voice digi player using SWAR in second version https://www.youtube.com/watch?v=1GrdvcghDXE

Re: Finding the average of two unsigned integers without overflow

#193

Post by jart »

benlivengood wrote: post #88

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.

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.

Re: Finding the average of two unsigned integers without overflow

#194

Post by Retric »

mschuster91 wrote: post #189
Retric wrote: post #181

Earlier quoted context omitted.

Freedom means some people will do stuff you don’t like.

And democracy means, at its core, to restrict the freedom of people committing actions that society has decided to be unlawful.

Except society hasn’t decided that such action is unlawful even if some people, such as yourself, wish it was. I am sure at least a few vegans would like to outlaw eating meat, but democracy also works the other way ensuring such extremely unpopular laws never get passed.

Re: Finding the average of two unsigned integers without overflow

#195

Post by [deleted] »

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

Earlier quoted context omitted.

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!

[deleted]

Re: Finding the average of two unsigned integers without overflow

#196

Post by mschuster91 »

Retric wrote: post #194
mschuster91 wrote: post #189

Earlier quoted context omitted.

And democracy means, at its core, to restrict the freedom of people committing actions that society has decided to be unlawful.

Except society hasn’t decided that such action is unlawful even if some people, such as yourself, wish it was. I am sure at least a few vegans would like to outlaw eating meat, but democracy also works the other way ensuring such extremely unpopular laws never get passed.

> I am sure at least a few vegans would like to outlaw eating meat, but democracy also works the other way ensuring such extremely unpopular laws never get passed.

I would not be so certain about that one.

Many countries are thinking of outright "meat taxes", health scores (similar to smoking warnings in the desired nudging effect) or extending CO² taxes onto agriculture: meat production causes about 14% of global CO² emissions [1], and outlawing/disincentivizing meat consumption is a very easy, very fast and incredibly effective way of cutting down on CO², methane and dung emissions. Not to mention the indirect emissions from land burning (especially in Brazil) or the societal cost of overconsumption of meat (e.g. obesity and heart issues).

Personally, I'm in the "omnivore" camp but recognize that the way how we deal with meat products has to be massively reformed. We need to cut waste and curb consumption, the sooner the better.

[1]: https://www.theguardian.com/environment/2021/sep/13/meat-gre...

Re: Finding the average of two unsigned integers without overflow

#197

Post by Retric »

mschuster91 wrote: post #196
Retric wrote: post #194

Earlier quoted context omitted.

Except society hasn’t decided that such action is unlawful even if some people, such as yourself, wish it was. I am sure at least a few vegans would like to outlaw eating meat, but democracy also works the other way ensuring such extremely unpopular laws never get passed.

> I am sure at least a few vegans would like to outlaw eating meat, but democracy also works the other way ensuring such extremely unpopular laws never get passed. I would not be so certain about that one. Many countries are thinking of outright "meat taxes", health scores (similar to smoking warnings in the desired nudging effect) or extending CO² taxes onto agriculture: meat production causes about 14% of global CO…

That’s the more popular view, but there is still a group of hard core “meat is murder” vegans. Personally I would say get rid of all farm subsidies, but politics makes strange bedfellows and democracy means accepting compromises up to a point.

Re: Finding the average of two unsigned integers without overflow

#198

Post by remram »

ggrrhh_ta wrote: post #174
wildmanx wrote: post #141

Earlier quoted context omitted.

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)/…

The average of 15 and 30 is not 22. The average of 51 and 03 is not 22.

Re: Finding the average of two unsigned integers without overflow

#199

Post by dralley »

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

Re: Finding the average of two unsigned integers without overflow

#200

Post by c-linkage »

nmilo wrote: post #7

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.

Just use the following code and you should be good!

  unsigned average(unsigned a, unsigned b)
  {
      return (a >> 1) + (b >> 1) + (a & b & 1);
  }
Post reply on HN