libstdc++
|
00001 // ratio -*- C++ -*- 00002 00003 // Copyright (C) 2008, 2009 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 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 <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 00044 { 00045 /** 00046 * @defgroup ratio Rational Arithmetic 00047 * @ingroup utilities 00048 * 00049 * Compile time representation of fininte rational numbers. 00050 * @{ 00051 */ 00052 00053 template<intmax_t _Pn> 00054 struct __static_sign 00055 : integral_constant<intmax_t, (_Pn < 0) ? -1 : 1> 00056 { }; 00057 00058 template<intmax_t _Pn> 00059 struct __static_abs 00060 : integral_constant<intmax_t, _Pn * __static_sign<_Pn>::value> 00061 { }; 00062 00063 template<intmax_t _Pn, intmax_t _Qn> 00064 struct __static_gcd; 00065 00066 template<intmax_t _Pn, intmax_t _Qn> 00067 struct __static_gcd 00068 : __static_gcd<_Qn, (_Pn % _Qn)> 00069 { }; 00070 00071 template<intmax_t _Pn> 00072 struct __static_gcd<_Pn, 0> 00073 : integral_constant<intmax_t, __static_abs<_Pn>::value> 00074 { }; 00075 00076 template<intmax_t _Qn> 00077 struct __static_gcd<0, _Qn> 00078 : integral_constant<intmax_t, __static_abs<_Qn>::value> 00079 { }; 00080 00081 // Let c = 2^(half # of bits in an intmax_t) 00082 // then we find a1, a0, b1, b0 s.t. N = a1*c + a0, M = b1*c + b0 00083 // The multiplication of N and M becomes, 00084 // N * M = (a1 * b1)c^2 + (a0 * b1 + b0 * a1)c + a0 * b0 00085 // Multiplication is safe if each term and the sum of the terms 00086 // is representable by intmax_t. 00087 template<intmax_t _Pn, intmax_t _Qn> 00088 struct __safe_multiply 00089 { 00090 private: 00091 static const uintmax_t __c = uintmax_t(1) << (sizeof(intmax_t) * 4); 00092 00093 static const uintmax_t __a0 = __static_abs<_Pn>::value % __c; 00094 static const uintmax_t __a1 = __static_abs<_Pn>::value / __c; 00095 static const uintmax_t __b0 = __static_abs<_Qn>::value % __c; 00096 static const uintmax_t __b1 = __static_abs<_Qn>::value / __c; 00097 00098 static_assert(__a1 == 0 || __b1 == 0, 00099 "overflow in multiplication"); 00100 static_assert(__a0 * __b1 + __b0 * __a1 < (__c >> 1), 00101 "overflow in multiplication"); 00102 static_assert(__b0 * __a0 <= __INTMAX_MAX__, 00103 "overflow in multiplication"); 00104 static_assert((__a0 * __b1 + __b0 * __a1) * __c <= 00105 __INTMAX_MAX__ - __b0 * __a0, "overflow in multiplication"); 00106 00107 public: 00108 static const intmax_t value = _Pn * _Qn; 00109 }; 00110 00111 // Helpers for __safe_add 00112 template<intmax_t _Pn, intmax_t _Qn, bool> 00113 struct __add_overflow_check_impl 00114 : integral_constant<bool, (_Pn <= __INTMAX_MAX__ - _Qn)> 00115 { }; 00116 00117 template<intmax_t _Pn, intmax_t _Qn> 00118 struct __add_overflow_check_impl<_Pn, _Qn, false> 00119 : integral_constant<bool, (_Pn >= -__INTMAX_MAX__ - _Qn)> 00120 { }; 00121 00122 template<intmax_t _Pn, intmax_t _Qn> 00123 struct __add_overflow_check 00124 : __add_overflow_check_impl<_Pn, _Qn, (_Qn >= 0)> 00125 { }; 00126 00127 template<intmax_t _Pn, intmax_t _Qn> 00128 struct __safe_add 00129 { 00130 static_assert(__add_overflow_check<_Pn, _Qn>::value != 0, 00131 "overflow in addition"); 00132 00133 static const intmax_t value = _Pn + _Qn; 00134 }; 00135 00136 /** 00137 * @brief Provides compile-time rational arithmetic. 00138 * 00139 * This class template represents any finite rational number with a 00140 * numerator and denominator representable by compile-time constants of 00141 * type intmax_t. The ratio is simplified when instantiated. 00142 * 00143 * For example: 00144 * @code 00145 * std::ratio<7,-21>::num == -1; 00146 * std::ratio<7,-21>::den == 3; 00147 * @endcode 00148 * 00149 */ 00150 template<intmax_t _Num, intmax_t _Den = 1> 00151 struct ratio 00152 { 00153 static_assert(_Den != 0, "denominator cannot be zero"); 00154 static_assert(_Num >= -__INTMAX_MAX__ && _Den >= -__INTMAX_MAX__, 00155 "out of range"); 00156 00157 // Note: sign(N) * abs(N) == N 00158 static const intmax_t num = 00159 _Num * __static_sign<_Den>::value / __static_gcd<_Num, _Den>::value; 00160 00161 static const intmax_t den = 00162 __static_abs<_Den>::value / __static_gcd<_Num, _Den>::value; 00163 }; 00164 00165 template<intmax_t _Num, intmax_t _Den> 00166 const intmax_t ratio<_Num, _Den>::num; 00167 00168 template<intmax_t _Num, intmax_t _Den> 00169 const intmax_t ratio<_Num, _Den>::den; 00170 00171 /// ratio_add 00172 template<typename _R1, typename _R2> 00173 struct ratio_add 00174 { 00175 private: 00176 static const intmax_t __gcd = 00177 __static_gcd<_R1::den, _R2::den>::value; 00178 00179 public: 00180 typedef ratio< 00181 __safe_add< 00182 __safe_multiply<_R1::num, (_R2::den / __gcd)>::value, 00183 __safe_multiply<_R2::num, (_R1::den / __gcd)>::value>::value, 00184 __safe_multiply<_R1::den, (_R2::den / __gcd)>::value> type; 00185 }; 00186 00187 /// ratio_subtract 00188 template<typename _R1, typename _R2> 00189 struct ratio_subtract 00190 { 00191 typedef typename ratio_add< 00192 _R1, 00193 ratio<-_R2::num, _R2::den>>::type type; 00194 }; 00195 00196 /// ratio_multiply 00197 template<typename _R1, typename _R2> 00198 struct ratio_multiply 00199 { 00200 private: 00201 static const intmax_t __gcd1 = 00202 __static_gcd<_R1::num, _R2::den>::value; 00203 static const intmax_t __gcd2 = 00204 __static_gcd<_R2::num, _R1::den>::value; 00205 00206 public: 00207 typedef ratio< 00208 __safe_multiply<(_R1::num / __gcd1), 00209 (_R2::num / __gcd2)>::value, 00210 __safe_multiply<(_R1::den / __gcd2), 00211 (_R2::den / __gcd1)>::value> type; 00212 }; 00213 00214 /// ratio_divide 00215 template<typename _R1, typename _R2> 00216 struct ratio_divide 00217 { 00218 static_assert(_R2::num != 0, "division by 0"); 00219 00220 typedef typename ratio_multiply< 00221 _R1, 00222 ratio<_R2::den, _R2::num>>::type type; 00223 }; 00224 00225 /// ratio_equal 00226 template<typename _R1, typename _R2> 00227 struct ratio_equal 00228 : integral_constant<bool, _R1::num == _R2::num && _R1::den == _R2::den> 00229 { }; 00230 00231 /// ratio_not_equal 00232 template<typename _R1, typename _R2> 00233 struct ratio_not_equal 00234 : integral_constant<bool, !ratio_equal<_R1, _R2>::value> 00235 { }; 00236 00237 template<typename _R1, typename _R2> 00238 struct __ratio_less_simple_impl 00239 : integral_constant<bool, 00240 (__safe_multiply<_R1::num, _R2::den>::value 00241 < __safe_multiply<_R2::num, _R1::den>::value)> 00242 { }; 00243 00244 // If the denominators are equal or the signs differ, we can just compare 00245 // numerators, otherwise fallback to the simple cross-multiply method. 00246 template<typename _R1, typename _R2> 00247 struct __ratio_less_impl 00248 : conditional<(_R1::den == _R2::den 00249 || (__static_sign<_R1::num>::value 00250 != __static_sign<_R2::num>::value)), 00251 integral_constant<bool, (_R1::num < _R2::num)>, 00252 __ratio_less_simple_impl<_R1, _R2>>::type 00253 { }; 00254 00255 /// ratio_less 00256 template<typename _R1, typename _R2> 00257 struct ratio_less 00258 : __ratio_less_impl<_R1, _R2>::type 00259 { }; 00260 00261 /// ratio_less_equal 00262 template<typename _R1, typename _R2> 00263 struct ratio_less_equal 00264 : integral_constant<bool, !ratio_less<_R2, _R1>::value> 00265 { }; 00266 00267 /// ratio_greater 00268 template<typename _R1, typename _R2> 00269 struct ratio_greater 00270 : integral_constant<bool, ratio_less<_R2, _R1>::value> 00271 { }; 00272 00273 /// ratio_greater_equal 00274 template<typename _R1, typename _R2> 00275 struct ratio_greater_equal 00276 : integral_constant<bool, !ratio_less<_R1, _R2>::value> 00277 { }; 00278 00279 typedef ratio<1, 1000000000000000000> atto; 00280 typedef ratio<1, 1000000000000000> femto; 00281 typedef ratio<1, 1000000000000> pico; 00282 typedef ratio<1, 1000000000> nano; 00283 typedef ratio<1, 1000000> micro; 00284 typedef ratio<1, 1000> milli; 00285 typedef ratio<1, 100> centi; 00286 typedef ratio<1, 10> deci; 00287 typedef ratio< 10, 1> deca; 00288 typedef ratio< 100, 1> hecto; 00289 typedef ratio< 1000, 1> kilo; 00290 typedef ratio< 1000000, 1> mega; 00291 typedef ratio< 1000000000, 1> giga; 00292 typedef ratio< 1000000000000, 1> tera; 00293 typedef ratio< 1000000000000000, 1> peta; 00294 typedef ratio< 1000000000000000000, 1> exa; 00295 00296 // @} group ratio 00297 } 00298 00299 #endif //_GLIBCXX_USE_C99_STDINT_TR1 00300 00301 #endif //__GXX_EXPERIMENTAL_CXX0X__ 00302 00303 #endif //_GLIBCXX_RATIO