libstdc++
|
00001 // ratio -*- C++ -*- 00002 00003 // Copyright (C) 2008, 2009, 2010 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 const intmax_t __gcd = 00181 __static_gcd<_R1::den, _R2::den>::value; 00182 00183 public: 00184 typedef ratio< 00185 __safe_add< 00186 __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, 00187 __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value, 00188 __safe_multiply<_R1::den, (_R2::den / __gcd)>::value> type; 00189 00190 static constexpr intmax_t num = type::num; 00191 static constexpr intmax_t den = type::den; 00192 }; 00193 00194 template<typename _R1, typename _R2> 00195 constexpr intmax_t ratio_add<_R1, _R2>::num; 00196 00197 template<typename _R1, typename _R2> 00198 constexpr intmax_t ratio_add<_R1, _R2>::den; 00199 00200 /// ratio_subtract 00201 template<typename _R1, typename _R2> 00202 struct ratio_subtract 00203 { 00204 typedef typename ratio_add< 00205 _R1, 00206 ratio<-_R2::num, _R2::den>>::type type; 00207 00208 static constexpr intmax_t num = type::num; 00209 static constexpr intmax_t den = type::den; 00210 }; 00211 00212 template<typename _R1, typename _R2> 00213 constexpr intmax_t ratio_subtract<_R1, _R2>::num; 00214 00215 template<typename _R1, typename _R2> 00216 constexpr intmax_t ratio_subtract<_R1, _R2>::den; 00217 00218 /// ratio_multiply 00219 template<typename _R1, typename _R2> 00220 struct ratio_multiply 00221 { 00222 private: 00223 static const intmax_t __gcd1 = 00224 __static_gcd<_R1::num, _R2::den>::value; 00225 static const intmax_t __gcd2 = 00226 __static_gcd<_R2::num, _R1::den>::value; 00227 00228 public: 00229 typedef ratio< 00230 __safe_multiply<(_R1::num / __gcd1), 00231 (_R2::num / __gcd2)>::value, 00232 __safe_multiply<(_R1::den / __gcd2), 00233 (_R2::den / __gcd1)>::value> type; 00234 00235 static constexpr intmax_t num = type::num; 00236 static constexpr intmax_t den = type::den; 00237 }; 00238 00239 template<typename _R1, typename _R2> 00240 constexpr intmax_t ratio_multiply<_R1, _R2>::num; 00241 00242 template<typename _R1, typename _R2> 00243 constexpr intmax_t ratio_multiply<_R1, _R2>::den; 00244 00245 /// ratio_divide 00246 template<typename _R1, typename _R2> 00247 struct ratio_divide 00248 { 00249 static_assert(_R2::num != 0, "division by 0"); 00250 00251 typedef typename ratio_multiply< 00252 _R1, 00253 ratio<_R2::den, _R2::num>>::type type; 00254 00255 static constexpr intmax_t num = type::num; 00256 static constexpr intmax_t den = type::den; 00257 }; 00258 00259 template<typename _R1, typename _R2> 00260 constexpr intmax_t ratio_divide<_R1, _R2>::num; 00261 00262 template<typename _R1, typename _R2> 00263 constexpr intmax_t ratio_divide<_R1, _R2>::den; 00264 00265 /// ratio_equal 00266 template<typename _R1, typename _R2> 00267 struct ratio_equal 00268 : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den> 00269 { }; 00270 00271 /// ratio_not_equal 00272 template<typename _R1, typename _R2> 00273 struct ratio_not_equal 00274 : integral_constant<bool, !ratio_equal<_R1, _R2>::value> 00275 { }; 00276 00277 template<typename _R1> 00278 struct __ratio_less_impl_1 00279 : integral_constant<bool, _R1::num < _R1::den> 00280 { }; 00281 00282 template<typename _R1, typename _R2, 00283 bool = (_R1::num == 0 || _R2::num == 0 00284 || (__static_sign<_R1::num>::value 00285 != __static_sign<_R2::num>::value)), 00286 bool = (__static_sign<_R1::num>::value == -1 00287 && __static_sign<_R2::num>::value == -1)> 00288 struct __ratio_less_impl 00289 : __ratio_less_impl_1<typename ratio_divide<_R1, _R2>::type>::type 00290 { }; 00291 00292 template<typename _R1, typename _R2> 00293 struct __ratio_less_impl<_R1, _R2, true, false> 00294 : integral_constant<bool, _R1::num < _R2::num> 00295 { }; 00296 00297 template<typename _R1, typename _R2> 00298 struct __ratio_less_impl<_R1, _R2, false, true> 00299 : __ratio_less_impl_1<typename ratio_divide<_R2, _R1>::type>::type 00300 { }; 00301 00302 /// ratio_less 00303 template<typename _R1, typename _R2> 00304 struct ratio_less 00305 : __ratio_less_impl<_R1, _R2>::type 00306 { }; 00307 00308 /// ratio_less_equal 00309 template<typename _R1, typename _R2> 00310 struct ratio_less_equal 00311 : integral_constant<bool, !ratio_less<_R2, _R1>::value> 00312 { }; 00313 00314 /// ratio_greater 00315 template<typename _R1, typename _R2> 00316 struct ratio_greater 00317 : integral_constant<bool, ratio_less<_R2, _R1>::value> 00318 { }; 00319 00320 /// ratio_greater_equal 00321 template<typename _R1, typename _R2> 00322 struct ratio_greater_equal 00323 : integral_constant<bool, !ratio_less<_R1, _R2>::value> 00324 { }; 00325 00326 typedef ratio<1, 1000000000000000000> atto; 00327 typedef ratio<1, 1000000000000000> femto; 00328 typedef ratio<1, 1000000000000> pico; 00329 typedef ratio<1, 1000000000> nano; 00330 typedef ratio<1, 1000000> micro; 00331 typedef ratio<1, 1000> milli; 00332 typedef ratio<1, 100> centi; 00333 typedef ratio<1, 10> deci; 00334 typedef ratio< 10, 1> deca; 00335 typedef ratio< 100, 1> hecto; 00336 typedef ratio< 1000, 1> kilo; 00337 typedef ratio< 1000000, 1> mega; 00338 typedef ratio< 1000000000, 1> giga; 00339 typedef ratio< 1000000000000, 1> tera; 00340 typedef ratio< 1000000000000000, 1> peta; 00341 typedef ratio< 1000000000000000000, 1> exa; 00342 00343 // @} group ratio 00344 _GLIBCXX_END_NAMESPACE_VERSION 00345 } // namespace 00346 00347 #endif //_GLIBCXX_USE_C99_STDINT_TR1 00348 00349 #endif //__GXX_EXPERIMENTAL_CXX0X__ 00350 00351 #endif //_GLIBCXX_RATIO