codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===---------------------------- numeric ---------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX_NUMERIC11#define _LIBCUDACXX_NUMERIC12 13/*14 numeric synopsis15 16namespace std17{18 19#ifndef __cuda_std__20template <class InputIterator, class T>21 T22 accumulate(InputIterator first, InputIterator last, T init);23 24template <class InputIterator, class T, class BinaryOperation>25 T26 accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);27 28template<class InputIterator>29 typename iterator_traits<InputIterator>::value_type30 reduce(InputIterator first, InputIterator last); // C++1731 32template<class InputIterator, class T>33 T34 reduce(InputIterator first, InputIterator last, T init); // C++1735 36template<class InputIterator, class T, class BinaryOperation>37 T38 reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); // C++1739 40template <class InputIterator1, class InputIterator2, class T>41 T42 inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);43 44template <class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2>45 T46 inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,47 T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);48 49 50template<class InputIterator1, class InputIterator2, class T>51 T52 transform_reduce(InputIterator1 first1, InputIterator1 last1,53 InputIterator2 first2, T init); // C++1754 55template<class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2>56 T57 transform_reduce(InputIterator1 first1, InputIterator1 last1,58 InputIterator2 first2, T init,59 BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); // C++1760 61template<class InputIterator, class T, class BinaryOperation, class UnaryOperation>62 T63 transform_reduce(InputIterator first, InputIterator last, T init,64 BinaryOperation binary_op, UnaryOperation unary_op); // C++1765 66template <class InputIterator, class OutputIterator>67 OutputIterator68 partial_sum(InputIterator first, InputIterator last, OutputIterator result);69 70template <class InputIterator, class OutputIterator, class BinaryOperation>71 OutputIterator72 partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);73 74template<class InputIterator, class OutputIterator, class T>75 OutputIterator76 exclusive_scan(InputIterator first, InputIterator last,77 OutputIterator result, T init); // C++1778 79template<class InputIterator, class OutputIterator, class T, class BinaryOperation>80 OutputIterator81 exclusive_scan(InputIterator first, InputIterator last,82 OutputIterator result, T init, BinaryOperation binary_op); // C++1783 84template<class InputIterator, class OutputIterator>85 OutputIterator86 inclusive_scan(InputIterator first, InputIterator last, OutputIterator result); // C++1787 88template<class InputIterator, class OutputIterator, class BinaryOperation>89 OutputIterator90 inclusive_scan(InputIterator first, InputIterator last,91 OutputIterator result, BinaryOperation binary_op); // C++1792 93template<class InputIterator, class OutputIterator, class BinaryOperation, class T>94 OutputIterator95 inclusive_scan(InputIterator first, InputIterator last,96 OutputIterator result, BinaryOperation binary_op, T init); // C++1797 98template<class InputIterator, class OutputIterator, class T,99 class BinaryOperation, class UnaryOperation>100 OutputIterator101 transform_exclusive_scan(InputIterator first, InputIterator last,102 OutputIterator result, T init,103 BinaryOperation binary_op, UnaryOperation unary_op); // C++17104 105template<class InputIterator, class OutputIterator,106 class BinaryOperation, class UnaryOperation>107 OutputIterator108 transform_inclusive_scan(InputIterator first, InputIterator last,109 OutputIterator result,110 BinaryOperation binary_op, UnaryOperation unary_op); // C++17111 112template<class InputIterator, class OutputIterator,113 class BinaryOperation, class UnaryOperation, class T>114 OutputIterator115 transform_inclusive_scan(InputIterator first, InputIterator last,116 OutputIterator result,117 BinaryOperation binary_op, UnaryOperation unary_op,118 T init); // C++17119 120template <class InputIterator, class OutputIterator>121 OutputIterator122 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);123 124template <class InputIterator, class OutputIterator, class BinaryOperation>125 OutputIterator126 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);127#endif // __cuda_std__128 129template <class ForwardIterator, class T>130 void iota(ForwardIterator first, ForwardIterator last, T value);131 132#ifndef __cuda_std__133template <class M, class N>134 constexpr common_type_t<M,N> gcd(M m, N n); // C++17135 136template <class M, class N>137 constexpr common_type_t<M,N> lcm(M m, N n); // C++17138#endif // __cuda_std__139 140integer midpoint(integer a, integer b); // C++20141pointer midpoint(pointer a, pointer b); // C++20142floating_point midpoint(floating_point a, floating_point b); // C++20143 144} // std145 146*/147 148#ifndef __cuda_std__149#include <__config>150#endif // __cuda_std__151 152#include "__assert" // all public C++ headers provide the assertion handler153#include "__iterator/iterator_traits.h"154#include "__utility/move.h"155#include "cmath" // for isnormal156#include "functional"157#include "limits" // for numeric_limits158#include "version"159 160#ifndef __cuda_std__161#include <__pragma_push>162#endif // __cuda_std__163 164#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)165# pragma GCC system_header166#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)167# pragma clang system_header168#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)169# pragma system_header170#endif // no system header171 172_LIBCUDACXX_BEGIN_NAMESPACE_STD173 174#ifndef __cuda_std__175template <class _InputIterator, class _Tp>176inline _LIBCUDACXX_INLINE_VISIBILITY177_Tp178accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)179{180 for (; __first != __last; ++__first)181 __init = __init + *__first;182 return __init;183}184 185template <class _InputIterator, class _Tp, class _BinaryOperation>186inline _LIBCUDACXX_INLINE_VISIBILITY187_Tp188accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op)189{190 for (; __first != __last; ++__first)191 __init = __binary_op(__init, *__first);192 return __init;193}194 195#if _LIBCUDACXX_STD_VER > 14196template <class _InputIterator, class _Tp, class _BinaryOp>197inline _LIBCUDACXX_INLINE_VISIBILITY198_Tp199reduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOp __b)200{201 for (; __first != __last; ++__first)202 __init = __b(__init, *__first);203 return __init;204}205 206template <class _InputIterator, class _Tp>207inline _LIBCUDACXX_INLINE_VISIBILITY208_Tp209reduce(_InputIterator __first, _InputIterator __last, _Tp __init)210{211 return _CUDA_VSTD::reduce(__first, __last, __init, _CUDA_VSTD::plus<>());212}213 214template <class _InputIterator>215inline _LIBCUDACXX_INLINE_VISIBILITY216typename iterator_traits<_InputIterator>::value_type217reduce(_InputIterator __first, _InputIterator __last)218{219 return _CUDA_VSTD::reduce(__first, __last,220 typename iterator_traits<_InputIterator>::value_type{});221}222#endif223 224template <class _InputIterator1, class _InputIterator2, class _Tp>225inline _LIBCUDACXX_INLINE_VISIBILITY226_Tp227inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init)228{229 for (; __first1 != __last1; ++__first1, (void) ++__first2)230 __init = __init + *__first1 * *__first2;231 return __init;232}233 234template <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>235inline _LIBCUDACXX_INLINE_VISIBILITY236_Tp237inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,238 _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)239{240 for (; __first1 != __last1; ++__first1, (void) ++__first2)241 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));242 return __init;243}244 245#if _LIBCUDACXX_STD_VER > 14246template <class _InputIterator, class _Tp, class _BinaryOp, class _UnaryOp>247inline _LIBCUDACXX_INLINE_VISIBILITY248_Tp249transform_reduce(_InputIterator __first, _InputIterator __last,250 _Tp __init, _BinaryOp __b, _UnaryOp __u)251{252 for (; __first != __last; ++__first)253 __init = __b(__init, __u(*__first));254 return __init;255}256 257template <class _InputIterator1, class _InputIterator2,258 class _Tp, class _BinaryOp1, class _BinaryOp2>259inline _LIBCUDACXX_INLINE_VISIBILITY260_Tp261transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1,262 _InputIterator2 __first2, _Tp __init, _BinaryOp1 __b1, _BinaryOp2 __b2)263{264 for (; __first1 != __last1; ++__first1, (void) ++__first2)265 __init = __b1(__init, __b2(*__first1, *__first2));266 return __init;267}268 269template <class _InputIterator1, class _InputIterator2, class _Tp>270inline _LIBCUDACXX_INLINE_VISIBILITY271_Tp272transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1,273 _InputIterator2 __first2, _Tp __init)274{275 return _CUDA_VSTD::transform_reduce(__first1, __last1, __first2, _CUDA_VSTD::move(__init),276 _CUDA_VSTD::plus<>(), _CUDA_VSTD::multiplies<>());277}278#endif279 280template <class _InputIterator, class _OutputIterator>281inline _LIBCUDACXX_INLINE_VISIBILITY282_OutputIterator283partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result)284{285 if (__first != __last)286 {287 typename iterator_traits<_InputIterator>::value_type __t(*__first);288 *__result = __t;289 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)290 {291 __t = __t + *__first;292 *__result = __t;293 }294 }295 return __result;296}297 298template <class _InputIterator, class _OutputIterator, class _BinaryOperation>299inline _LIBCUDACXX_INLINE_VISIBILITY300_OutputIterator301partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result,302 _BinaryOperation __binary_op)303{304 if (__first != __last)305 {306 typename iterator_traits<_InputIterator>::value_type __t(*__first);307 *__result = __t;308 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)309 {310 __t = __binary_op(__t, *__first);311 *__result = __t;312 }313 }314 return __result;315}316 317#if _LIBCUDACXX_STD_VER > 14318template <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp>319inline _LIBCUDACXX_INLINE_VISIBILITY320_OutputIterator321exclusive_scan(_InputIterator __first, _InputIterator __last,322 _OutputIterator __result, _Tp __init, _BinaryOp __b)323{324 if (__first != __last)325 {326 _Tp __saved = __init;327 do328 {329 __init = __b(__init, *__first);330 *__result = __saved;331 __saved = __init;332 ++__result;333 } while (++__first != __last);334 }335 return __result;336}337 338template <class _InputIterator, class _OutputIterator, class _Tp>339inline _LIBCUDACXX_INLINE_VISIBILITY340_OutputIterator341exclusive_scan(_InputIterator __first, _InputIterator __last,342 _OutputIterator __result, _Tp __init)343{344 return _CUDA_VSTD::exclusive_scan(__first, __last, __result, __init, _CUDA_VSTD::plus<>());345}346 347template <class _InputIterator, class _OutputIterator, class _BinaryOp, class _Tp>348_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last,349 _OutputIterator __result, _BinaryOp __b, _Tp __init)350{351 for (; __first != __last; ++__first, (void) ++__result) {352 __init = __b(__init, *__first);353 *__result = __init;354 }355 return __result;356}357 358template <class _InputIterator, class _OutputIterator, class _BinaryOp>359_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last,360 _OutputIterator __result, _BinaryOp __b)361{362 if (__first != __last) {363 typename std::iterator_traits<_InputIterator>::value_type __init = *__first;364 *__result++ = __init;365 if (++__first != __last)366 return _CUDA_VSTD::inclusive_scan(__first, __last, __result, __b, __init);367 }368 369 return __result;370}371 372template <class _InputIterator, class _OutputIterator>373_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last,374 _OutputIterator __result)375{376 return _CUDA_VSTD::inclusive_scan(__first, __last, __result, std::plus<>());377}378 379template <class _InputIterator, class _OutputIterator, class _Tp,380 class _BinaryOp, class _UnaryOp>381inline _LIBCUDACXX_INLINE_VISIBILITY382_OutputIterator383transform_exclusive_scan(_InputIterator __first, _InputIterator __last,384 _OutputIterator __result, _Tp __init,385 _BinaryOp __b, _UnaryOp __u)386{387 if (__first != __last)388 {389 _Tp __saved = __init;390 do391 {392 __init = __b(__init, __u(*__first));393 *__result = __saved;394 __saved = __init;395 ++__result;396 } while (++__first != __last);397 }398 return __result;399}400 401template <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp, class _UnaryOp>402_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last,403 _OutputIterator __result, _BinaryOp __b, _UnaryOp __u, _Tp __init)404{405 for (; __first != __last; ++__first, (void) ++__result) {406 __init = __b(__init, __u(*__first));407 *__result = __init;408 }409 410 return __result;411}412 413template <class _InputIterator, class _OutputIterator, class _BinaryOp, class _UnaryOp>414_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last,415 _OutputIterator __result, _BinaryOp __b, _UnaryOp __u)416{417 if (__first != __last) {418 typename std::iterator_traits<_InputIterator>::value_type __init = __u(*__first);419 *__result++ = __init;420 if (++__first != __last)421 return _CUDA_VSTD::transform_inclusive_scan(__first, __last, __result, __b, __u, __init);422 }423 424 return __result;425}426#endif427 428template <class _InputIterator, class _OutputIterator>429inline _LIBCUDACXX_INLINE_VISIBILITY430_OutputIterator431adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result)432{433 if (__first != __last)434 {435 typename iterator_traits<_InputIterator>::value_type __t1(*__first);436 *__result = __t1;437 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)438 {439 typename iterator_traits<_InputIterator>::value_type __t2(*__first);440 *__result = __t2 - __t1;441 __t1 = _CUDA_VSTD::move(__t2);442 }443 }444 return __result;445}446 447template <class _InputIterator, class _OutputIterator, class _BinaryOperation>448inline _LIBCUDACXX_INLINE_VISIBILITY449_OutputIterator450adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result,451 _BinaryOperation __binary_op)452{453 if (__first != __last)454 {455 typename iterator_traits<_InputIterator>::value_type __t1(*__first);456 *__result = __t1;457 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)458 {459 typename iterator_traits<_InputIterator>::value_type __t2(*__first);460 *__result = __binary_op(__t2, __t1);461 __t1 = _CUDA_VSTD::move(__t2);462 }463 }464 return __result;465}466#endif // __cuda_std__467 468template <class _ForwardIterator, class _Tp>469inline _LIBCUDACXX_INLINE_VISIBILITY470void471iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_)472{473 for (; __first != __last; ++__first, (void) ++__value_)474 *__first = __value_;475}476 477 478#ifndef __cuda_std__479#if _LIBCUDACXX_STD_VER > 14480template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __ct_abs;481 482template <typename _Result, typename _Source>483struct __ct_abs<_Result, _Source, true> {484 constexpr _LIBCUDACXX_INLINE_VISIBILITY485 _Result operator()(_Source __t) const noexcept486 {487 if (__t >= 0) return __t;488 if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t);489 return -__t;490 }491};492 493template <typename _Result, typename _Source>494struct __ct_abs<_Result, _Source, false> {495 constexpr _LIBCUDACXX_INLINE_VISIBILITY496 _Result operator()(_Source __t) const noexcept { return __t; }497};498 499 500template<class _Tp>501constexpr _LIBCUDACXX_HIDDEN502_Tp __gcd(_Tp __m, _Tp __n)503{504 static_assert((!is_signed<_Tp>::value), "");505 return __n == 0 ? __m : _CUDA_VSTD::__gcd<_Tp>(__n, __m % __n);506}507 508 509template<class _Tp, class _Up>510constexpr _LIBCUDACXX_INLINE_VISIBILITY511common_type_t<_Tp,_Up>512gcd(_Tp __m, _Up __n)513{514 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types");515 static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to gcd cannot be bool" );516 static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to gcd cannot be bool" );517 using _Rp = common_type_t<_Tp,_Up>;518 using _Wp = make_unsigned_t<_Rp>;519 return static_cast<_Rp>(_CUDA_VSTD::__gcd(520 static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)),521 static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n))));522}523 524template<class _Tp, class _Up>525constexpr _LIBCUDACXX_INLINE_VISIBILITY526common_type_t<_Tp,_Up>527lcm(_Tp __m, _Up __n)528{529 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types");530 static_assert((!is_same<__remove_cv_t<_Tp>, bool>::value), "First argument to lcm cannot be bool" );531 static_assert((!is_same<__remove_cv_t<_Up>, bool>::value), "Second argument to lcm cannot be bool" );532 if (__m == 0 || __n == 0)533 return 0;534 535 using _Rp = common_type_t<_Tp,_Up>;536 _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / _CUDA_VSTD::gcd(__m, __n);537 _Rp __val2 = __ct_abs<_Rp, _Up>()(__n);538 _LIBCUDACXX_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm");539 return __val1 * __val2;540}541 542#endif /* _LIBCUDACXX_STD_VER > 14 */543 544#if _LIBCUDACXX_STD_VER > 17545template <class _Tp>546_LIBCUDACXX_INLINE_VISIBILITY constexpr547enable_if_t<is_integral_v<_Tp> && !is_same_v<bool, _Tp> && !is_null_pointer_v<_Tp>, _Tp>548midpoint(_Tp __a, _Tp __b) noexcept549_LIBCUDACXX_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK550{551 using _Up = std::make_unsigned_t<_Tp>;552 553 int __sign = 1;554 _Up __m = __a;555 _Up __M = __b;556 if (__a > __b)557 {558 __sign = -1;559 __m = __b;560 __M = __a;561 }562 return __a + __sign * _Tp(_Up(__M-__m) >> 1);563}564 565 566template <class _TPtr>567_LIBCUDACXX_INLINE_VISIBILITY constexpr568enable_if_t<is_pointer_v<_TPtr>569 && is_object_v<remove_pointer_t<_TPtr>>570 && ! is_void_v<remove_pointer_t<_TPtr>>571 && (sizeof(remove_pointer_t<_TPtr>) > 0), _TPtr>572midpoint(_TPtr __a, _TPtr __b) noexcept573{574 return __a + _CUDA_VSTD::midpoint(ptrdiff_t(0), __b - __a);575}576 577 578template <typename _Tp>579constexpr int __sign(_Tp __val) {580 return (_Tp(0) < __val) - (__val < _Tp(0));581}582 583template <typename _Fp>584constexpr _Fp __fp_abs(_Fp __f) { return __f >= 0 ? __f : -__f; }585 586template <class _Fp>587_LIBCUDACXX_INLINE_VISIBILITY constexpr588enable_if_t<is_floating_point_v<_Fp>, _Fp>589midpoint(_Fp __a, _Fp __b) noexcept590{591 constexpr _Fp __lo = numeric_limits<_Fp>::min()*2;592 constexpr _Fp __hi = numeric_limits<_Fp>::max()/2;593 return __fp_abs(__a) <= __hi && __fp_abs(__b) <= __hi ? // typical case: overflow is impossible594 (__a + __b)/2 : // always correctly rounded595 __fp_abs(__a) < __lo ? __a + __b/2 : // not safe to halve a596 __fp_abs(__a) < __lo ? __a/2 + __b : // not safe to halve b597 __a/2 + __b/2; // otherwise correctly rounded598}599 600#endif // _LIBCUDACXX_STD_VER > 17601#endif // __cuda_std__602 603_LIBCUDACXX_END_NAMESPACE_STD604 605#if defined(_LIBCUDACXX_HAS_PARALLEL_ALGORITHMS) && _LIBCUDACXX_STD_VER >= 17606# include <__pstl_numeric>607#endif608 609#ifndef __cuda_std__610#include <__pragma_pop>611#endif //__cuda_std__612 613#endif // _LIBCUDACXX_NUMERIC614