C++ Reference ยท Algorithms
C++ <numeric> header: gcd, lcm, midpoint and more
Tour of the C++ <numeric> header and friends: std::gcd, lcm, midpoint, lerp, iota, accumulate, reduce, inner_product, adjacent_difference.
The <numeric> header collects small numeric building blocks: folding a sequence into one value (accumulate, reduce, transform_reduce), running totals (partial_sum, inclusive_scan), filling with counting values (iota), differences between neighbors (adjacent_difference), and a few pure number functions: std::gcd and std::lcm (C++17), std::midpoint (C++20) and std::lerp (C++20, declared in <cmath>). C++26 adds saturating arithmetic (add_sat, sub_sat, mul_sat, div_sat, saturate_cast), which GCC 15.2 does not offer in C++23 mode, so it is not demonstrated here.
Most of the sequence algorithms have their own pages (see Related). This page focuses on the number functions and shows how the family fits together.
std::gcd(12, 18); // 6 std::lcm(4, 6); // 12 std::midpoint(1, 4); // 2 (rounds toward the first argument)
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
#include <numeric> template<class M, class N> constexpr std::common_type_t<M, N> std::gcd(M m, N n); template<class M, class N> constexpr std::common_type_t<M, N> std::lcm(M m, N n); template<class T> constexpr T std::midpoint(T a, T b) noexcept; // arithmetic types template<class T> constexpr T* std::midpoint(T* a, T* b); // pointers constexpr float std::lerp(float a, float b, float t) noexcept; // <cmath>, C++20
| Name | Description |
|---|---|
m, n |
Integer arguments for gcd and lcm. Must be integer types other than bool. |
a, b |
Values (or pointers into the same array) for midpoint and lerp. |
t |
Interpolation factor for lerp; 0 gives a, 1 gives b; values outside 0..1 extrapolate. |
Returns: gcd the greatest common divisor (gcd(0, 0) is 0); lcm the least common multiple (0 if either argument is 0); midpoint the halfway value; lerp the interpolated number.
Errors / undefined behavior: gcd and lcm have undefined behavior if |m|, |n|, or the lcm result is not representable in the result type (lcm(1'000'000, 1'000'001) overflows int). midpoint on pointers needs both in the same array.
Usage notes
- Never write the midpoint as
(a + b) / 2for integers: it can overflow.std::midpoint(a, b)cannot (C++20). Binary search code often useslo + (hi - lo) / 2for the same reason. - Rounding of
midpoint. For integers it rounds towarda, the first argument, somidpoint(1, 4)is 2 andmidpoint(4, 1)is 3. - Mixed types.
gcdandlcmconvert both arguments to their common type, so mixingintandlongis fine. Mixing signed and unsigned values is risky. - Cheaper
lcm.lcm(a, b)is computed as|a| / gcd(a, b) * |b|, which avoids an early overflow. Do the same when you write it by hand. std::lerpis exact at the endpoints (lerp(a, b, 1)is exactlyb) and monotonic, unlikea + t * (b - a)in floating point.- Saturating functions (
add_sat,sub_sat,mul_sat,div_sat,saturate_cast) clamp to the type's range instead of overflowing. They are C++26 and missing from GCC 15.2 in C++23 mode (verified on our runner); write a manual check withstd::numeric_limitsuntil your compiler has them. - Accumulator type.
std::accumulate(v.begin(), v.end(), 0)sums into aninteven for avector<double>; write0.0. Seestd::accumulate. - Prefer
reducefor speed. It may reorder operations (the operation must be associative and commutative), and takes an execution policy. - Related headers. Mathematical functions (
sqrt,pow,abs) are in<cmath>and<cstdlib>; bit tricks are in<bit>.
Related
std::accumulate,std::reduce,std::partial_sum,std::iota,<cmath>- Lessons: Numeric algorithms, Math