Real algebraic numbers

00001 
00008 #ifndef SYNAPS_ARITHM_RATIONAL_H
00009 #define SYNAPS_ARITHM_RATIONAL_H
00010 
00011 #include <cassert>
00012 #include <synaps/init.h>
00013 #include <synaps/base/comparison.h>
00014 #include <synaps/arithm/sign.h>
00015 
00016 __BEGIN_NAMESPACE_SYNAPS
00017 
00018 
00023 template < typename  NT_ >
00024 class Rational
00025 {
00026  public:
00027   typedef NT_        NT;
00028   Rational() : num_(0), den_(1) { }
00029   template < typename  RT >
00030   Rational(const RT& n) : num_(n), den_(1) {}
00031   template < typename  RT1, typename  RT2 >
00032   Rational(const RT1& n, const RT2& d) : num_(n), den_(d)
00033   {
00034     assert( d != 0);
00035     adjust_sign();
00036   }
00037   
00038   Rational<NT>& operator+= (const Rational<NT>& r);
00039   Rational<NT>& operator-= (const Rational<NT>& r);
00040   Rational<NT>& operator*= (const Rational<NT>& r);
00041   Rational<NT>& operator/= (const Rational<NT>& r);
00042   Rational<NT>& operator+= (const NT& r);
00043   Rational<NT>& operator-= (const NT& r);
00044   Rational<NT>& operator*= (const NT& r);
00045   Rational<NT>& operator/= (const NT& r);
00046   
00047   Rational<NT>&    normalize();
00048   Rational<NT>&    adjust_sign();
00049   
00050   const NT&   numerator()   const { return num_; }
00051   const NT&   denominator() const { return den_; }
00052 
00053  public:
00054   NT   num_;     
00055   NT   den_;     
00056 };
00057 //--------------------------------------------------------------------
00058 namespace arithm 
00059 {
00060   template<class T>  struct isfield_;
00061   template<class X>  struct isfield_<Rational<X> > { typedef true_t T; };
00062 }
00063 //--------------------------------------------------------------------
00064 
00065 template<class C> inline
00066 bool adjust_denum( const C & x ) { return x < 0;  };
00067 
00068 template < typename NT >  inline
00069 Rational<NT>&
00070 Rational<NT>::adjust_sign()
00071 {
00072   if ( adjust_denum( den_ ) ) { num_ = -num_; den_ = -den_; }
00073   return *this;
00074 }
00075 //------------------------------------------------------------------------------------------
00076 
00077 template < typename NT >  inline
00078 Rational<NT>&
00079 Rational<NT>::normalize()
00080 {
00081   if ( num_ == den_ ) {
00082     num_ = den_ = 1;
00083     return *this;
00084   }
00085   
00086   if (-num_ == den_) {
00087       num_ = -1;
00088       den_ = 1;
00089       return *this;
00090   }
00091   NT ggt = gcd(num_, den_);
00092   if (ggt != 1 ) {
00093     num_ /= ggt;
00094     den_ /= ggt;
00095     adjust_sign();
00096   }
00097   return *this;
00098 }
00099 //------------------------------------------------------------------------------------------
00100 
00101 // Arithmetic operators
00102 template < typename NT >  inline
00103 Rational<NT>&
00104 Rational<NT>::operator+= (const Rational<NT>& r)
00105 {
00106   num_ = num_ * r.den_ + r.num_ * den_;
00107   den_ *= r.den_;
00108   return *this;
00109 }
00110 //------------------------------------------------------------------------------------------
00111 
00112 
00113 template < typename NT >  inline
00114 Rational<NT>&
00115 Rational<NT>::operator-= (const Rational<NT>& r)
00116 {
00117   num_ = num_ * r.den_ - r.num_ * den_;
00118   den_ *= r.den_;
00119   return *this;
00120 }
00121 //------------------------------------------------------------------------------------------
00122 
00123 template < typename NT >  inline
00124 Rational<NT>&
00125 Rational<NT>::operator*= (const Rational<NT>& r)
00126 {
00127   num_ *= r.num_;
00128   den_ *= r.den_;
00129   return *this;
00130 }
00131 //------------------------------------------------------------------------------------------
00132 
00133 template < typename NT >  inline
00134 Rational<NT>& Rational<NT>::operator/= (const Rational<NT>& r)
00135 {
00136   assert( r.num_ != 0 );
00137   num_ *= r.den_;
00138   den_ *= r.num_;
00139   adjust_sign();
00140   return *this;
00141 }
00142 //------------------------------------------------------------------------------------------
00143 
00144 template < typename NT >  inline
00145 Rational<NT>& Rational<NT>::operator+= (const NT& r)
00146 {
00147   num_ += r * den_;
00148   return *this;
00149 }
00150 //------------------------------------------------------------------------------------------
00151 
00152 template < typename NT >  inline
00153 Rational<NT>& Rational<NT>::operator-= (const NT& r)
00154 {
00155   num_ -= r * den_;
00156   return *this;
00157 }
00158 //------------------------------------------------------------------------------------------
00159 
00160 template < typename NT >  inline
00161 Rational<NT>&
00162 Rational<NT>::operator*= (const NT& r)
00163 {
00164   num_ *= r;
00165   return *this;
00166 }
00167 //------------------------------------------------------------------------------------------
00168 
00169 template < typename NT >  inline
00170 Rational<NT>&
00171 Rational<NT>::operator/= (const NT& r)
00172 {
00173   assert( r != 0 );
00174   den_ *= r;
00175   adjust_sign();
00176   return *this;
00177 }
00178 //------------------------------------------------------------------------------------------
00179 
00180 // Help function. Do not use it :-)
00181 template < typename NT >  inline
00182 int quotient_cmp( const Rational<NT>& x, const Rational<NT>& y )
00183 {
00184   int xsign = sign(x.num_);
00185   int ysign = sign(y.num_);
00186   
00187   if ((xsign == 0) && (ysign == 0)) return EQUAL;
00188   if (xsign < ysign) return SMALLER;
00189   if (xsign > ysign) return LARGER;
00190   // now x and y have the same sign
00191   NT ta = x.num_ * y.den_;
00192   NT tb = y.num_ * x.den_;
00193   NT t = ta - tb;
00194   return sign(t);
00195 }
00196 //------------------------------------------------------------------------------------------
00197 
00198 template < typename NT > inline
00199 int compare(const Rational<NT>& x, const Rational<NT>& y)
00200 { return quotient_cmp(x, y); }
00201 //------------------------------------------------------------------------------------------
00202 
00203 template < typename NT > inline
00204 std::ostream&
00205 operator<<(std::ostream& s, const Rational<NT>& r)
00206 {
00207    return s << r.numerator() << "/" << r.denominator();
00208 }
00209 //------------------------------------------------------------------------------------------
00210 
00211 
00212 //------------------------------------------------------------------------------------------
00213 // Arithmetic with Rationals
00214 //------------------------------------------------------------------------------------------
00215 template < typename NT >  inline
00216 Rational<NT>
00217 operator+(const Rational<NT>& x, const Rational<NT>& y)
00218 {
00219   Rational<NT> z = x;
00220   return z += y;
00221 }
00222 //------------------------------------------------------------------------------------------
00223 
00224 template < typename NT >  inline
00225 Rational<NT>
00226 operator-(const Rational<NT>& x, const Rational<NT>& y)
00227 { return (Rational<NT>(x) -= y); }
00228 //------------------------------------------------------------------------------------------
00229 
00230 template < typename NT >  inline
00231 Rational<NT>
00232 operator*(const Rational<NT>& x, const Rational<NT>& y)
00233 {
00234   Rational<NT> z = x;
00235   return z *= y;
00236 }
00237 //------------------------------------------------------------------------------------------
00238 
00239 template < typename NT >  inline
00240 Rational<NT>
00241 operator/(const Rational<NT>& x, const Rational<NT>& y)
00242 {
00243   Rational<NT> z = x;
00244   return z /= y;
00245 }
00246 //------------------------------------------------------------------------------------------
00247 
00248 template < typename NT >  inline
00249 Rational<NT>
00250 operator-(const Rational<NT>& x)
00251 { return Rational<NT>(-x.num_,x.den_); }
00252 //------------------------------------------------------------------------------------------
00253 
00254 template < typename NT >  inline
00255 Rational<NT>
00256 operator+(const NT& x, const Rational<NT>& y)
00257 {
00258   Rational<NT> z(x);
00259   return z += y;
00260 }
00261 //------------------------------------------------------------------------------------------
00262 
00263 template < typename NT >  inline
00264 Rational<NT>
00265 operator+(const Rational<NT>& x, const NT& y)
00266 {
00267   Rational<NT> z = x;
00268   return z += y;
00269 }
00270 //------------------------------------------------------------------------------------------
00271 
00272 template < typename NT >  inline
00273 Rational<NT>
00274 operator-(const NT& x, const Rational<NT>& y)
00275 {
00276   Rational<NT> z(x);
00277   return z -= y;
00278 }
00279 //------------------------------------------------------------------------------------------
00280 
00281 template < typename NT >  inline
00282 Rational<NT>
00283 operator-(const Rational<NT>& x, const NT& y)
00284 {
00285   Rational<NT> z = x;
00286   return z -= y;
00287 }
00288 //------------------------------------------------------------------------------------------
00289 
00290 template < typename NT >  inline
00291 Rational<NT>
00292 operator*(const NT& x, const Rational<NT>& y)
00293 {
00294   Rational<NT> z(x);
00295   return z *= y;
00296 }
00297 //------------------------------------------------------------------------------------------
00298 
00299 template < typename NT >  inline
00300 Rational<NT>
00301 operator*(const Rational<NT>& x, const NT& y)
00302 {
00303   Rational<NT> z = x;
00304   return z *= y;
00305 }
00306 //------------------------------------------------------------------------------------------
00307 
00308 template < typename NT >  inline
00309 Rational<NT>
00310 operator/(const NT& x, const Rational<NT>& y)
00311 {
00312   Rational<NT> z(x) ;
00313   return z /= y;
00314 }
00315 //------------------------------------------------------------------------------------------
00316 
00317 template < typename NT >  inline
00318 Rational<NT>
00319 operator/(const Rational<NT>& x, const NT& y)
00320 {
00321   Rational<NT> z = x;
00322   return z /= y;
00323 }
00324 //------------------------------------------------------------------------------------------
00325 
00326 
00327 
00328 //------------------------------------------------------------------------------------------
00329 // Booleans operations
00330 //------------------------------------------------------------------------------------------
00331 
00332 template < typename NT >  inline
00333 bool
00334 operator==(const Rational<NT>& x, const Rational<NT>& y)
00335 { return x.num_ * y.den_ == x.den_ * y.num_; }
00336 //------------------------------------------------------------------------------------------
00337 
00338 template < typename NT >  inline
00339 bool
00340 operator==(const Rational<NT>& x, const NT& y)
00341 { return x.den_ * y == x.num_; }
00342 //------------------------------------------------------------------------------------------
00343 
00344 template < typename NT >  inline
00345 bool
00346 operator==(const NT& x, const Rational<NT>& y)
00347 { return y == x; }
00348 //------------------------------------------------------------------------------------------
00349 
00350 template < typename NT >  inline
00351 bool
00352 operator!=(const Rational<NT>& x, const Rational<NT>& y)
00353 { return ! (x == y); }
00354 //------------------------------------------------------------------------------------------
00355 
00356 template < typename NT >  inline
00357 bool
00358 operator!=(const Rational<NT>& x, const NT& y)
00359 { return ! (x == y); }
00360 //------------------------------------------------------------------------------------------
00361 
00362 template < typename NT >  inline
00363 bool
00364 operator!=(const NT& x, const Rational<NT>& y)
00365 { return ! (x == y); }
00366 //------------------------------------------------------------------------------------------
00367 
00368 template < typename NT >  inline
00369 bool
00370 operator<(const Rational<NT>& x, const Rational<NT>& y)
00371 {
00372   return quotient_cmp(x,y) == SMALLER;
00373 }
00374 //------------------------------------------------------------------------------------------
00375 
00376 template < typename NT >  inline
00377 bool
00378 operator<(const Rational<NT>& x, const NT& y)
00379 {
00380   return quotient_cmp(x,Rational<NT>(y)) == SMALLER;
00381 }
00382 //------------------------------------------------------------------------------------------
00383 
00384 template < typename NT >  inline
00385 bool
00386 operator<(const NT& x, const Rational<NT>& y)
00387 {
00388   return quotient_cmp(Rational<NT>(x),y) == SMALLER;
00389 }
00390 //------------------------------------------------------------------------------------------
00391 
00392 template < typename NT >  inline
00393 bool
00394 operator>(const Rational<NT>& x, const Rational<NT>& y)
00395 { return y < x; }
00396 //------------------------------------------------------------------------------------------
00397 
00398 template < typename NT >  inline
00399 bool
00400 operator>(const Rational<NT>& x, const NT& y)
00401 { return y < x; }
00402 //------------------------------------------------------------------------------------------
00403 
00404 template < typename NT >  inline
00405 bool
00406 operator>(const NT& x, const Rational<NT>& y)
00407 { return y < x; }
00408 //------------------------------------------------------------------------------------------
00409 
00410 
00411 template < typename NT >  inline
00412 bool
00413 operator<=(const Rational<NT>& x, const Rational<NT>& y)
00414 { return ! (y < x); }
00415 //------------------------------------------------------------------------------------------
00416 
00417 template < typename NT >  inline
00418 bool
00419 operator<=(const Rational<NT>& x, const NT& y)
00420 { return ! (y < x); }
00421 //------------------------------------------------------------------------------------------
00422 
00423 template < typename NT >  inline
00424 bool
00425 operator<=(const NT& x, const Rational<NT>& y)
00426 { return ! (y < x); }
00427 //------------------------------------------------------------------------------------------
00428 
00429 
00430 template < typename NT >  inline
00431 bool
00432 operator>=(const Rational<NT>& x, const Rational<NT>& y)
00433 { return ! (x < y); }
00434 //------------------------------------------------------------------------------------------
00435 
00436 template < typename NT >  inline
00437 bool
00438 operator>=(const Rational<NT>& x, const NT& y)
00439 { return ! (x < y); }
00440 //------------------------------------------------------------------------------------------
00441 
00442 template < typename NT >  inline
00443 bool
00444 operator>=(const NT& x, const Rational<NT>& y)
00445 { return ! (x < y); }
00446 //------------------------------------------------------------------------------------------
00447 
00448 
00449 
00450 // Change this asa!
00451 template < typename NT >
00452 double
00453 to_double(const Rational<NT>& q)
00454 {
00455   return (to_double(q.numerator()) / to_double(q.denominator()));
00456 }
00457 //------------------------------------------------------------------------------------------
00458 
00459 
00460 // Global functions for the numerator and the denominator
00461 template < typename NT >  inline
00462 const NT&
00463 denominator(const Rational<NT>& q)
00464 { return q.den_ ; }
00465 //------------------------------------------------------------------------------------------
00466 
00467 template < typename NT >  inline
00468 const NT&
00469 numerator(const Rational<NT>& q)
00470 { return q.num_ ; }
00471 //------------------------------------------------------------------------------------------
00472 
00473 namespace let 
00474 {
00475   template < typename T, typename S > inline
00476   void assign(T & a, const Rational<S>& x)
00477   {
00478     a = x.numerator()/x.denominator();
00479   }
00480   template < typename T > inline
00481   void assign(Rational<T>& a, const T& x)
00482         {
00483                 a = Rational<T>(x);
00484         }
00485 
00486   inline void assign(double& a, const Rational<double>& x)
00487   {
00488     a = x.numerator()/x.denominator();
00489   }
00490 
00491 }
00492 
00493 __END_NAMESPACE_SYNAPS
00494 
00495 #endif // SYNAPS_ARITHM_RATIONAL_H
00496
synaps/arithm/Rational.h
