1 // ratio -*- C++ -*- 2 3 // Copyright (C) 2008, 2009, 2010, 2011 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 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 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 43 namespace 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 68 template<intmax_t _Pn, intmax_t _Qn> 69 struct __static_gcd 70 : __static_gcd<_Qn, (_Pn % _Qn)> 71 { }; 72 73 template<intmax_t _Pn> 74 struct __static_gcd<_Pn, 0> 75 : integral_constant<intmax_t, __static_abs<_Pn>::value> 76 { }; 77 78 template<intmax_t _Qn> 79 struct __static_gcd<0, _Qn> 80 : integral_constant<intmax_t, __static_abs<_Qn>::value> 81 { }; 82 83 // Let c = 2^(half # of bits in an intmax_t) 84 // then we find a1, a0, b1, b0 s.t. N = a1*c + a0, M = b1*c + b0 85 // The multiplication of N and M becomes, 86 // N * M = (a1 * b1)c^2 + (a0 * b1 + b0 * a1)c + a0 * b0 87 // Multiplication is safe if each term and the sum of the terms 88 // is representable by intmax_t. 89 template<intmax_t _Pn, intmax_t _Qn> 90 struct __safe_multiply 91 { 92 private: 93 static const uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); 94 95 static const uintmax_t __a0 = __static_abs<_Pn>::value % __c; 96 static const uintmax_t __a1 = __static_abs<_Pn>::value / __c; 97 static const uintmax_t __b0 = __static_abs<_Qn>::value % __c; 98 static const uintmax_t __b1 = __static_abs<_Qn>::value / __c; 99 100 static_assert(__a1 == 0 || __b1 == 0, 101 "overflow in multiplication"); 102 static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1), 103 "overflow in multiplication"); 104 static_assert(__b0 * __a0 <= __INTMAX_MAX__, 105 "overflow in multiplication"); 106 static_assert((__a0 * __b1 + __b0 * __a1) * __c <= 107 __INTMAX_MAX__ - __b0 * __a0, "overflow in multiplication"); 108 109 public: 110 static const intmax_t value = _Pn * _Qn; 111 }; 112 113 // Helpers for __safe_add 114 template<intmax_t _Pn, intmax_t _Qn, bool> 115 struct __add_overflow_check_impl 116 : integral_constant<bool, (_Pn <= __INTMAX_MAX__ - _Qn)> 117 { }; 118 119 template<intmax_t _Pn, intmax_t _Qn> 120 struct __add_overflow_check_impl<_Pn, _Qn, false> 121 : integral_constant<bool, (_Pn >= -__INTMAX_MAX__ - _Qn)> 122 { }; 123 124 template<intmax_t _Pn, intmax_t _Qn> 125 struct __add_overflow_check 126 : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)> 127 { }; 128 129 template<intmax_t _Pn, intmax_t _Qn> 130 struct __safe_add 131 { 132 static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, 133 "overflow in addition"); 134 135 static const intmax_t value = _Pn + _Qn; 136 }; 137 138 /** 139 * @brief Provides compile-time rational arithmetic. 140 * 141 * This class template represents any finite rational number with a 142 * numerator and denominator representable by compile-time constants of 143 * type intmax_t. The ratio is simplified when instantiated. 144 * 145 * For example: 146 * @code 147 * std::ratio<7,-21>::num == -1; 148 * std::ratio<7,-21>::den == 3; 149 * @endcode 150 * 151 */ 152 template<intmax_t _Num, intmax_t _Den = 1> 153 struct ratio 154 { 155 static_assert(_Den != 0, "denominator cannot be zero"); 156 static_assert(_Num >= -__INTMAX_MAX__ && _Den >= -__INTMAX_MAX__, 157 "out of range"); 158 159 // Note: sign(N) * abs(N) == N 160 static constexpr intmax_t num = 161 _Num * __static_sign<_Den>::value / __static_gcd<_Num, _Den>::value; 162 163 static constexpr intmax_t den = 164 __static_abs<_Den>::value / __static_gcd<_Num, _Den>::value; 165 166 typedef ratio<num, den> type; 167 }; 168 169 template<intmax_t _Num, intmax_t _Den> 170 constexpr intmax_t ratio<_Num, _Den>::num; 171 172 template<intmax_t _Num, intmax_t _Den> 173 constexpr intmax_t ratio<_Num, _Den>::den; 174 175 /// ratio_add 176 template<typename _R1, typename _R2> 177 struct ratio_add 178 { 179 private: 180 static constexpr intmax_t __gcd = 181 __static_gcd<_R1::den, _R2::den>::value; 182 static constexpr intmax_t __n = __safe_add< 183 __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, 184 __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value; 185 186 // The new numerator may have common factors with the denominator, 187 // but they have to also be factors of __gcd. 188 static constexpr intmax_t __gcd2 = __static_gcd<__n, __gcd>::value; 189 190 public: 191 typedef ratio<__n / __gcd2, 192 __safe_multiply<_R1::den / __gcd2, _R2::den / __gcd>::value> type; 193 194 static constexpr intmax_t num = type::num; 195 static constexpr intmax_t den = type::den; 196 }; 197 198 template<typename _R1, typename _R2> 199 constexpr intmax_t ratio_add<_R1, _R2>::num; 200 201 template<typename _R1, typename _R2> 202 constexpr intmax_t ratio_add<_R1, _R2>::den; 203 204 /// ratio_subtract 205 template<typename _R1, typename _R2> 206 struct ratio_subtract 207 { 208 typedef typename ratio_add< 209 _R1, 210 ratio<-_R2::num, _R2::den>>::type type; 211 212 static constexpr intmax_t num = type::num; 213 static constexpr intmax_t den = type::den; 214 }; 215 216 template<typename _R1, typename _R2> 217 constexpr intmax_t ratio_subtract<_R1, _R2>::num; 218 219 template<typename _R1, typename _R2> 220 constexpr intmax_t ratio_subtract<_R1, _R2>::den; 221 222 /// ratio_multiply 223 template<typename _R1, typename _R2> 224 struct ratio_multiply 225 { 226 private: 227 static const intmax_t __gcd1 = 228 __static_gcd<_R1::num, _R2::den>::value; 229 static const intmax_t __gcd2 = 230 __static_gcd<_R2::num, _R1::den>::value; 231 232 public: 233 typedef ratio< 234 __safe_multiply<(_R1::num / __gcd1), 235 (_R2::num / __gcd2)>::value, 236 __safe_multiply<(_R1::den / __gcd2), 237 (_R2::den / __gcd1)>::value> type; 238 239 static constexpr intmax_t num = type::num; 240 static constexpr intmax_t den = type::den; 241 }; 242 243 template<typename _R1, typename _R2> 244 constexpr intmax_t ratio_multiply<_R1, _R2>::num; 245 246 template<typename _R1, typename _R2> 247 constexpr intmax_t ratio_multiply<_R1, _R2>::den; 248 249 /// ratio_divide 250 template<typename _R1, typename _R2> 251 struct ratio_divide 252 { 253 static_assert(_R2::num != 0, "division by 0"); 254 255 typedef typename ratio_multiply< 256 _R1, 257 ratio<_R2::den, _R2::num>>::type type; 258 259 static constexpr intmax_t num = type::num; 260 static constexpr intmax_t den = type::den; 261 }; 262 263 template<typename _R1, typename _R2> 264 constexpr intmax_t ratio_divide<_R1, _R2>::num; 265 266 template<typename _R1, typename _R2> 267 constexpr intmax_t ratio_divide<_R1, _R2>::den; 268 269 /// ratio_equal 270 template<typename _R1, typename _R2> 271 struct ratio_equal 272 : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den> 273 { }; 274 275 /// ratio_not_equal 276 template<typename _R1, typename _R2> 277 struct ratio_not_equal 278 : integral_constant<bool, !ratio_equal<_R1, _R2>::value> 279 { }; 280 281 // 0 <= _Ri < 1 282 // If one is 0, conclude 283 // Otherwise, x < y iff 1/y < 1/x 284 template<typename _R1, typename _R2> 285 struct __ratio_less_impl_2; 286 287 // _Ri > 0 288 // Compare the integral parts, and remove them if they are equal 289 template<typename _R1, typename _R2, intmax_t __q1 = _R1::num / _R1::den, 290 intmax_t __q2 = _R2::num / _R2::den, bool __eq = (__q1 == __q2)> 291 struct __ratio_less_impl_1 292 : __ratio_less_impl_2<ratio<_R1::num % _R1::den, _R1::den>, 293 ratio<_R2::num % _R2::den, _R2::den> >::type 294 { }; 295 296 template<typename _R1, typename _R2, intmax_t __q1, intmax_t __q2> 297 struct __ratio_less_impl_1<_R1, _R2, __q1, __q2, false> 298 : integral_constant<bool, (__q1 < __q2) > 299 { }; 300 301 template<typename _R1, typename _R2> 302 struct __ratio_less_impl_2 303 : __ratio_less_impl_1<ratio<_R2::den, _R2::num>, 304 ratio<_R1::den, _R1::num> >::type 305 { }; 306 307 template<intmax_t __d1, typename _R2> 308 struct __ratio_less_impl_2<ratio<0, __d1>, _R2> 309 : integral_constant<bool, true> 310 { }; 311 312 template<typename _R1, intmax_t __d2> 313 struct __ratio_less_impl_2<_R1, ratio<0, __d2> > 314 : integral_constant<bool, false> 315 { }; 316 317 template<intmax_t __d1, intmax_t __d2> 318 struct __ratio_less_impl_2<ratio<0, __d1>, ratio<0, __d2> > 319 : integral_constant<bool, false> 320 { }; 321 322 template<typename _R1, typename _R2, 323 bool = (_R1::num == 0 || _R2::num == 0 324 || (__static_sign<_R1::num>::value 325 != __static_sign<_R2::num>::value)), 326 bool = (__static_sign<_R1::num>::value == -1 327 && __static_sign<_R2::num>::value == -1)> 328 struct __ratio_less_impl 329 : __ratio_less_impl_1<_R1, _R2>::type 330 { }; 331 332 template<typename _R1, typename _R2> 333 struct __ratio_less_impl<_R1, _R2, true, false> 334 : integral_constant<bool, _R1::num < _R2::num> 335 { }; 336 337 template<typename _R1, typename _R2> 338 struct __ratio_less_impl<_R1, _R2, false, true> 339 : __ratio_less_impl_1<ratio<-_R2::num, _R2::den>, 340 ratio<-_R1::num, _R1::den> >::type 341 { }; 342 343 /// ratio_less 344 // using a continued fraction expansion 345 template<typename _R1, typename _R2> 346 struct ratio_less 347 : __ratio_less_impl<_R1, _R2>::type 348 { }; 349 350 /// ratio_less_equal 351 template<typename _R1, typename _R2> 352 struct ratio_less_equal 353 : integral_constant<bool, !ratio_less<_R2, _R1>::value> 354 { }; 355 356 /// ratio_greater 357 template<typename _R1, typename _R2> 358 struct ratio_greater 359 : integral_constant<bool, ratio_less<_R2, _R1>::value> 360 { }; 361 362 /// ratio_greater_equal 363 template<typename _R1, typename _R2> 364 struct ratio_greater_equal 365 : integral_constant<bool, !ratio_less<_R1, _R2>::value> 366 { }; 367 368 typedef ratio<1, 1000000000000000000> atto; 369 typedef ratio<1, 1000000000000000> femto; 370 typedef ratio<1, 1000000000000> pico; 371 typedef ratio<1, 1000000000> nano; 372 typedef ratio<1, 1000000> micro; 373 typedef ratio<1, 1000> milli; 374 typedef ratio<1, 100> centi; 375 typedef ratio<1, 10> deci; 376 typedef ratio< 10, 1> deca; 377 typedef ratio< 100, 1> hecto; 378 typedef ratio< 1000, 1> kilo; 379 typedef ratio< 1000000, 1> mega; 380 typedef ratio< 1000000000, 1> giga; 381 typedef ratio< 1000000000000, 1> tera; 382 typedef ratio< 1000000000000000, 1> peta; 383 typedef ratio< 1000000000000000000, 1> exa; 384 385 // @} group ratio 386 _GLIBCXX_END_NAMESPACE_VERSION 387 } // namespace 388 389 #endif //_GLIBCXX_USE_C99_STDINT_TR1 390 391 #endif //__GXX_EXPERIMENTAL_CXX0X__ 392 393 #endif //_GLIBCXX_RATIO 394
