Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_RATIONAL_RATIONAL 00002 #define H_MATH_RATIONAL_RATIONAL 00003 00006 #include <ostream> 00007 #include <stdexcept> 00008 #include <stdint.h> 00009 #include "math/gcd/gcd.h" 00010 #include "utils/preconditions/preconditions.h" 00011 00012 #define NEEDS_INT_DEFINED 00013 #include "third_party/safeint3.hpp" 00014 00015 00020 #pragma GCC diagnostic ignored "-Wtype-limits" 00021 namespace math { 00022 namespace rational { 00023 00024 template <typename T> 00025 class Rational { 00026 public: 00027 // compile assert 00028 C_ASSERT(NumericType<T>::isInt); 00029 00033 Rational():num(0),den(1) { 00034 } 00035 00040 Rational(T value):num(value),den(1) { 00041 normalize(); 00042 } 00043 00050 Rational(T n, T d):num(n),den(d) { 00051 Preconditions::check(d != 0, 00052 "Rational number shoud have non-zero denominator"); 00053 00054 normalize(); 00055 } 00056 00060 Rational(const Rational<T>& value):num(value.num),den(value.den) { 00061 Preconditions::check(value.den != 0, 00062 "Rational numer shoud have non-zero denominator"); 00063 normalize(); 00064 } 00065 00069 Rational<T> inverted() const { 00070 if (num == 0) { 00071 throw std::overflow_error("Division by zero!"); 00072 } 00073 return Rational<T>(den, num); 00074 } 00075 00079 T numerator() const { 00080 return num; 00081 } 00082 00086 T denominator() const { 00087 return den; 00088 } 00089 00095 void normalize() { 00096 T h = math::gcd::gcd(num, den); 00097 assert(h != 0); // gcd shouldn't return zero (den != 0) 00098 num /= h; 00099 den /= h; 00100 00101 if (IntTraits<T>::isSigned && (den < 0)) { 00102 den = -den; 00103 num = -num; 00104 } 00105 } 00106 00107 00108 private: 00110 T num; 00112 T den; 00113 }; 00114 00115 00128 template<typename T> 00129 Rational<T> operator*(const Rational<T> &a, const Rational<T> &b) 00130 { 00131 // here we use safe versions of computations 00132 // if you believe your code will won't need them, just make it as 00133 // normal multiplication (but it is not recommended) 00134 try { 00135 SafeInt<T> num(a.numerator()); num *= b.numerator(); 00136 SafeInt<T> den(a.denominator()); den *= b.denominator(); 00137 return Rational<T>((T)num, (T)den); 00138 } catch (SafeIntException err){ 00139 throw std::overflow_error("Overflow while multiplying"); 00140 } 00141 } 00142 00150 template<typename T> 00151 Rational<T> operator/(const Rational<T> &a, const Rational<T> &b) 00152 { 00153 if (b.numerator() == 0) { 00154 throw std::overflow_error("Division by zero!"); 00155 } 00156 00157 return a * b.inverted(); 00158 } 00159 00165 template<typename T> 00166 Rational<T> operator-(const Rational<T> &a) 00167 { 00168 // can't do unary minus on unsigned types 00169 C_ASSERT(IntTraits<T>::isSigned); 00170 // we need SafeInt here because unary minus on 00171 // MIN_INT will overflow. 00172 try { 00173 return Rational<T>(-SafeInt<T>(a.numerator()), a.denominator()); 00174 } catch (SafeIntException err){ 00175 throw std::overflow_error("Overflow while add/subtract"); 00176 } 00177 } 00178 00186 template<typename T> 00187 Rational<T> operator+(const Rational<T> &a, const Rational<T> &b) 00188 { 00189 try { 00190 SafeInt<T> t1(a.numerator()); t1 *= b.denominator(); 00191 SafeInt<T> t2(b.numerator()); t2 *= a.denominator(); 00192 SafeInt<T> den(a.denominator()); den *= b.denominator(); 00193 return Rational<T>( (T) (t1 + t2), den); 00194 } catch (SafeIntException err){ 00195 throw std::overflow_error("Overflow while add/subtract"); 00196 } 00197 } 00198 00206 template<typename T> 00207 Rational<T> operator-(const Rational<T> &a, const Rational<T> &b) 00208 { 00209 try { 00210 SafeInt<T> t1(a.numerator()); t1 *= b.denominator(); 00211 SafeInt<T> t2(b.numerator()); t2 *= a.denominator(); 00212 SafeInt<T> den(a.denominator()); den *= b.denominator(); 00213 return Rational<T>( (T) (t1 - t2), den); 00214 } catch (SafeIntException err){ 00215 throw std::overflow_error("Overflow while add/subtract"); 00216 } 00217 } 00218 00227 template<typename T> 00228 bool operator==(const Rational<T> &a, const Rational<T> &b) { 00229 return (a.numerator() == b.numerator()) && (a.denominator() == b.denominator()); 00230 } 00231 00237 template<typename T> 00238 bool operator<(const Rational<T> &a, const Rational<T> &b) { 00239 try { 00240 SafeInt<T> t1(a.numerator()); t1 *= b.denominator(); 00241 SafeInt<T> t2(b.numerator()); t2 *= a.denominator(); 00242 return t1 < t2; 00243 } catch (SafeIntException err){ 00244 throw std::overflow_error("Overflow while comparison"); 00245 } 00246 } 00247 00253 template<typename T> 00254 bool operator>(const Rational<T> &a, const Rational<T> &b) { 00255 return b < a; 00256 } 00257 00263 template<typename T> 00264 bool operator<=(const Rational<T> &a, const Rational<T> &b) { 00265 return !(b>a); 00266 } 00267 00273 template<typename T> 00274 bool operator>=(const Rational<T> &a, const Rational<T> &b) { 00275 return !(a<b); 00276 } 00277 00289 template<typename T> 00290 std::ostream& operator<<(std::ostream& out, const Rational<T> &a) { 00291 out << a.numerator() << "/" << a.denominator(); 00292 return out; 00293 } 00294 00295 } // rational 00296 } // math 00297 #endif