1// ratio -*- C++ -*-
2
3// Copyright (C) 2008-2018 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file include/ratio
26 * This is a Standard C++ Library header.
27 */
28
29#ifndef _GLIBCXX_RATIO
30#define _GLIBCXX_RATIO 1
31
32#pragma GCC system_header
33
34#if __cplusplus < 201103L
35# include <bits/c++0x_warning.h>
36#else
37
38#include <type_traits>
39#include <cstdint>
40
41#ifdef _GLIBCXX_USE_C99_STDINT_TR1
42
43namespace std _GLIBCXX_VISIBILITY(default)
44{
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
46
47 /**
48 * @defgroup ratio Rational Arithmetic
49 * @ingroup utilities
50 *
51 * Compile time representation of finite rational numbers.
52 * @{
53 */
54
55 template<intmax_t _Pn>
56 struct __static_sign
57 : integral_constant<intmax_t, (_Pn < 0) ? -1 : 1>
58 { };
59
60 template<intmax_t _Pn>
61 struct __static_abs
62 : integral_constant<intmax_t, _Pn * __static_sign<_Pn>::value>
63 { };
64
65 template<intmax_t _Pn, intmax_t _Qn>
66 struct __static_gcd
67 : __static_gcd<_Qn, (_Pn % _Qn)>
68 { };
69
70 template<intmax_t _Pn>
71 struct __static_gcd<_Pn, 0>
72 : integral_constant<intmax_t, __static_abs<_Pn>::value>
73 { };
74
75 template<intmax_t _Qn>
76 struct __static_gcd<0, _Qn>
77 : integral_constant<intmax_t, __static_abs<_Qn>::value>
78 { };
79
80 // Let c = 2^(half # of bits in an intmax_t)
81 // then we find a1, a0, b1, b0 s.t. N = a1*c + a0, M = b1*c + b0
82 // The multiplication of N and M becomes,
83 // N * M = (a1 * b1)c^2 + (a0 * b1 + b0 * a1)c + a0 * b0
84 // Multiplication is safe if each term and the sum of the terms
85 // is representable by intmax_t.
86 template<intmax_t _Pn, intmax_t _Qn>
87 struct __safe_multiply
88 {
89 private:
90 static const uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4);
91
92 static const uintmax_t __a0 = __static_abs<_Pn>::value % __c;
93 static const uintmax_t __a1 = __static_abs<_Pn>::value / __c;
94 static const uintmax_t __b0 = __static_abs<_Qn>::value % __c;
95 static const uintmax_t __b1 = __static_abs<_Qn>::value / __c;
96
97 static_assert(__a1 == 0 || __b1 == 0,
98 "overflow in multiplication");
99 static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1),
100 "overflow in multiplication");
101 static_assert(__b0 * __a0 <= __INTMAX_MAX__,
102 "overflow in multiplication");
103 static_assert((__a0 * __b1 + __b0 * __a1) * __c
104 <= __INTMAX_MAX__ - __b0 * __a0,
105 "overflow in multiplication");
106
107 public:
108 static const intmax_t value = _Pn * _Qn;
109 };
110
111 // Some double-precision utilities, where numbers are represented as
112 // __hi*2^(8*sizeof(uintmax_t)) + __lo.
113 template<uintmax_t __hi1, uintmax_t __lo1, uintmax_t __hi2, uintmax_t __lo2>
114 struct __big_less
115 : integral_constant<bool, (__hi1 < __hi2
116 || (__hi1 == __hi2 && __lo1 < __lo2))>
117 { };
118
119 template<uintmax_t __hi1, uintmax_t __lo1, uintmax_t __hi2, uintmax_t __lo2>
120 struct __big_add
121 {
122 static constexpr uintmax_t __lo = __lo1 + __lo2;
123 static constexpr uintmax_t __hi = (__hi1 + __hi2 +
124 (__lo1 + __lo2 < __lo1)); // carry
125 };
126
127 // Subtract a number from a bigger one.
128 template<uintmax_t __hi1, uintmax_t __lo1, uintmax_t __hi2, uintmax_t __lo2>
129 struct __big_sub
130 {
131 static_assert(!__big_less<__hi1, __lo1, __hi2, __lo2>::value,
132 "Internal library error");
133 static constexpr uintmax_t __lo = __lo1 - __lo2;
134 static constexpr uintmax_t __hi = (__hi1 - __hi2 -
135 (__lo1 < __lo2)); // carry
136 };
137
138 // Same principle as __safe_multiply.
139 template<uintmax_t __x, uintmax_t __y>
140 struct __big_mul
141 {
142 private:
143 static constexpr uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4);
144 static constexpr uintmax_t __x0 = __x % __c;
145 static constexpr uintmax_t __x1 = __x / __c;
146 static constexpr uintmax_t __y0 = __y % __c;
147 static constexpr uintmax_t __y1 = __y / __c;
148 static constexpr uintmax_t __x0y0 = __x0 * __y0;
149 static constexpr uintmax_t __x0y1 = __x0 * __y1;
150 static constexpr uintmax_t __x1y0 = __x1 * __y0;
151 static constexpr uintmax_t __x1y1 = __x1 * __y1;
152 static constexpr uintmax_t __mix = __x0y1 + __x1y0; // possible carry...
153 static constexpr uintmax_t __mix_lo = __mix * __c;
154 static constexpr uintmax_t __mix_hi
155 = __mix / __c + ((__mix < __x0y1) ? __c : 0); // ... added here
156 typedef __big_add<__mix_hi, __mix_lo, __x1y1, __x0y0> _Res;
157 public:
158 static constexpr uintmax_t __hi = _Res::__hi;
159 static constexpr uintmax_t __lo = _Res::__lo;
160 };
161
162 // Adapted from __udiv_qrnnd_c in longlong.h
163 // This version assumes that the high bit of __d is 1.
164 template<uintmax_t __n1, uintmax_t __n0, uintmax_t __d>
165 struct __big_div_impl
166 {
167 private:
168 static_assert(__d >= (uintmax_t(1) << (sizeof(intmax_t) * 8 - 1)),
169 "Internal library error");
170 static_assert(__n1 < __d, "Internal library error");
171 static constexpr uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4);
172 static constexpr uintmax_t __d1 = __d / __c;
173 static constexpr uintmax_t __d0 = __d % __c;
174
175 static constexpr uintmax_t __q1x = __n1 / __d1;
176 static constexpr uintmax_t __r1x = __n1 % __d1;
177 static constexpr uintmax_t __m = __q1x * __d0;
178 static constexpr uintmax_t __r1y = __r1x * __c + __n0 / __c;
179 static constexpr uintmax_t __r1z = __r1y + __d;
180 static constexpr uintmax_t __r1
181 = ((__r1y < __m) ? ((__r1z >= __d) && (__r1z < __m))
182 ? (__r1z + __d) : __r1z : __r1y) - __m;
183 static constexpr uintmax_t __q1
184 = __q1x - ((__r1y < __m)
185 ? ((__r1z >= __d) && (__r1z < __m)) ? 2 : 1 : 0);
186 static constexpr uintmax_t __q0x = __r1 / __d1;
187 static constexpr uintmax_t __r0x = __r1 % __d1;
188 static constexpr uintmax_t __n = __q0x * __d0;
189 static constexpr uintmax_t __r0y = __r0x * __c + __n0 % __c;
190 static constexpr uintmax_t __r0z = __r0y + __d;
191 static constexpr uintmax_t __r0
192 = ((__r0y < __n) ? ((__r0z >= __d) && (__r0z < __n))
193 ? (__r0z + __d) : __r0z : __r0y) - __n;
194 static constexpr uintmax_t __q0
195 = __q0x - ((__r0y < __n) ? ((__r0z >= __d)
196 && (__r0z < __n)) ? 2 : 1 : 0);
197
198 public:
199 static constexpr uintmax_t __quot = __q1 * __c + __q0;
200 static constexpr uintmax_t __rem = __r0;
201
202 private:
203 typedef __big_mul<__quot, __d> _Prod;
204 typedef __big_add<_Prod::__hi, _Prod::__lo, 0, __rem> _Sum;
205 static_assert(_Sum::__hi == __n1 && _Sum::__lo == __n0,
206 "Internal library error");
207 };
208
209 template<uintmax_t __n1, uintmax_t __n0, uintmax_t __d>
210 struct __big_div
211 {
212 private:
213 static_assert(__d != 0, "Internal library error");
214 static_assert(sizeof (uintmax_t) == sizeof (unsigned long long),
215 "This library calls __builtin_clzll on uintmax_t, which "
216 "is unsafe on your platform. Please complain to "
217 "http://gcc.gnu.org/bugzilla/");
218 static constexpr int __shift = __builtin_clzll(__d);
219 static constexpr int __coshift_ = sizeof(uintmax_t) * 8 - __shift;
220 static constexpr int __coshift = (__shift != 0) ? __coshift_ : 0;
221 static constexpr uintmax_t __c1 = uintmax_t(1) << __shift;
222 static constexpr uintmax_t __c2 = uintmax_t(1) << __coshift;
223 static constexpr uintmax_t __new_d = __d * __c1;
224 static constexpr uintmax_t __new_n0 = __n0 * __c1;
225 static constexpr uintmax_t __n1_shifted = (__n1 % __d) * __c1;
226 static constexpr uintmax_t __n0_top = (__shift != 0) ? (__n0 / __c2) : 0;
227 static constexpr uintmax_t __new_n1 = __n1_shifted + __n0_top;
228 typedef __big_div_impl<__new_n1, __new_n0, __new_d> _Res;
229
230 public:
231 static constexpr uintmax_t __quot_hi = __n1 / __d;
232 static constexpr uintmax_t __quot_lo = _Res::__quot;
233 static constexpr uintmax_t __rem = _Res::__rem / __c1;
234
235 private:
236 typedef __big_mul<__quot_lo, __d> _P0;
237 typedef __big_mul<__quot_hi, __d> _P1;
238 typedef __big_add<_P0::__hi, _P0::__lo, _P1::__lo, __rem> _Sum;
239 // No overflow.
240 static_assert(_P1::__hi == 0, "Internal library error");
241 static_assert(_Sum::__hi >= _P0::__hi, "Internal library error");
242 // Matches the input data.
243 static_assert(_Sum::__hi == __n1 && _Sum::__lo == __n0,
244 "Internal library error");
245 static_assert(__rem < __d, "Internal library error");
246 };
247
248 /**
249 * @brief Provides compile-time rational arithmetic.
250 *
251 * This class template represents any finite rational number with a
252 * numerator and denominator representable by compile-time constants of
253 * type intmax_t. The ratio is simplified when instantiated.
254 *
255 * For example:
256 * @code
257 * std::ratio<7,-21>::num == -1;
258 * std::ratio<7,-21>::den == 3;
259 * @endcode
260 *
261 */
262 template<intmax_t _Num, intmax_t _Den = 1>
263 struct ratio
264 {
265 static_assert(_Den != 0, "denominator cannot be zero");
266 static_assert(_Num >= -__INTMAX_MAX__ && _Den >= -__INTMAX_MAX__,
267 "out of range");
268
269 // Note: sign(N) * abs(N) == N
270 static constexpr intmax_t num =
271 _Num * __static_sign<_Den>::value / __static_gcd<_Num, _Den>::value;
272
273 static constexpr intmax_t den =
274 __static_abs<_Den>::value / __static_gcd<_Num, _Den>::value;
275
276 typedef ratio<num, den> type;
277 };
278
279 template<intmax_t _Num, intmax_t _Den>
280 constexpr intmax_t ratio<_Num, _Den>::num;
281
282 template<intmax_t _Num, intmax_t _Den>
283 constexpr intmax_t ratio<_Num, _Den>::den;
284
285 template<typename _R1, typename _R2>
286 struct __ratio_multiply
287 {
288 private:
289 static const intmax_t __gcd1 =
290 __static_gcd<_R1::num, _R2::den>::value;
291 static const intmax_t __gcd2 =
292 __static_gcd<_R2::num, _R1::den>::value;
293
294 public:
295 typedef ratio<
296 __safe_multiply<(_R1::num / __gcd1),
297 (_R2::num / __gcd2)>::value,
298 __safe_multiply<(_R1::den / __gcd2),
299 (_R2::den / __gcd1)>::value> type;
300
301 static constexpr intmax_t num = type::num;
302 static constexpr intmax_t den = type::den;
303 };
304
305 template<typename _R1, typename _R2>
306 constexpr intmax_t __ratio_multiply<_R1, _R2>::num;
307
308 template<typename _R1, typename _R2>
309 constexpr intmax_t __ratio_multiply<_R1, _R2>::den;
310
311 /// ratio_multiply
312 template<typename _R1, typename _R2>
313 using ratio_multiply = typename __ratio_multiply<_R1, _R2>::type;
314
315 template<typename _R1, typename _R2>
316 struct __ratio_divide
317 {
318 static_assert(_R2::num != 0, "division by 0");
319
320 typedef typename __ratio_multiply<
321 _R1,
322 ratio<_R2::den, _R2::num>>::type type;
323
324 static constexpr intmax_t num = type::num;
325 static constexpr intmax_t den = type::den;
326 };
327
328 template<typename _R1, typename _R2>
329 constexpr intmax_t __ratio_divide<_R1, _R2>::num;
330
331 template<typename _R1, typename _R2>
332 constexpr intmax_t __ratio_divide<_R1, _R2>::den;
333
334 /// ratio_divide
335 template<typename _R1, typename _R2>
336 using ratio_divide = typename __ratio_divide<_R1, _R2>::type;
337
338 /// ratio_equal
339 template<typename _R1, typename _R2>
340 struct ratio_equal
341 : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den>
342 { };
343
344 /// ratio_not_equal
345 template<typename _R1, typename _R2>
346 struct ratio_not_equal
347 : integral_constant<bool, !ratio_equal<_R1, _R2>::value>
348 { };
349
350 // Both numbers are positive.
351 template<typename _R1, typename _R2,
352 typename _Left = __big_mul<_R1::num,_R2::den>,
353 typename _Right = __big_mul<_R2::num,_R1::den> >
354 struct __ratio_less_impl_1
355 : integral_constant<bool, __big_less<_Left::__hi, _Left::__lo,
356 _Right::__hi, _Right::__lo>::value>
357 { };
358
359 template<typename _R1, typename _R2,
360 bool = (_R1::num == 0 || _R2::num == 0
361 || (__static_sign<_R1::num>::value
362 != __static_sign<_R2::num>::value)),
363 bool = (__static_sign<_R1::num>::value == -1
364 && __static_sign<_R2::num>::value == -1)>
365 struct __ratio_less_impl
366 : __ratio_less_impl_1<_R1, _R2>::type
367 { };
368
369 template<typename _R1, typename _R2>
370 struct __ratio_less_impl<_R1, _R2, true, false>
371 : integral_constant<bool, _R1::num < _R2::num>
372 { };
373
374 template<typename _R1, typename _R2>
375 struct __ratio_less_impl<_R1, _R2, false, true>
376 : __ratio_less_impl_1<ratio<-_R2::num, _R2::den>,
377 ratio<-_R1::num, _R1::den> >::type
378 { };
379
380 /// ratio_less
381 template<typename _R1, typename _R2>
382 struct ratio_less
383 : __ratio_less_impl<_R1, _R2>::type
384 { };
385
386 /// ratio_less_equal
387 template<typename _R1, typename _R2>
388 struct ratio_less_equal
389 : integral_constant<bool, !ratio_less<_R2, _R1>::value>
390 { };
391
392 /// ratio_greater
393 template<typename _R1, typename _R2>
394 struct ratio_greater
395 : integral_constant<bool, ratio_less<_R2, _R1>::value>
396 { };
397
398 /// ratio_greater_equal
399 template<typename _R1, typename _R2>
400 struct ratio_greater_equal
401 : integral_constant<bool, !ratio_less<_R1, _R2>::value>
402 { };
403
404#if __cplusplus > 201402L
405 template <typename _R1, typename _R2>
406 inline constexpr bool ratio_equal_v = ratio_equal<_R1, _R2>::value;
407 template <typename _R1, typename _R2>
408 inline constexpr bool ratio_not_equal_v = ratio_not_equal<_R1, _R2>::value;
409 template <typename _R1, typename _R2>
410 inline constexpr bool ratio_less_v = ratio_less<_R1, _R2>::value;
411 template <typename _R1, typename _R2>
412 inline constexpr bool ratio_less_equal_v =
413 ratio_less_equal<_R1, _R2>::value;
414 template <typename _R1, typename _R2>
415 inline constexpr bool ratio_greater_v = ratio_greater<_R1, _R2>::value;
416 template <typename _R1, typename _R2>
417 inline constexpr bool ratio_greater_equal_v
418 = ratio_greater_equal<_R1, _R2>::value;
419#endif // C++17
420
421 template<typename _R1, typename _R2,
422 bool = (_R1::num >= 0),
423 bool = (_R2::num >= 0),
424 bool = ratio_less<ratio<__static_abs<_R1::num>::value, _R1::den>,
425 ratio<__static_abs<_R2::num>::value, _R2::den> >::value>
426 struct __ratio_add_impl
427 {
428 private:
429 typedef typename __ratio_add_impl<
430 ratio<-_R1::num, _R1::den>,
431 ratio<-_R2::num, _R2::den> >::type __t;
432 public:
433 typedef ratio<-__t::num, __t::den> type;
434 };
435
436 // True addition of nonnegative numbers.
437 template<typename _R1, typename _R2, bool __b>
438 struct __ratio_add_impl<_R1, _R2, true, true, __b>
439 {
440 private:
441 static constexpr uintmax_t __g = __static_gcd<_R1::den, _R2::den>::value;
442 static constexpr uintmax_t __d2 = _R2::den / __g;
443 typedef __big_mul<_R1::den, __d2> __d;
444 typedef __big_mul<_R1::num, _R2::den / __g> __x;
445 typedef __big_mul<_R2::num, _R1::den / __g> __y;
446 typedef __big_add<__x::__hi, __x::__lo, __y::__hi, __y::__lo> __n;
447 static_assert(__n::__hi >= __x::__hi, "Internal library error");
448 typedef __big_div<__n::__hi, __n::__lo, __g> __ng;
449 static constexpr uintmax_t __g2 = __static_gcd<__ng::__rem, __g>::value;
450 typedef __big_div<__n::__hi, __n::__lo, __g2> __n_final;
451 static_assert(__n_final::__rem == 0, "Internal library error");
452 static_assert(__n_final::__quot_hi == 0 &&
453 __n_final::__quot_lo <= __INTMAX_MAX__, "overflow in addition");
454 typedef __big_mul<_R1::den / __g2, __d2> __d_final;
455 static_assert(__d_final::__hi == 0 &&
456 __d_final::__lo <= __INTMAX_MAX__, "overflow in addition");
457 public:
458 typedef ratio<__n_final::__quot_lo, __d_final::__lo> type;
459 };
460
461 template<typename _R1, typename _R2>
462 struct __ratio_add_impl<_R1, _R2, false, true, true>
463 : __ratio_add_impl<_R2, _R1>
464 { };
465
466 // True subtraction of nonnegative numbers yielding a nonnegative result.
467 template<typename _R1, typename _R2>
468 struct __ratio_add_impl<_R1, _R2, true, false, false>
469 {
470 private:
471 static constexpr uintmax_t __g = __static_gcd<_R1::den, _R2::den>::value;
472 static constexpr uintmax_t __d2 = _R2::den / __g;
473 typedef __big_mul<_R1::den, __d2> __d;
474 typedef __big_mul<_R1::num, _R2::den / __g> __x;
475 typedef __big_mul<-_R2::num, _R1::den / __g> __y;
476 typedef __big_sub<__x::__hi, __x::__lo, __y::__hi, __y::__lo> __n;
477 typedef __big_div<__n::__hi, __n::__lo, __g> __ng;
478 static constexpr uintmax_t __g2 = __static_gcd<__ng::__rem, __g>::value;
479 typedef __big_div<__n::__hi, __n::__lo, __g2> __n_final;
480 static_assert(__n_final::__rem == 0, "Internal library error");
481 static_assert(__n_final::__quot_hi == 0 &&
482 __n_final::__quot_lo <= __INTMAX_MAX__, "overflow in addition");
483 typedef __big_mul<_R1::den / __g2, __d2> __d_final;
484 static_assert(__d_final::__hi == 0 &&
485 __d_final::__lo <= __INTMAX_MAX__, "overflow in addition");
486 public:
487 typedef ratio<__n_final::__quot_lo, __d_final::__lo> type;
488 };
489
490 template<typename _R1, typename _R2>
491 struct __ratio_add
492 {
493 typedef typename __ratio_add_impl<_R1, _R2>::type type;
494 static constexpr intmax_t num = type::num;
495 static constexpr intmax_t den = type::den;
496 };
497
498 template<typename _R1, typename _R2>
499 constexpr intmax_t __ratio_add<_R1, _R2>::num;
500
501 template<typename _R1, typename _R2>
502 constexpr intmax_t __ratio_add<_R1, _R2>::den;
503
504 /// ratio_add
505 template<typename _R1, typename _R2>
506 using ratio_add = typename __ratio_add<_R1, _R2>::type;
507
508 template<typename _R1, typename _R2>
509 struct __ratio_subtract
510 {
511 typedef typename __ratio_add<
512 _R1,
513 ratio<-_R2::num, _R2::den>>::type type;
514
515 static constexpr intmax_t num = type::num;
516 static constexpr intmax_t den = type::den;
517 };
518
519 template<typename _R1, typename _R2>
520 constexpr intmax_t __ratio_subtract<_R1, _R2>::num;
521
522 template<typename _R1, typename _R2>
523 constexpr intmax_t __ratio_subtract<_R1, _R2>::den;
524
525 /// ratio_subtract
526 template<typename _R1, typename _R2>
527 using ratio_subtract = typename __ratio_subtract<_R1, _R2>::type;
528
529
530 typedef ratio<1, 1000000000000000000> atto;
531 typedef ratio<1, 1000000000000000> femto;
532 typedef ratio<1, 1000000000000> pico;
533 typedef ratio<1, 1000000000> nano;
534 typedef ratio<1, 1000000> micro;
535 typedef ratio<1, 1000> milli;
536 typedef ratio<1, 100> centi;
537 typedef ratio<1, 10> deci;
538 typedef ratio< 10, 1> deca;
539 typedef ratio< 100, 1> hecto;
540 typedef ratio< 1000, 1> kilo;
541 typedef ratio< 1000000, 1> mega;
542 typedef ratio< 1000000000, 1> giga;
543 typedef ratio< 1000000000000, 1> tera;
544 typedef ratio< 1000000000000000, 1> peta;
545 typedef ratio< 1000000000000000000, 1> exa;
546
547 // @} group ratio
548_GLIBCXX_END_NAMESPACE_VERSION
549} // namespace
550
551#endif //_GLIBCXX_USE_C99_STDINT_TR1
552
553#endif // C++11
554
555#endif //_GLIBCXX_RATIO
556