1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // UNSUPPORTED: c++03, c++11, c++14 10 11 // <numeric> 12 13 // template<class _M, class _N> 14 // constexpr common_type_t<_M,_N> gcd(_M __m, _N __n) 15 16 #include <numeric> 17 #include <cassert> 18 #include <climits> 19 #include <cstdint> 20 #include <limits> 21 #include <random> 22 #include <type_traits> 23 24 #include "test_macros.h" 25 26 constexpr struct { 27 int x; 28 int y; 29 int expect; 30 } Cases[] = { 31 {0, 0, 0}, 32 {1, 0, 1}, 33 {0, 1, 1}, 34 {1, 1, 1}, 35 {2, 3, 1}, 36 {2, 4, 2}, 37 {36, 17, 1}, 38 {36, 18, 18} 39 }; 40 41 42 template <typename Input1, typename Input2, typename Output> 43 constexpr bool test0(int in1, int in2, int out) 44 { 45 auto value1 = static_cast<Input1>(in1); 46 auto value2 = static_cast<Input2>(in2); 47 static_assert(std::is_same_v<Output, decltype(std::gcd(value1, value2))>, ""); 48 static_assert(std::is_same_v<Output, decltype(std::gcd(value2, value1))>, ""); 49 assert(static_cast<Output>(out) == std::gcd(value1, value2)); 50 return true; 51 } 52 53 template <typename T> 54 T basic_gcd_(T m, T n) { 55 return n == 0 ? m : basic_gcd_<T>(n, m % n); 56 } 57 58 template <typename T> 59 T basic_gcd(T m, T n) { 60 using Tp = std::make_unsigned_t<T>; 61 if constexpr (std::is_signed_v<T>) { 62 if (m < 0 && m != std::numeric_limits<T>::min()) 63 m = -m; 64 if (n < 0 && n != std::numeric_limits<T>::min()) 65 n = -n; 66 } 67 return basic_gcd_(static_cast<Tp>(m), static_cast<Tp>(n)); 68 } 69 70 template <typename Input> 71 void do_fuzzy_tests() { 72 std::mt19937 gen(1938); 73 using DistIntType = std::conditional_t<sizeof(Input) == 1, int, Input>; // See N4981 [rand.req.genl]/1.5 74 constexpr Input max_input = std::numeric_limits<Input>::max(); 75 std::uniform_int_distribution<DistIntType> distrib(0, max_input); 76 77 constexpr int nb_rounds = 10000; 78 for (int i = 0; i < nb_rounds; ++i) { 79 Input n = static_cast<Input>(distrib(gen)); 80 Input m = static_cast<Input>(distrib(gen)); 81 assert(std::gcd(n, m) == basic_gcd(n, m)); 82 } 83 } 84 85 template <typename Input> 86 void do_limit_tests() { 87 Input inputs[] = { 88 // The behavior of std::gcd is undefined if the absolute value of one of its 89 // operand is not representable in the result type. 90 std::numeric_limits<Input>::min() + (std::is_signed<Input>::value ? 3 : 0), 91 std::numeric_limits<Input>::min() + 1, 92 std::numeric_limits<Input>::min() + 2, 93 std::numeric_limits<Input>::max(), 94 std::numeric_limits<Input>::max() - 1, 95 std::numeric_limits<Input>::max() - 2, 96 0, 97 1, 98 2, 99 3, 100 4, 101 5, 102 6, 103 7, 104 8, 105 9, 106 10, 107 (Input)-1, 108 (Input)-2, 109 (Input)-3, 110 (Input)-4, 111 (Input)-5, 112 (Input)-6, 113 (Input)-7, 114 (Input)-8, 115 (Input)-9, 116 (Input)-10, 117 }; 118 119 for (auto n : inputs) { 120 for (auto m : inputs) { 121 assert(std::gcd(n, m) == basic_gcd(n, m)); 122 } 123 } 124 } 125 126 template <typename Input1, typename Input2 = Input1> 127 constexpr bool do_test(int = 0) 128 { 129 using S1 = std::make_signed_t<Input1>; 130 using S2 = std::make_signed_t<Input2>; 131 using U1 = std::make_unsigned_t<Input1>; 132 using U2 = std::make_unsigned_t<Input2>; 133 bool accumulate = true; 134 for (auto TC : Cases) { 135 { // Test with two signed types 136 using Output = std::common_type_t<S1, S2>; 137 accumulate &= test0<S1, S2, Output>(TC.x, TC.y, TC.expect); 138 accumulate &= test0<S1, S2, Output>(-TC.x, TC.y, TC.expect); 139 accumulate &= test0<S1, S2, Output>(TC.x, -TC.y, TC.expect); 140 accumulate &= test0<S1, S2, Output>(-TC.x, -TC.y, TC.expect); 141 accumulate &= test0<S2, S1, Output>(TC.x, TC.y, TC.expect); 142 accumulate &= test0<S2, S1, Output>(-TC.x, TC.y, TC.expect); 143 accumulate &= test0<S2, S1, Output>(TC.x, -TC.y, TC.expect); 144 accumulate &= test0<S2, S1, Output>(-TC.x, -TC.y, TC.expect); 145 } 146 { // test with two unsigned types 147 using Output = std::common_type_t<U1, U2>; 148 accumulate &= test0<U1, U2, Output>(TC.x, TC.y, TC.expect); 149 accumulate &= test0<U2, U1, Output>(TC.x, TC.y, TC.expect); 150 } 151 { // Test with mixed signs 152 using Output = std::common_type_t<S1, U2>; 153 accumulate &= test0<S1, U2, Output>(TC.x, TC.y, TC.expect); 154 accumulate &= test0<U2, S1, Output>(TC.x, TC.y, TC.expect); 155 accumulate &= test0<S1, U2, Output>(-TC.x, TC.y, TC.expect); 156 accumulate &= test0<U2, S1, Output>(TC.x, -TC.y, TC.expect); 157 } 158 { // Test with mixed signs 159 using Output = std::common_type_t<S2, U1>; 160 accumulate &= test0<S2, U1, Output>(TC.x, TC.y, TC.expect); 161 accumulate &= test0<U1, S2, Output>(TC.x, TC.y, TC.expect); 162 accumulate &= test0<S2, U1, Output>(-TC.x, TC.y, TC.expect); 163 accumulate &= test0<U1, S2, Output>(TC.x, -TC.y, TC.expect); 164 } 165 } 166 return accumulate; 167 } 168 169 int main(int argc, char**) 170 { 171 int non_cce = argc; // a value that can't possibly be constexpr 172 173 static_assert(do_test<signed char>(), ""); 174 static_assert(do_test<short>(), ""); 175 static_assert(do_test<int>(), ""); 176 static_assert(do_test<long>(), ""); 177 static_assert(do_test<long long>(), ""); 178 179 assert(do_test<signed char>(non_cce)); 180 assert(do_test<short>(non_cce)); 181 assert(do_test<int>(non_cce)); 182 assert(do_test<long>(non_cce)); 183 assert(do_test<long long>(non_cce)); 184 185 static_assert(do_test<std::int8_t>(), ""); 186 static_assert(do_test<std::int16_t>(), ""); 187 static_assert(do_test<std::int32_t>(), ""); 188 static_assert(do_test<std::int64_t>(), ""); 189 190 assert(do_test<std::int8_t>(non_cce)); 191 assert(do_test<std::int16_t>(non_cce)); 192 assert(do_test<std::int32_t>(non_cce)); 193 assert(do_test<std::int64_t>(non_cce)); 194 195 static_assert(do_test<signed char, int>(), ""); 196 static_assert(do_test<int, signed char>(), ""); 197 static_assert(do_test<short, int>(), ""); 198 static_assert(do_test<int, short>(), ""); 199 static_assert(do_test<int, long>(), ""); 200 static_assert(do_test<long, int>(), ""); 201 static_assert(do_test<int, long long>(), ""); 202 static_assert(do_test<long long, int>(), ""); 203 204 assert((do_test<signed char, int>(non_cce))); 205 assert((do_test<int, signed char>(non_cce))); 206 assert((do_test<short, int>(non_cce))); 207 assert((do_test<int, short>(non_cce))); 208 assert((do_test<int, long>(non_cce))); 209 assert((do_test<long, int>(non_cce))); 210 assert((do_test<int, long long>(non_cce))); 211 assert((do_test<long long, int>(non_cce))); 212 213 // LWG#2837 214 { 215 auto res = std::gcd(static_cast<std::int64_t>(1234), INT32_MIN); 216 static_assert(std::is_same_v<decltype(res), std::int64_t>, ""); 217 assert(res == 2); 218 } 219 220 do_fuzzy_tests<std::int8_t>(); 221 do_fuzzy_tests<std::int16_t>(); 222 do_fuzzy_tests<std::int32_t>(); 223 do_fuzzy_tests<std::int64_t>(); 224 do_fuzzy_tests<std::uint8_t>(); 225 do_fuzzy_tests<std::uint16_t>(); 226 do_fuzzy_tests<std::uint32_t>(); 227 do_fuzzy_tests<std::uint64_t>(); 228 229 do_limit_tests<std::int8_t>(); 230 do_limit_tests<std::int16_t>(); 231 do_limit_tests<std::int32_t>(); 232 do_limit_tests<std::int64_t>(); 233 do_limit_tests<std::uint8_t>(); 234 do_limit_tests<std::uint16_t>(); 235 do_limit_tests<std::uint32_t>(); 236 do_limit_tests<std::uint64_t>(); 237 238 return 0; 239 } 240