1// ratio.hpp ---------------------------------------------------------------//
2
3// Copyright 2008 Howard Hinnant
4// Copyright 2008 Beman Dawes
5// Copyright 2009 Vicente J. Botet Escriba
6
7// Distributed under the Boost Software License, Version 1.0.
8// See http://www.boost.org/LICENSE_1_0.txt
9
10/*
11
12This code was derived by Beman Dawes from Howard Hinnant's time2_demo prototype.
13Many thanks to Howard for making his code available under the Boost license.
14The original code was modified to conform to Boost conventions and to section
1520.4 Compile-time rational arithmetic [ratio], of the C++ committee working
16paper N2798.
17See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2798.pdf.
18
19time2_demo contained this comment:
20
21 Much thanks to Andrei Alexandrescu,
22 Walter Brown,
23 Peter Dimov,
24 Jeff Garland,
25 Terry Golubiewski,
26 Daniel Krugler,
27 Anthony Williams.
28*/
29
30// The way overflow is managed for ratio_less is taken from llvm/libcxx/include/ratio
31
32#ifndef BOOST_RATIO_DETAIL_RATIO_OPERATIONS_HPP
33#define BOOST_RATIO_DETAIL_RATIO_OPERATIONS_HPP
34
35#include <boost/ratio/config.hpp>
36#include <boost/ratio/detail/mpl/abs.hpp>
37#include <boost/ratio/detail/mpl/sign.hpp>
38#include <cstdlib>
39#include <climits>
40#include <limits>
41#include <boost/cstdint.hpp>
42#include <boost/type_traits/integral_constant.hpp>
43#include <boost/core/enable_if.hpp>
44#include <boost/integer_traits.hpp>
45
46//
47// We simply cannot include this header on gcc without getting copious warnings of the kind:
48//
49// boost/integer.hpp:77:30: warning: use of C99 long long integer constant
50//
51// And yet there is no other reasonable implementation, so we declare this a system header
52// to suppress these warnings.
53//
54#if defined(__GNUC__) && (__GNUC__ >= 4)
55#pragma GCC system_header
56#endif
57
58namespace boost
59{
60
61//----------------------------------------------------------------------------//
62// helpers //
63//----------------------------------------------------------------------------//
64
65namespace ratio_detail
66{
67
68 template <boost::intmax_t X, boost::intmax_t Y, boost::intmax_t = mpl::sign_c<boost::intmax_t, Y>::value>
69 class br_add;
70
71 template <boost::intmax_t X, boost::intmax_t Y>
72 class br_add<X, Y, 1>
73 {
74 static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
75 static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
76
77 BOOST_RATIO_STATIC_ASSERT(X <= max - Y , BOOST_RATIO_OVERFLOW_IN_ADD, ());
78 public:
79 static const boost::intmax_t value = X + Y;
80 };
81
82 template <boost::intmax_t X, boost::intmax_t Y>
83 class br_add<X, Y, 0>
84 {
85 public:
86 static const boost::intmax_t value = X;
87 };
88
89 template <boost::intmax_t X, boost::intmax_t Y>
90 class br_add<X, Y, -1>
91 {
92 static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
93 static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
94
95 BOOST_RATIO_STATIC_ASSERT(min - Y <= X, BOOST_RATIO_OVERFLOW_IN_ADD, ());
96 public:
97 static const boost::intmax_t value = X + Y;
98 };
99
100 template <boost::intmax_t X, boost::intmax_t Y, boost::intmax_t = mpl::sign_c<boost::intmax_t, Y>::value>
101 class br_sub;
102
103 template <boost::intmax_t X, boost::intmax_t Y>
104 class br_sub<X, Y, 1>
105 {
106 static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
107 static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
108
109 BOOST_RATIO_STATIC_ASSERT(min + Y <= X, BOOST_RATIO_OVERFLOW_IN_SUB, ());
110 public:
111 static const boost::intmax_t value = X - Y;
112 };
113
114 template <boost::intmax_t X, boost::intmax_t Y>
115 class br_sub<X, Y, 0>
116 {
117 public:
118 static const boost::intmax_t value = X;
119 };
120
121 template <boost::intmax_t X, boost::intmax_t Y>
122 class br_sub<X, Y, -1>
123 {
124 static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
125 static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
126
127 BOOST_RATIO_STATIC_ASSERT(X <= max + Y, BOOST_RATIO_OVERFLOW_IN_SUB, ());
128 public:
129 static const boost::intmax_t value = X - Y;
130 };
131
132 template <boost::intmax_t X, boost::intmax_t Y>
133 class br_mul
134 {
135 static const boost::intmax_t nan =
136 boost::intmax_t(BOOST_RATIO_UINTMAX_C(1) << (sizeof(boost::intmax_t) * CHAR_BIT - 1));
137 static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
138 static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
139
140 static const boost::intmax_t a_x = mpl::abs_c<boost::intmax_t, X>::value;
141 static const boost::intmax_t a_y = mpl::abs_c<boost::intmax_t, Y>::value;
142
143 BOOST_RATIO_STATIC_ASSERT(X != nan, BOOST_RATIO_OVERFLOW_IN_MUL, ());
144 BOOST_RATIO_STATIC_ASSERT(Y != nan, BOOST_RATIO_OVERFLOW_IN_MUL, ());
145 BOOST_RATIO_STATIC_ASSERT(a_x <= max / a_y, BOOST_RATIO_OVERFLOW_IN_MUL, ());
146 public:
147 static const boost::intmax_t value = X * Y;
148 };
149
150 template <boost::intmax_t Y>
151 class br_mul<0, Y>
152 {
153 public:
154 static const boost::intmax_t value = 0;
155 };
156
157 template <boost::intmax_t X>
158 class br_mul<X, 0>
159 {
160 public:
161 static const boost::intmax_t value = 0;
162 };
163
164 template <>
165 class br_mul<0, 0>
166 {
167 public:
168 static const boost::intmax_t value = 0;
169 };
170
171 // Not actually used but left here in case needed in future maintenance
172 template <boost::intmax_t X, boost::intmax_t Y>
173 class br_div
174 {
175 static const boost::intmax_t nan = boost::intmax_t(BOOST_RATIO_UINTMAX_C(1) << (sizeof(boost::intmax_t) * CHAR_BIT - 1));
176 static const boost::intmax_t min = boost::integer_traits<boost::intmax_t>::const_min;
177 static const boost::intmax_t max = boost::integer_traits<boost::intmax_t>::const_max;
178
179 BOOST_RATIO_STATIC_ASSERT(X != nan, BOOST_RATIO_OVERFLOW_IN_DIV, ());
180 BOOST_RATIO_STATIC_ASSERT(Y != nan, BOOST_RATIO_OVERFLOW_IN_DIV, ());
181 BOOST_RATIO_STATIC_ASSERT(Y != 0, BOOST_RATIO_DIVIDE_BY_0, ());
182 public:
183 static const boost::intmax_t value = X / Y;
184 };
185
186 // ratio arithmetic
187 template <class R1, class R2> struct ratio_add;
188 template <class R1, class R2> struct ratio_subtract;
189 template <class R1, class R2> struct ratio_multiply;
190 template <class R1, class R2> struct ratio_divide;
191
192 template <class R1, class R2>
193 struct ratio_add
194 {
195 //The nested typedef type shall be a synonym for ratio<T1, T2>::type where T1 has the value R1::num *
196 //R2::den + R2::num * R1::den and T2 has the value R1::den * R2::den.
197 // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
198 private:
199 static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
200 static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
201 public:
202 // No need to normalize as ratio_multiply is already normalized
203 typedef typename ratio_multiply
204 <
205 ratio<gcd_n1_n2, R1::den / gcd_d1_d2>,
206 ratio
207 <
208 boost::ratio_detail::br_add
209 <
210 boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value,
211 boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value
212 >::value,
213 R2::den
214 >
215 >::type type;
216 };
217 template <class R, boost::intmax_t D>
218 struct ratio_add<R, ratio<0,D> >
219 {
220 typedef R type;
221 };
222
223 template <class R1, class R2>
224 struct ratio_subtract
225 {
226 //The nested typedef type shall be a synonym for ratio<T1, T2>::type where T1 has the value
227 // R1::num *R2::den - R2::num * R1::den and T2 has the value R1::den * R2::den.
228 // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
229 private:
230 static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
231 static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
232 public:
233 // No need to normalize as ratio_multiply is already normalized
234 typedef typename ratio_multiply
235 <
236 ratio<gcd_n1_n2, R1::den / gcd_d1_d2>,
237 ratio
238 <
239 boost::ratio_detail::br_sub
240 <
241 boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value,
242 boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value
243 >::value,
244 R2::den
245 >
246 >::type type;
247 };
248
249 template <class R, boost::intmax_t D>
250 struct ratio_subtract<R, ratio<0,D> >
251 {
252 typedef R type;
253 };
254
255 template <class R1, class R2>
256 struct ratio_multiply
257 {
258 // The nested typedef type shall be a synonym for ratio<R1::num * R2::den - R2::num * R1::den, R1::den * R2::den>::type.
259 // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
260 private:
261 static const boost::intmax_t gcd_n1_d2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::den>::value;
262 static const boost::intmax_t gcd_d1_n2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::num>::value;
263 public:
264 typedef typename ratio
265 <
266 boost::ratio_detail::br_mul<R1::num / gcd_n1_d2, R2::num / gcd_d1_n2>::value,
267 boost::ratio_detail::br_mul<R2::den / gcd_n1_d2, R1::den / gcd_d1_n2>::value
268 >::type type;
269 };
270
271 template <class R1, class R2>
272 struct ratio_divide
273 {
274 // The nested typedef type shall be a synonym for ratio<R1::num * R2::den, R2::num * R1::den>::type.
275 // As the preceding doesn't works because of overflow on boost::intmax_t we need something more elaborated.
276 private:
277 static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
278 static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
279 public:
280 typedef typename ratio
281 <
282 boost::ratio_detail::br_mul<R1::num / gcd_n1_n2, R2::den / gcd_d1_d2>::value,
283 boost::ratio_detail::br_mul<R2::num / gcd_n1_n2, R1::den / gcd_d1_d2>::value
284 >::type type;
285 };
286 template <class R1, class R2>
287 struct is_evenly_divisible_by
288 {
289 private:
290 static const boost::intmax_t gcd_n1_n2 = mpl::gcd_c<boost::intmax_t, R1::num, R2::num>::value;
291 static const boost::intmax_t gcd_d1_d2 = mpl::gcd_c<boost::intmax_t, R1::den, R2::den>::value;
292 public:
293 typedef integral_constant<bool,
294 ((R2::num / gcd_n1_n2 ==1) && (R1::den / gcd_d1_d2)==1)
295 > type;
296 };
297
298 template <class T>
299 struct is_ratio : public boost::false_type
300 {};
301 template <boost::intmax_t N, boost::intmax_t D>
302 struct is_ratio<ratio<N, D> > : public boost::true_type
303 {};
304
305 template <class R1, class R2,
306 boost::intmax_t Q1 = R1::num / R1::den, boost::intmax_t M1 = R1::num % R1::den,
307 boost::intmax_t Q2 = R2::num / R2::den, boost::intmax_t M2 = R2::num % R2::den>
308 struct ratio_less1
309 {
310 static const bool value = Q1 < Q2;
311 };
312
313 template <class R1, class R2, boost::intmax_t Q>
314 struct ratio_less1<R1, R2, Q, 0, Q, 0>
315 {
316 static const bool value = false;
317 };
318
319 template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M2>
320 struct ratio_less1<R1, R2, Q, 0, Q, M2>
321 {
322 static const bool value = true;
323 };
324
325 template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M1>
326 struct ratio_less1<R1, R2, Q, M1, Q, 0>
327 {
328 static const bool value = false;
329 };
330
331 template <class R1, class R2, boost::intmax_t Q, boost::intmax_t M1, boost::intmax_t M2>
332 struct ratio_less1<R1, R2, Q, M1, Q, M2>
333 {
334 static const bool value = ratio_less1<ratio<R2::den, M2>, ratio<R1::den, M1>
335 >::value;
336 };
337
338 template <
339 class R1,
340 class R2,
341 boost::intmax_t S1 = mpl::sign_c<boost::intmax_t, R1::num>::value,
342 boost::intmax_t S2 = mpl::sign_c<boost::intmax_t, R2::num>::value
343>
344 struct ratio_less
345 {
346 static const bool value = S1 < S2;
347 };
348
349 template <class R1, class R2>
350 struct ratio_less<R1, R2, 1LL, 1LL>
351 {
352 static const bool value = ratio_less1<R1, R2>::value;
353 };
354
355 template <class R1, class R2>
356 struct ratio_less<R1, R2, -1LL, -1LL>
357 {
358 static const bool value = ratio_less1<ratio<-R2::num, R2::den>,
359 ratio<-R1::num, R1::den> >::value;
360 };
361
362
363} // namespace ratio_detail
364
365} // namespace boost
366
367#endif // BOOST_RATIO_HPP
368