libstdc++
|
00001 // ratio -*- C++ -*- 00002 00003 // Copyright (C) 2008, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file include/ratio 00026 * This is a Standard C++ Library header. 00027 */ 00028 00029 #ifndef _GLIBCXX_RATIO 00030 #define _GLIBCXX_RATIO 1 00031 00032 #pragma GCC system_header 00033 00034 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00035 # include <bits/c++0x_warning.h> 00036 #else 00037 00038 #include <type_traits> 00039 #include <cstdint> 00040 00041 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 00042 00043 namespace std _GLIBCXX_VISIBILITY(default) 00044 { 00045 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00046 00047 /** 00048 * @defgroup ratio Rational Arithmetic 00049 * @ingroup utilities 00050 * 00051 * Compile time representation of finite rational numbers. 00052 * @{ 00053 */ 00054 00055 template<intmax_t _Pn> 00056 struct __static_sign 00057 : integral_constant<intmax_t, (_Pn < 0) ? -1 : 1> 00058 { }; 00059 00060 template<intmax_t _Pn> 00061 struct __static_abs 00062 : integral_constant<intmax_t, _Pn * __static_sign<_Pn>::value> 00063 { }; 00064 00065 template<intmax_t _Pn, intmax_t _Qn> 00066 struct __static_gcd; 00067 00068 template<intmax_t _Pn, intmax_t _Qn> 00069 struct __static_gcd 00070 : __static_gcd<_Qn, (_Pn % _Qn)> 00071 { }; 00072 00073 template<intmax_t _Pn> 00074 struct __static_gcd<_Pn, 0> 00075 : integral_constant<intmax_t, __static_abs<_Pn>::value> 00076 { }; 00077 00078 template<intmax_t _Qn> 00079 struct __static_gcd<0, _Qn> 00080 : integral_constant<intmax_t, __static_abs<_Qn>::value> 00081 { }; 00082 00083 // Let c = 2^(half # of bits in an intmax_t) 00084 // then we find a1, a0, b1, b0 s.t. N = a1*c + a0, M = b1*c + b0 00085 // The multiplication of N and M becomes, 00086 // N * M = (a1 * b1)c^2 + (a0 * b1 + b0 * a1)c + a0 * b0 00087 // Multiplication is safe if each term and the sum of the terms 00088 // is representable by intmax_t. 00089 template<intmax_t _Pn, intmax_t _Qn> 00090 struct __safe_multiply 00091 { 00092 private: 00093 static const uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); 00094 00095 static const uintmax_t __a0 = __static_abs<_Pn>::value % __c; 00096 static const uintmax_t __a1 = __static_abs<_Pn>::value / __c; 00097 static const uintmax_t __b0 = __static_abs<_Qn>::value % __c; 00098 static const uintmax_t __b1 = __static_abs<_Qn>::value / __c; 00099 00100 static_assert(__a1 == 0 || __b1 == 0, 00101 "overflow in multiplication"); 00102 static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1), 00103 "overflow in multiplication"); 00104 static_assert(__b0 * __a0 <= __INTMAX_MAX__, 00105 "overflow in multiplication"); 00106 static_assert((__a0 * __b1 + __b0 * __a1) * __c <= 00107 __INTMAX_MAX__ - __b0 * __a0, "overflow in multiplication"); 00108 00109 public: 00110 static const intmax_t value = _Pn * _Qn; 00111 }; 00112 00113 // Helpers for __safe_add 00114 template<intmax_t _Pn, intmax_t _Qn, bool> 00115 struct __add_overflow_check_impl 00116 : integral_constant<bool, (_Pn <= __INTMAX_MAX__ - _Qn)> 00117 { }; 00118 00119 template<intmax_t _Pn, intmax_t _Qn> 00120 struct __add_overflow_check_impl<_Pn, _Qn, false> 00121 : integral_constant<bool, (_Pn >= -__INTMAX_MAX__ - _Qn)> 00122 { }; 00123 00124 template<intmax_t _Pn, intmax_t _Qn> 00125 struct __add_overflow_check 00126 : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)> 00127 { }; 00128 00129 template<intmax_t _Pn, intmax_t _Qn> 00130 struct __safe_add 00131 { 00132 static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, 00133 "overflow in addition"); 00134 00135 static const intmax_t value = _Pn + _Qn; 00136 }; 00137 00138 /** 00139 * @brief Provides compile-time rational arithmetic. 00140 * 00141 * This class template represents any finite rational number with a 00142 * numerator and denominator representable by compile-time constants of 00143 * type intmax_t. The ratio is simplified when instantiated. 00144 * 00145 * For example: 00146 * @code 00147 * std::ratio<7,-21>::num == -1; 00148 * std::ratio<7,-21>::den == 3; 00149 * @endcode 00150 * 00151 */ 00152 template<intmax_t _Num, intmax_t _Den = 1> 00153 struct ratio 00154 { 00155 static_assert(_Den != 0, "denominator cannot be zero"); 00156 static_assert(_Num >= -__INTMAX_MAX__ && _Den >= -__INTMAX_MAX__, 00157 "out of range"); 00158 00159 // Note: sign(N) * abs(N) == N 00160 static constexpr intmax_t num = 00161 _Num * __static_sign<_Den>::value / __static_gcd<_Num, _Den>::value; 00162 00163 static constexpr intmax_t den = 00164 __static_abs<_Den>::value / __static_gcd<_Num, _Den>::value; 00165 00166 typedef ratio<num, den> type; 00167 }; 00168 00169 template<intmax_t _Num, intmax_t _Den> 00170 constexpr intmax_t ratio<_Num, _Den>::num; 00171 00172 template<intmax_t _Num, intmax_t _Den> 00173 constexpr intmax_t ratio<_Num, _Den>::den; 00174 00175 /// ratio_add 00176 template<typename _R1, typename _R2> 00177 struct ratio_add 00178 { 00179 private: 00180 static constexpr intmax_t __gcd = 00181 __static_gcd<_R1::den, _R2::den>::value; 00182 static constexpr intmax_t __n = __safe_add< 00183 __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, 00184 __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value; 00185 00186 // The new numerator may have common factors with the denominator, 00187 // but they have to also be factors of __gcd. 00188 static constexpr intmax_t __gcd2 = __static_gcd<__n, __gcd>::value; 00189 00190 public: 00191 typedef ratio<__n / __gcd2, 00192 __safe_multiply<_R1::den / __gcd2, _R2::den / __gcd>::value> type; 00193 00194 static constexpr intmax_t num = type::num; 00195 static constexpr intmax_t den = type::den; 00196 }; 00197 00198 template<typename _R1, typename _R2> 00199 constexpr intmax_t ratio_add<_R1, _R2>::num; 00200 00201 template<typename _R1, typename _R2> 00202 constexpr intmax_t ratio_add<_R1, _R2>::den; 00203 00204 /// ratio_subtract 00205 template<typename _R1, typename _R2> 00206 struct ratio_subtract 00207 { 00208 typedef typename ratio_add< 00209 _R1, 00210 ratio<-_R2::num, _R2::den>>::type type; 00211 00212 static constexpr intmax_t num = type::num; 00213 static constexpr intmax_t den = type::den; 00214 }; 00215 00216 template<typename _R1, typename _R2> 00217 constexpr intmax_t ratio_subtract<_R1, _R2>::num; 00218 00219 template<typename _R1, typename _R2> 00220 constexpr intmax_t ratio_subtract<_R1, _R2>::den; 00221 00222 /// ratio_multiply 00223 template<typename _R1, typename _R2> 00224 struct ratio_multiply 00225 { 00226 private: 00227 static const intmax_t __gcd1 = 00228 __static_gcd<_R1::num, _R2::den>::value; 00229 static const intmax_t __gcd2 = 00230 __static_gcd<_R2::num, _R1::den>::value; 00231 00232 public: 00233 typedef ratio< 00234 __safe_multiply<(_R1::num / __gcd1), 00235 (_R2::num / __gcd2)>::value, 00236 __safe_multiply<(_R1::den / __gcd2), 00237 (_R2::den / __gcd1)>::value> type; 00238 00239 static constexpr intmax_t num = type::num; 00240 static constexpr intmax_t den = type::den; 00241 }; 00242 00243 template<typename _R1, typename _R2> 00244 constexpr intmax_t ratio_multiply<_R1, _R2>::num; 00245 00246 template<typename _R1, typename _R2> 00247 constexpr intmax_t ratio_multiply<_R1, _R2>::den; 00248 00249 /// ratio_divide 00250 template<typename _R1, typename _R2> 00251 struct ratio_divide 00252 { 00253 static_assert(_R2::num != 0, "division by 0"); 00254 00255 typedef typename ratio_multiply< 00256 _R1, 00257 ratio<_R2::den, _R2::num>>::type type; 00258 00259 static constexpr intmax_t num = type::num; 00260 static constexpr intmax_t den = type::den; 00261 }; 00262 00263 template<typename _R1, typename _R2> 00264 constexpr intmax_t ratio_divide<_R1, _R2>::num; 00265 00266 template<typename _R1, typename _R2> 00267 constexpr intmax_t ratio_divide<_R1, _R2>::den; 00268 00269 /// ratio_equal 00270 template<typename _R1, typename _R2> 00271 struct ratio_equal 00272 : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den> 00273 { }; 00274 00275 /// ratio_not_equal 00276 template<typename _R1, typename _R2> 00277 struct ratio_not_equal 00278 : integral_constant<bool, !ratio_equal<_R1, _R2>::value> 00279 { }; 00280 00281 // 0 <= _Ri < 1 00282 // If one is 0, conclude 00283 // Otherwise, x < y iff 1/y < 1/x 00284 template<typename _R1, typename _R2> 00285 struct __ratio_less_impl_2; 00286 00287 // _Ri > 0 00288 // Compare the integral parts, and remove them if they are equal 00289 template<typename _R1, typename _R2, intmax_t __q1 = _R1::num / _R1::den, 00290 intmax_t __q2 = _R2::num / _R2::den, bool __eq = (__q1 == __q2)> 00291 struct __ratio_less_impl_1 00292 : __ratio_less_impl_2<ratio<_R1::num % _R1::den, _R1::den>, 00293 ratio<_R2::num % _R2::den, _R2::den> >::type 00294 { }; 00295 00296 template<typename _R1, typename _R2, intmax_t __q1, intmax_t __q2> 00297 struct __ratio_less_impl_1<_R1, _R2, __q1, __q2, false> 00298 : integral_constant<bool, (__q1 < __q2) > 00299 { }; 00300 00301 template<typename _R1, typename _R2> 00302 struct __ratio_less_impl_2 00303 : __ratio_less_impl_1<ratio<_R2::den, _R2::num>, 00304 ratio<_R1::den, _R1::num> >::type 00305 { }; 00306 00307 template<intmax_t __d1, typename _R2> 00308 struct __ratio_less_impl_2<ratio<0, __d1>, _R2> 00309 : integral_constant<bool, true> 00310 { }; 00311 00312 template<typename _R1, intmax_t __d2> 00313 struct __ratio_less_impl_2<_R1, ratio<0, __d2> > 00314 : integral_constant<bool, false> 00315 { }; 00316 00317 template<intmax_t __d1, intmax_t __d2> 00318 struct __ratio_less_impl_2<ratio<0, __d1>, ratio<0, __d2> > 00319 : integral_constant<bool, false> 00320 { }; 00321 00322 template<typename _R1, typename _R2, 00323 bool = (_R1::num == 0 || _R2::num == 0 00324 || (__static_sign<_R1::num>::value 00325 != __static_sign<_R2::num>::value)), 00326 bool = (__static_sign<_R1::num>::value == -1 00327 && __static_sign<_R2::num>::value == -1)> 00328 struct __ratio_less_impl 00329 : __ratio_less_impl_1<_R1, _R2>::type 00330 { }; 00331 00332 template<typename _R1, typename _R2> 00333 struct __ratio_less_impl<_R1, _R2, true, false> 00334 : integral_constant<bool, _R1::num < _R2::num> 00335 { }; 00336 00337 template<typename _R1, typename _R2> 00338 struct __ratio_less_impl<_R1, _R2, false, true> 00339 : __ratio_less_impl_1<ratio<-_R2::num, _R2::den>, 00340 ratio<-_R1::num, _R1::den> >::type 00341 { }; 00342 00343 /// ratio_less 00344 // using a continued fraction expansion 00345 template<typename _R1, typename _R2> 00346 struct ratio_less 00347 : __ratio_less_impl<_R1, _R2>::type 00348 { }; 00349 00350 /// ratio_less_equal 00351 template<typename _R1, typename _R2> 00352 struct ratio_less_equal 00353 : integral_constant<bool, !ratio_less<_R2, _R1>::value> 00354 { }; 00355 00356 /// ratio_greater 00357 template<typename _R1, typename _R2> 00358 struct ratio_greater 00359 : integral_constant<bool, ratio_less<_R2, _R1>::value> 00360 { }; 00361 00362 /// ratio_greater_equal 00363 template<typename _R1, typename _R2> 00364 struct ratio_greater_equal 00365 : integral_constant<bool, !ratio_less<_R1, _R2>::value> 00366 { }; 00367 00368 typedef ratio<1, 1000000000000000000> atto; 00369 typedef ratio<1, 1000000000000000> femto; 00370 typedef ratio<1, 1000000000000> pico; 00371 typedef ratio<1, 1000000000> nano; 00372 typedef ratio<1, 1000000> micro; 00373 typedef ratio<1, 1000> milli; 00374 typedef ratio<1, 100> centi; 00375 typedef ratio<1, 10> deci; 00376 typedef ratio< 10, 1> deca; 00377 typedef ratio< 100, 1> hecto; 00378 typedef ratio< 1000, 1> kilo; 00379 typedef ratio< 1000000, 1> mega; 00380 typedef ratio< 1000000000, 1> giga; 00381 typedef ratio< 1000000000000, 1> tera; 00382 typedef ratio< 1000000000000000, 1> peta; 00383 typedef ratio< 1000000000000000000, 1> exa; 00384 00385 // @} group ratio 00386 _GLIBCXX_END_NAMESPACE_VERSION 00387 } // namespace 00388 00389 #endif //_GLIBCXX_USE_C99_STDINT_TR1 00390 00391 #endif //__GXX_EXPERIMENTAL_CXX0X__ 00392 00393 #endif //_GLIBCXX_RATIO