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