55#ifndef _GLIBCXX_NUMERIC
56#define _GLIBCXX_NUMERIC 1
59#pragma GCC system_header
66#ifdef _GLIBCXX_PARALLEL
70#if __cplusplus >= 201402L
76#if __cplusplus >= 201703L
80#if __cplusplus > 201703L
84#define __glibcxx_want_constexpr_numeric
85#define __glibcxx_want_gcd
86#define __glibcxx_want_gcd_lcm
87#define __glibcxx_want_interpolate
88#define __glibcxx_want_lcm
89#define __glibcxx_want_parallel_algorithm
90#define __glibcxx_want_ranges_iota
91#define __glibcxx_want_saturation_arithmetic
94#if __glibcxx_ranges_iota >= 202202L
98#ifdef __glibcxx_saturation_arithmetic
110namespace std _GLIBCXX_VISIBILITY(default)
112_GLIBCXX_BEGIN_NAMESPACE_VERSION
114#if __cplusplus >= 201402L
119 template<
typename _Res,
typename _Tp>
123 static_assert(
sizeof(_Res) >=
sizeof(_Tp),
124 "result type must be at least as wide as the input type");
128#ifdef _GLIBCXX_ASSERTIONS
129 if (!__is_constant_evaluated())
132 return -
static_cast<_Res
>(__val);
135 template<
typename>
void __abs_r(
bool) =
delete;
138 template<
typename _Tp>
140 __gcd(_Tp __m, _Tp __n)
142 static_assert(is_unsigned<_Tp>::value,
"type must be unsigned");
149 const int __i = std::__countr_zero(__m);
151 const int __j = std::__countr_zero(__n);
153 const int __k = __i < __j ? __i : __j;
169 __n >>= std::__countr_zero(__n);
175#ifdef __cpp_lib_gcd_lcm
177 template<typename _Mn, typename _Nn>
178 constexpr common_type_t<_Mn, _Nn>
179 gcd(_Mn __m, _Nn __n)
noexcept
181 static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
182 "std::gcd arguments must be integers");
183 static_assert(_Mn(2) == 2 && _Nn(2) == 2,
184 "std::gcd arguments must not be bool");
185 using _Ct = common_type_t<_Mn, _Nn>;
186 const _Ct __m2 = __detail::__abs_r<_Ct>(__m);
187 const _Ct __n2 = __detail::__abs_r<_Ct>(__n);
188 return __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2);
192 template<
typename _Mn,
typename _Nn>
193 constexpr common_type_t<_Mn, _Nn>
194 lcm(_Mn __m, _Nn __n)
noexcept
196 static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
197 "std::lcm arguments must be integers");
198 static_assert(_Mn(2) == 2 && _Nn(2) == 2,
199 "std::lcm arguments must not be bool");
200 using _Ct = common_type_t<_Mn, _Nn>;
201 const _Ct __m2 = __detail::__abs_r<_Ct>(__m);
202 const _Ct __n2 = __detail::__abs_r<_Ct>(__n);
203 if (__m2 == 0 || __n2 == 0)
205 _Ct __r = __m2 / __detail::__gcd<make_unsigned_t<_Ct>>(__m2, __n2);
207 if constexpr (is_signed_v<_Ct>)
208 if (__is_constant_evaluated())
211 bool __overflow = __builtin_mul_overflow(__r, __n2, &__r);
212 __glibcxx_assert(!__overflow);
219#ifdef __cpp_lib_interpolate
220 template<
typename _Tp>
222 enable_if_t<__and_v<is_arithmetic<_Tp>, is_same<remove_cv_t<_Tp>, _Tp>,
223 __not_<is_same<_Tp, bool>>>,
225 midpoint(_Tp __a, _Tp __b)
noexcept
227 if constexpr (is_integral_v<_Tp>)
229 using _Up = make_unsigned_t<_Tp>;
240 return __a + __k * _Tp(_Up(__M - __m) / 2);
246 const _Tp __abs_a = __a < 0 ? -__a : __a;
247 const _Tp __abs_b = __b < 0 ? -__b : __b;
248 if (__abs_a <= __hi && __abs_b <= __hi) [[likely]]
249 return (__a + __b) / 2;
254 return __a/2 + __b/2;
258 template<
typename _Tp>
259 constexpr enable_if_t<is_object_v<_Tp>, _Tp*>
260 midpoint(_Tp* __a, _Tp* __b)
noexcept
262 static_assert(
sizeof(_Tp) != 0,
"type must be complete" );
263 return __a + (__b - __a) / 2;
267#if __cplusplus >= 201703L
290 template<
typename _InputIterator,
typename _Tp,
typename _BinaryOperation>
293 reduce(_InputIterator __first, _InputIterator __last, _Tp __init,
294 _BinaryOperation __binary_op)
297 static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, _Tp&, __ref>);
298 static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, __ref, _Tp&>);
299 static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, _Tp&, _Tp&>);
300 static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, __ref, __ref>);
301 if constexpr (__is_random_access_iter<_InputIterator>::value)
303 while ((__last - __first) >= 4)
305 _Tp __v1 = __binary_op(__first[0], __first[1]);
306 _Tp __v2 = __binary_op(__first[2], __first[3]);
307 _Tp __v3 = __binary_op(__v1, __v2);
308 __init = __binary_op(__init, __v3);
312 for (; __first != __last; ++__first)
313 __init = __binary_op(__init, *__first);
328 template<
typename _InputIterator,
typename _Tp>
331 reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
345 template<
typename _InputIterator>
347 inline typename iterator_traits<_InputIterator>::value_type
348 reduce(_InputIterator __first, _InputIterator __last)
372 template<
typename _InputIterator1,
typename _InputIterator2,
typename _Tp,
373 typename _BinaryOperation1,
typename _BinaryOperation2>
377 _InputIterator2 __first2, _Tp __init,
378 _BinaryOperation1 __binary_op1,
379 _BinaryOperation2 __binary_op2)
381 if constexpr (__and_v<__is_random_access_iter<_InputIterator1>,
382 __is_random_access_iter<_InputIterator2>>)
384 while ((__last1 - __first1) >= 4)
386 _Tp __v1 = __binary_op1(__binary_op2(__first1[0], __first2[0]),
387 __binary_op2(__first1[1], __first2[1]));
388 _Tp __v2 = __binary_op1(__binary_op2(__first1[2], __first2[2]),
389 __binary_op2(__first1[3], __first2[3]));
390 _Tp __v3 = __binary_op1(__v1, __v2);
391 __init = __binary_op1(__init, __v3);
396 for (; __first1 != __last1; ++__first1, (void) ++__first2)
397 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
416 template<
typename _InputIterator1,
typename _InputIterator2,
typename _Tp>
420 _InputIterator2 __first2, _Tp __init)
441 template<
typename _InputIterator,
typename _Tp,
442 typename _BinaryOperation,
typename _UnaryOperation>
446 _BinaryOperation __binary_op, _UnaryOperation __unary_op)
448 if constexpr (__is_random_access_iter<_InputIterator>::value)
450 while ((__last - __first) >= 4)
452 _Tp __v1 = __binary_op(__unary_op(__first[0]),
453 __unary_op(__first[1]));
454 _Tp __v2 = __binary_op(__unary_op(__first[2]),
455 __unary_op(__first[3]));
456 _Tp __v3 = __binary_op(__v1, __v2);
457 __init = __binary_op(__init, __v3);
461 for (; __first != __last; ++__first)
462 __init = __binary_op(__init, __unary_op(*__first));
484 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp,
485 typename _BinaryOperation>
489 _OutputIterator __result, _Tp __init,
490 _BinaryOperation __binary_op)
492 while (__first != __last)
495 __init = __binary_op(__v, *__first);
519 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
521 inline _OutputIterator
523 _OutputIterator __result, _Tp __init)
547 template<
typename _InputIterator,
typename _OutputIterator,
548 typename _BinaryOperation,
typename _Tp>
552 _OutputIterator __result, _BinaryOperation __binary_op,
555 for (; __first != __last; ++__first)
556 *__result++ = __init = __binary_op(__init, *__first);
576 template<
typename _InputIterator,
typename _OutputIterator,
577 typename _BinaryOperation>
581 _OutputIterator __result, _BinaryOperation __binary_op)
583 if (__first != __last)
585 auto __init = *__first;
586 *__result++ = __init;
588 if (__first != __last)
610 template<
typename _InputIterator,
typename _OutputIterator>
612 inline _OutputIterator
614 _OutputIterator __result)
637 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp,
638 typename _BinaryOperation,
typename _UnaryOperation>
642 _OutputIterator __result, _Tp __init,
643 _BinaryOperation __binary_op,
644 _UnaryOperation __unary_op)
646 while (__first != __last)
649 __init = __binary_op(__init, __unary_op(*__first));
676 template<
typename _InputIterator,
typename _OutputIterator,
677 typename _BinaryOperation,
typename _UnaryOperation,
typename _Tp>
681 _OutputIterator __result,
682 _BinaryOperation __binary_op,
683 _UnaryOperation __unary_op,
686 for (; __first != __last; ++__first)
687 *__result++ = __init = __binary_op(__init, __unary_op(*__first));
710 template<
typename _InputIterator,
typename _OutputIterator,
711 typename _BinaryOperation,
typename _UnaryOperation>
715 _OutputIterator __result,
716 _BinaryOperation __binary_op,
717 _UnaryOperation __unary_op)
719 if (__first != __last)
721 auto __init = __unary_op(*__first);
722 *__result++ = __init;
724 if (__first != __last)
726 __binary_op, __unary_op,
737#if __glibcxx_ranges_iota >= 202202L
739 template<
typename _Out,
typename _Tp>
740 using iota_result = out_value_result<_Out, _Tp>;
744 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp>
745 requires indirectly_writable<_Out, const _Tp&>
746 constexpr iota_result<_Out, _Tp>
747 operator()(_Out __first, _Sent __last, _Tp __value)
const
749 while (__first != __last)
751 *__first =
static_cast<const _Tp&
>(__value);
758 template<weakly_incrementable _Tp, output_range<const _Tp&> _Range>
759 constexpr iota_result<borrowed_iterator_t<_Range>, _Tp>
760 operator()(_Range&& __r, _Tp __value)
const
761 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__value)); }
764 inline constexpr __iota_fn
iota{};
769_GLIBCXX_END_NAMESPACE_VERSION
772#if __cplusplus >= 201703L && _GLIBCXX_HOSTED
774# if _PSTL_EXECUTION_POLICIES_DEFINED
776# include <pstl/glue_numeric_impl.h>
779# include <pstl/glue_numeric_defs.h>
780# define _PSTL_NUMERIC_FORWARD_DECLARED 1
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op, _Tp __init)
Output the cumulative sum of one range to a second range.
constexpr _OutputIterator exclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Tp __init, _BinaryOperation __binary_op)
Output the cumulative sum of one range to a second range.
constexpr _OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op, _Tp __init)
Output the cumulative sum of one range to a second range.
constexpr void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
Create a range of sequentially increasing values.
constexpr _OutputIterator transform_exclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op)
Output the cumulative sum of one range to a second range.
constexpr _Tp transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)
Combine elements from two ranges and reduce.
constexpr _Tp reduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op)
Calculate reduction of values in a range.
ISO C++ entities toplevel namespace is std.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
constexpr common_type_t< _Mn, _Nn > lcm(_Mn __m, _Nn __n)
Least common multiple.
constexpr common_type_t< _Mn, _Nn > gcd(_Mn __m, _Nn __n) noexcept
Greatest common divisor.
static constexpr _Tp max() noexcept
static constexpr _Tp min() noexcept
One of the math functors.
One of the math functors.
Traits class for iterators.
Parallel STL function calls corresponding to stl_numeric.h. The functions defined here mainly do case...