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