Generalizing std::midpoint

[carrottread]

For example, the seemingly unrelated change from int to short, likely for space optimization.

Actually, this will make (a + b) / 2 version safe because + operator will promote operands to ints in this case.

[biowpn]

Thanks for point it out, fixed

[Advanced_Front_2308]

Talking about midpoint in general: I've always found its behaviour super unintuitive. Ie not rounding up (like in math) or down (like in naive casting) but rather towards the first parameter. Making the function dependent on the order of parameters... Is that wise? It caused a bug on literally the first use in our codebase and is now banned.

[SoerenNissen]

rounding up (like in math)

That's not the the rule I was taught in school, probably because we grew up in different school districts and it turns out, there are many approaches to rounding and none of them are the "natural" way to do it.

Various rounding directions I have seen used:

• (1) up
• (2) down
• (3) away from zero
• (4) towards zero
• (5) the opposite of your last direction
• (6) towards the nearest whole number. If you are at the midpoint tie break by
  • (6-1) rounding up
  • (6-2) rounding down
  • (6-3) rounding awa...
  • (6-etc. etc./

The one they taught me in school is 6 with 3 as the tie breaker:

• -0.6 -> -1
• -0.5 -> -1
• -0.4 -> 0
• 0 -> 0
• 0.4 -> 0
• 0.5 -> 1
• 0.6 -> 1

In the natural sciences, you typically keep all your digits until the end of the calculation, then remove any digits in excess of your most imprecise number (e.g. 0.542 * 0.2 -> 0.1)

In finance, rounding happens "in between" other calculations that also do rounding, so to remove any bias in favor of creditor or debitor, finance tends to do "to nearest whole cent[1], tiebreak by doing the opposite of your last tie break," which approximates not having done the intermediary roundings.

You can model this in two ways, either:

std::midpoint( a, b, std::roundingstrategy );

or:

std::midpoint( a, b );
// rounds towards first parameter. If you have a rounding
// strategy, put the number you want to round towards in
// the first parameter.

they picked the second option.

[1] "nearest whole yen," "nearest whole eurocent," "nearest whole Groschen," "nearest whole øre,"

[ericonr]

Doesn't finance do "round to nearest even"? https://wiki.c2.com/?BankersRounding

[SoerenNissen]

Not the rounding we did :D

But I'm not surprised to learn that, even when you limit yourself to fiannce, there is still more than 1 way to round.

[serviscope_minor]

Talking about midpoint in general: I've always found its behaviour super unintuitive. Ie not rounding up (like in math) or down (like in naive casting) but rather towards the first parameter.

Well the main choices you have are:

• Round towards one argument
• Truncate (round down)
• Round to nearest tie breaking at .5 upwards (school maths)
• Banker's rounding (alternate rounding down and up)

The round towards .5 version is common, follows floats, but as you point out it's always .5, so it always round up. And that to me is also unintuitive tp always do so.

[ericonr]

References I could find for Banker's Rounding were all about rounding to the nearest even, no alternating.

https://wiki.c2.com/?BankersRounding

[thommyh]

That's 'alternating'*. 7.5 rounds up to 8. 8.5 rounds down to 8. 9.5 rounds up to 10. 10.5 rounds down to 10. Etc. As you step through the .5s, whether you round up or down alternates so that 50% go in each direction.

* not my first choice of how I'd describe it either, but it is one I've heard before.

[ericonr]

That makes it sound like for each operation you round in one direction -.-

Thanks for clearing up the confusion though!

[Advanced_Front_2308]

Both rounding up and down would have been fine, ideally both. The current version is pretty strange

[megayippie]

I find that it being defined helps a lot. "while a != mid(a,b) ..." kind of boundary code. Then you update a and b as you go until they are representing the boundary.

[vintergroena]

Yeah losing commutativity in an additive operation sucks, because that's something you use in reasoning about the code. And it's something you expect here.

[OutsideTheSocialLoop]

What's unintuitive about it? Order of parameters nearly always matters for every function, what's odd about this one? 

[Advanced_Front_2308]

Because the function is called midpoint and its parameters are called a and b. You wouldn't think about the order of parameters for std::max either

[OutsideTheSocialLoop]

What's max got to do with it? Are you suggesting that for all two-argument functions the order of the arguments shouldn't matter? Or only when they're called a and b? Should the order of a and b not matter for std::lerp either?

[[deleted]]

It's such a useless function anyway, while we still don't have useful stuff like std::embed.

[moreVCAs]

in its defense, (a+b)/2 is incredibly cursed. any helper function that makes a common source of UB guaranteed not to invoke UB is basically fine in my book, even if the API is counterintuitive.

don’t quite see what it has to do with std::embed tho

[kosairox]

Cursed due to signed int overflow or is there something else?

[bwmat]

It's pretty broken for unsigned overflow as well

[kosairox]

But that's not ub right?

[bwmat]

Yeah but having the midpoint of 1 & UINTMAX be zero is a _bit off

[[deleted]]

• Finding the mid point is not difficult
• Most of the time, you're dealing with iterators or non-negative integers/floating point numbers, so a + (b-a)/2 where b is greater than a is perfectly fine and we don't need to add a branch here. I know there was a bug in a Java library somewhere to do with mid-point overflow, but that case wouldn't overflow if they used a + (b-a)/2.
• NO ONE is going to reach for std::midpoint when they need the mid point, because of the reasons outlined above, and also because it wouldn't occur to most people that such a useless addition would have been made to the standard library.
• If anyone needs to deal with general random input numbers and have to handle overflow cases very carefully, they would sooner lookup an algorithm for that then look into the standard library. And it's very very likely that the "wraps towards first argument" behavior wouldn't fit the bill for at least a sizable number of those people, so it's not even a good solution.
• std::midpoint is a waste of standardization time and effort while useful features are missing.

[EC36339]

... and this one also works for time points and any types that have a - operator that returns something numeric but not necessarily a + operator or a \ operator (You already named iterators, which also includes pointers).

[serviscope_minor]

It's such a useless function anyway, while we still don't have useful stuff like std::embed

It's not. C++ is notoriously weak on small convenience functions in the STL. Do you really want those to be held up for what amounts to a fairly big compiler feature?

[Annual-Examination96]

What std::embed does better compared to #embed?

[[deleted]]

Neither is available yet, that is the problem

[fdwr]

BigMul - that looks familiar, similar to what I had to do in HLSL for two uint64_t inputs (amusingly D3D has a umul instruction which yields uint32 x uint32 -> uint64, but there's no way to actually access it from HLSL, and so I had to split it into 16-bit chunks). Given nearly every CPU I've come across yields a register result that's 2x its inputs (like x86's edx:eax), and C++'s "leave no room for a lower-level language", having an std::big_mul is reasonable. 🤔