1// ratio -*- C++ -*- 2 3// Copyright (C) 2008, 2009, 2010 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 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 43namespace std 44{ 45 /** 46 * @defgroup ratio Rational Arithmetic 47 * @ingroup utilities 48 * 49 * Compile time representation of finite rational numbers. 50 * @{ 51 */ 52 53 template<intmax_t _Pn> 54 struct __static_sign 55 : integral_constant<intmax_t, (_Pn < 0) ? -1 : 1> 56 { }; 57 58 template<intmax_t _Pn> 59 struct __static_abs 60 : integral_constant<intmax_t, _Pn * __static_sign<_Pn>::value> 61 { }; 62 63 template<intmax_t _Pn, intmax_t _Qn> 64 struct __static_gcd; 65 66 template<intmax_t _Pn, intmax_t _Qn> 67 struct __static_gcd 68 : __static_gcd<_Qn, (_Pn % _Qn)> 69 { }; 70 71 template<intmax_t _Pn> 72 struct __static_gcd<_Pn, 0> 73 : integral_constant<intmax_t, __static_abs<_Pn>::value> 74 { }; 75 76 template<intmax_t _Qn> 77 struct __static_gcd<0, _Qn> 78 : integral_constant<intmax_t, __static_abs<_Qn>::value> 79 { }; 80 81 // Let c = 2^(half # of bits in an intmax_t) 82 // then we find a1, a0, b1, b0 s.t. N = a1*c + a0, M = b1*c + b0 83 // The multiplication of N and M becomes, 84 // N * M = (a1 * b1)c^2 + (a0 * b1 + b0 * a1)c + a0 * b0 85 // Multiplication is safe if each term and the sum of the terms 86 // is representable by intmax_t. 87 template<intmax_t _Pn, intmax_t _Qn> 88 struct __safe_multiply 89 { 90 private: 91 static const uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); 92 93 static const uintmax_t __a0 = __static_abs<_Pn>::value % __c; 94 static const uintmax_t __a1 = __static_abs<_Pn>::value / __c; 95 static const uintmax_t __b0 = __static_abs<_Qn>::value % __c; 96 static const uintmax_t __b1 = __static_abs<_Qn>::value / __c; 97 98 static_assert(__a1 == 0 || __b1 == 0, 99 "overflow in multiplication"); 100 static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1), 101 "overflow in multiplication"); 102 static_assert(__b0 * __a0 <= __INTMAX_MAX__, 103 "overflow in multiplication"); 104 static_assert((__a0 * __b1 + __b0 * __a1) * __c <= 105 __INTMAX_MAX__ - __b0 * __a0, "overflow in multiplication"); 106 107 public: 108 static const intmax_t value = _Pn * _Qn; 109 }; 110 111 // Helpers for __safe_add 112 template<intmax_t _Pn, intmax_t _Qn, bool> 113 struct __add_overflow_check_impl 114 : integral_constant<bool, (_Pn <= __INTMAX_MAX__ - _Qn)> 115 { }; 116 117 template<intmax_t _Pn, intmax_t _Qn> 118 struct __add_overflow_check_impl<_Pn, _Qn, false> 119 : integral_constant<bool, (_Pn >= -__INTMAX_MAX__ - _Qn)> 120 { }; 121 122 template<intmax_t _Pn, intmax_t _Qn> 123 struct __add_overflow_check 124 : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)> 125 { }; 126 127 template<intmax_t _Pn, intmax_t _Qn> 128 struct __safe_add 129 { 130 static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, 131 "overflow in addition"); 132 133 static const intmax_t value = _Pn + _Qn; 134 }; 135 136 /** 137 * @brief Provides compile-time rational arithmetic. 138 * 139 * This class template represents any finite rational number with a 140 * numerator and denominator representable by compile-time constants of 141 * type intmax_t. The ratio is simplified when instantiated. 142 * 143 * For example: 144 * @code 145 * std::ratio<7,-21>::num == -1; 146 * std::ratio<7,-21>::den == 3; 147 * @endcode 148 * 149 */ 150 template<intmax_t _Num, intmax_t _Den = 1> 151 struct ratio 152 { 153 static_assert(_Den != 0, "denominator cannot be zero"); 154 static_assert(_Num >= -__INTMAX_MAX__ && _Den >= -__INTMAX_MAX__, 155 "out of range"); 156 157 // Note: sign(N) * abs(N) == N 158 static const intmax_t num = 159 _Num * __static_sign<_Den>::value / __static_gcd<_Num, _Den>::value; 160 161 static const intmax_t den = 162 __static_abs<_Den>::value / __static_gcd<_Num, _Den>::value; 163 }; 164 165 template<intmax_t _Num, intmax_t _Den> 166 const intmax_t ratio<_Num, _Den>::num; 167 168 template<intmax_t _Num, intmax_t _Den> 169 const intmax_t ratio<_Num, _Den>::den; 170 171 /// ratio_add 172 template<typename _R1, typename _R2> 173 struct ratio_add 174 { 175 private: 176 static const intmax_t __gcd = 177 __static_gcd<_R1::den, _R2::den>::value; 178 179 public: 180 typedef ratio< 181 __safe_add< 182 __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, 183 __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value, 184 __safe_multiply<_R1::den, (_R2::den / __gcd)>::value> type; 185 }; 186 187 /// ratio_subtract 188 template<typename _R1, typename _R2> 189 struct ratio_subtract 190 { 191 typedef typename ratio_add< 192 _R1, 193 ratio<-_R2::num, _R2::den>>::type type; 194 }; 195 196 /// ratio_multiply 197 template<typename _R1, typename _R2> 198 struct ratio_multiply 199 { 200 private: 201 static const intmax_t __gcd1 = 202 __static_gcd<_R1::num, _R2::den>::value; 203 static const intmax_t __gcd2 = 204 __static_gcd<_R2::num, _R1::den>::value; 205 206 public: 207 typedef ratio< 208 __safe_multiply<(_R1::num / __gcd1), 209 (_R2::num / __gcd2)>::value, 210 __safe_multiply<(_R1::den / __gcd2), 211 (_R2::den / __gcd1)>::value> type; 212 }; 213 214 /// ratio_divide 215 template<typename _R1, typename _R2> 216 struct ratio_divide 217 { 218 static_assert(_R2::num != 0, "division by 0"); 219 220 typedef typename ratio_multiply< 221 _R1, 222 ratio<_R2::den, _R2::num>>::type type; 223 }; 224 225 /// ratio_equal 226 template<typename _R1, typename _R2> 227 struct ratio_equal 228 : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den> 229 { }; 230 231 /// ratio_not_equal 232 template<typename _R1, typename _R2> 233 struct ratio_not_equal 234 : integral_constant<bool, !ratio_equal<_R1, _R2>::value> 235 { }; 236 237 template<typename _R1, typename _R2> 238 struct __ratio_less_simple_impl 239 : integral_constant<bool, 240 (__safe_multiply<_R1::num, _R2::den>::value 241 < __safe_multiply<_R2::num, _R1::den>::value)> 242 { }; 243 244 // If the denominators are equal or the signs differ, we can just compare 245 // numerators, otherwise fallback to the simple cross-multiply method. 246 template<typename _R1, typename _R2> 247 struct __ratio_less_impl 248 : conditional<(_R1::den == _R2::den 249 || (__static_sign<_R1::num>::value 250 != __static_sign<_R2::num>::value)), 251 integral_constant<bool, (_R1::num < _R2::num)>, 252 __ratio_less_simple_impl<_R1, _R2>>::type 253 { }; 254 255 /// ratio_less 256 template<typename _R1, typename _R2> 257 struct ratio_less 258 : __ratio_less_impl<_R1, _R2>::type 259 { }; 260 261 /// ratio_less_equal 262 template<typename _R1, typename _R2> 263 struct ratio_less_equal 264 : integral_constant<bool, !ratio_less<_R2, _R1>::value> 265 { }; 266 267 /// ratio_greater 268 template<typename _R1, typename _R2> 269 struct ratio_greater 270 : integral_constant<bool, ratio_less<_R2, _R1>::value> 271 { }; 272 273 /// ratio_greater_equal 274 template<typename _R1, typename _R2> 275 struct ratio_greater_equal 276 : integral_constant<bool, !ratio_less<_R1, _R2>::value> 277 { }; 278 279 typedef ratio<1, 1000000000000000000> atto; 280 typedef ratio<1, 1000000000000000> femto; 281 typedef ratio<1, 1000000000000> pico; 282 typedef ratio<1, 1000000000> nano; 283 typedef ratio<1, 1000000> micro; 284 typedef ratio<1, 1000> milli; 285 typedef ratio<1, 100> centi; 286 typedef ratio<1, 10> deci; 287 typedef ratio< 10, 1> deca; 288 typedef ratio< 100, 1> hecto; 289 typedef ratio< 1000, 1> kilo; 290 typedef ratio< 1000000, 1> mega; 291 typedef ratio< 1000000000, 1> giga; 292 typedef ratio< 1000000000000, 1> tera; 293 typedef ratio< 1000000000000000, 1> peta; 294 typedef ratio< 1000000000000000000, 1> exa; 295 296 // @} group ratio 297} 298 299#endif //_GLIBCXX_USE_C99_STDINT_TR1 300 301#endif //__GXX_EXPERIMENTAL_CXX0X__ 302 303#endif //_GLIBCXX_RATIO 304