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

source code of libcxx/test/std/numerics/numeric.ops/numeric.ops.gcd/gcd.pass.cpp