CppCon 2019: Marshall Clow “std::midpoint? How Hard Could it Be?”
Why Stack Overflow recommends it
Stack Overflow users link it when answering questions about computing the average or midpoint of two numbers without overflow, as the definitive account of why (a+b)/2 goes wrong.
Recommended by 3 people across 4 different months, 2019 to 2023.
What it is
A CppCon 2019 talk by Marshall Clow, libc++ lead developer and chair of the C++ library working group, on the C++20 function std::midpoint. He walks through the history of its implementation in libc++ and the pitfalls involved, including undefined behavior, numeric representations, integer promotion rules and floating point.
What people said
Recommends Bob__ · 2019-10 · Stack Overflow · on “How to add two large double precision numbers in c++”
It's OT, but here: CppCon 2019: Marshall Clow “std::midpoint? How Hard Could it Be?” [this video] you can find all the excruciating details on how `(x + y)/2` could go wrong.
Recommends cigien · 2020-09 · Stack Overflow · on “Binary Search: how to determine half of the array”
In the 2nd version, if high + low is greater than the maximum value of an int (assuming high is an int ) then it can overflow, invoking undefined behavior. This particular bug is solved with the 1st version. There are still issues with the 1st version, e.g. if low is a very large negative number, the difference can still overflow. From c++20, you should use std::midpoint [LINK] for this, which handles a whole bunch of corner cases, and does the right thing for all of them. This seemingly simple function is actually surprisingly difficult to implement, and in fact, there's an hour long talk [this video] given by Marshall Clow at cppcon 2019, that covers the implementation of just this function.
Recommends Bob__ · 2021-09 · Stack Overflow · on “Why segmentation fault in recursion to find roots of a function?”
@user305883 If I may, that's the Horner's method [LINK] for evaluating polynomials. About the evaluation of `mean`, you may find this talk (even if it's about a C++ feature) "std::midpoint? How Hard Could it Be?" [this video] enlighting.
Recommends chtz · 2023-09 · Stack Overflow · on “How to compute mean of two floating-point numbers?”
Related CppCon talk: std::midpoint? How Hard Could it Be? [this video] -- floating point is handled starting around 48:40
Cites sh- · 2022-02 · Stack Overflow · on “Efficient overflow-immune arithmetic mean in C/C++”
The arithmetic mean of two unsigned integers is defined as: mean = (a+b)/2 Directly implementing this in C/C++ may overflow and produce a wrong result. A correct implementation would avoid this. One way of coding it could be: mean = a/2 + b/2 + (a%2 + b%2)/2 But this produces rather a lot of code with typical compilers. In assembler, this usually can be done much more efficiently. For example, the x86 can do this in the following way (assembler pseudo code, I hope you get the point): ADD a,b ; addition, leaving the overflow condition in the carry bit RCR a,1 ; rotate right through carry, effectively a division by 2 After those two instructions, the result is in a , and the remainder of the d
Cites geometrian · 2022-07 · Stack Overflow · on “Fastest way to take the average of two signed integers in x86 assembly?”
As an outside answer, consider the pavg family of instructions [LINK] . I say "outside", since this is likely not acceptable to you. It assumes the value is unsigned 8-bit or 16-bit and in an SSE register, which of course also requires SSE. I mention it mainly since it is x86's anointed equivalent to averaging instructions in other ISAs. In its defense, SSE is ubiquitous by now, even guaranteed on x86-64. Also, this instruction is 1 cycle, and actually can do 4 at once if you like. Best of all, unlike your original solutions, it also correctly handles overflow issues. Note that it's possible to use an unsigned routine to implement a signed routine, though in general correctly accounting for