flower/rational.cc

   1 /*
   2   rational.cc -- implement Rational
   3
   4   source file of the Flower Library
   5
   6   (c) 1997--2004 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "rational.hh"
  10
  11 #include <cmath>
  12 #include <cstdlib>
  13
  14 #include "string-convert.hh"
  15 #include "libc-extension.hh"
  16
  17 Rational::operator double () const
  18 {
  19   return (double)sign_ * num_ / den_;
  20 }
  21
  22 #ifdef STREAM_SUPPORT
  23 ostream &
  24 operator << (ostream &o, Rational r)
  25 {
  26   o <<  r.string ();
  27   return o;
  28 }
  29 #endif
  30
  31
  32 Rational
  33 Rational::trunc_rat () const
  34 {
  35   return Rational (num_ - (num_ % den_), den_);
  36 }
  37
  38 Rational::Rational ()
  39 {
  40   sign_ = 0;
  41   num_ = den_ = 1;
  42 }
  43
  44 Rational::Rational (int n, int d)
  45 {
  46   sign_ = ::sign (n) * ::sign (d);
  47   num_ = abs (n);
  48   den_ = abs (d);
  49   normalise ();
  50 }
  51
  52 Rational::Rational (int n)
  53 {
  54   sign_ = ::sign (n);
  55   num_ = abs (n);
  56   den_= 1;
  57 }
  58
  59 static
  60 int gcd (int a, int b)
  61 {
  62   int t;
  63   while ((t = a % b))
  64     {
  65       a = b;
  66       b = t;
  67     }
  68   return b;
  69 }
  70
  71 #if 0
  72 static
  73 int lcm (int a, int b)
  74 {
  75   return abs (a*b / gcd (a,b));
  76 }
  77 #endif
  78
  79 void
  80 Rational::set_infinite (int s)
  81 {
  82   sign_ = ::sign (s) * 2;
  83 }
  84
  85 Rational
  86 Rational::operator - () const
  87 {
  88   Rational r (*this);
  89   r.negate ();
  90   return r;
  91 }
  92
  93 Rational
  94 Rational::div_rat (Rational div) const
  95 {
  96   Rational r (*this);
  97   r /= div;
  98   return r.trunc_rat ();
  99 }
 100
 101 Rational
 102 Rational::mod_rat (Rational div) const
 103 {
 104   Rational r (*this);
 105   r = (r / div - r.div_rat (div)) * div;
 106   return r;
 107 }
 108
 109 void
 110 Rational::normalise ()
 111 {
 112   if (!sign_)
 113     {
 114       den_ = 1;
 115       num_ = 0;
 116     }
 117   else if (!den_)
 118     {
 119       sign_ = 2;
 120       num_ = 1;
 121     }
 122   else if (!num_)
 123     {
 124       sign_ = 0;
 125       den_ = 1;
 126     }
 127   else
 128     {
 129       int g = gcd (num_ , den_);
 130
 131       num_ /= g;
 132       den_ /= g;
 133     }
 134 }
 135 int
 136 Rational::sign () const
 137 {
 138   return ::sign (sign_);
 139 }
 140
 141 int
 142 Rational::compare (Rational const &r, Rational const &s)
 143 {
 144   if (r.sign_ < s.sign_)
 145     return -1;
 146   else if (r.sign_ > s.sign_)
 147     return 1;
 148   else if (r.is_infinity ())
 149     return 0;
 150   else if (r.sign_ == 0)
 151     return 0;
 152   else
 153     {
 154       return r.sign_ * ::sign  (int (r.num_ * s.den_) - int (s.num_ * r.den_));
 155     }
 156 }
 157
 158 int
 159 compare (Rational const &r, Rational const &s)
 160 {
 161   return Rational::compare (r, s );
 162 }
 163
 164 Rational &
 165 Rational::operator %= (Rational r)
 166 {
 167   *this = r.mod_rat (r);
 168   return *this;
 169 }
 170
 171 Rational &
 172 Rational::operator += (Rational r)
 173 {
 174   if (is_infinity ())
 175     ;
 176   else if (r.is_infinity ())
 177     {
 178       *this = r;
 179     }
 180   else
 181     {
 182       int n = sign_ * num_ *r.den_ + r.sign_ * den_ * r.num_;
 183       int d = den_ * r.den_;
 184       sign_ =  ::sign (n) * ::sign (d);
 185       num_ = abs (n);
 186       den_ = abs (d);
 187       normalise ();
 188     }
 189   return *this;
 190 }
 191
 192
 193 /*
 194   copied from libg++ 2.8.0
 195  */
 196 Rational::Rational (double x)
 197 {
 198   if (x != 0.0)
 199     {
 200       sign_ = ::sign (x);
 201       x *= sign_;
 202
 203       int expt;
 204       double mantissa = frexp (x, &expt);
 205
 206       const int FACT = 1 << 20;
 207
 208       /*
 209         Thanks to Afie for this too simple  idea.
 210
 211         do not blindly substitute by libg++ code, since that uses
 212         arbitrary-size integers.  The rationals would overflow too
 213         easily.
 214       */
 215
 216       num_ = (unsigned int) (mantissa * FACT);
 217       den_ = (unsigned int) FACT;
 218       normalise ();
 219       if (expt < 0)
 220         den_ <<= -expt;
 221       else
 222         num_ <<= expt;
 223       normalise ();
 224     }
 225   else
 226     {
 227       num_ = 0;
 228       den_ = 1;
 229       sign_ =0;
 230       normalise ();
 231     }
 232 }
 233
 234
 235 void
 236 Rational::invert ()
 237 {
 238   int r (num_);
 239   num_  = den_;
 240   den_ = r;
 241 }
 242
 243 Rational &
 244 Rational::operator *= (Rational r)
 245 {
 246   sign_ *= ::sign (r.sign_);
 247   if (r.is_infinity ())
 248     {
 249       sign_ = sign () * 2;
 250       goto exit_func;
 251     }
 252
 253   num_ *= r.num_;
 254   den_ *= r.den_;
 255
 256   normalise ();
 257  exit_func:
 258   return *this;
 259 }
 260
 261 Rational &
 262 Rational::operator /= (Rational r)
 263 {
 264   r.invert ();
 265   return (*this *= r);
 266 }
 267
 268 void
 269 Rational::negate ()
 270 {
 271   sign_ *= -1;
 272 }
 273
 274 Rational&
 275 Rational::operator -= (Rational r)
 276 {
 277   r.negate ();
 278   return (*this += r);
 279 }
 280
 281 String
 282 Rational::to_string () const
 283 {
 284   if (is_infinity ())
 285     {
 286       String s (sign_ > 0 ? "" : "-" );
 287       return String (s + "infinity");
 288     }
 289
 290   String s = ::to_string (num ());
 291   if (den () != 1 && num ())
 292     s += "/" + ::to_string (den ());
 293   return s;
 294 }
 295
 296 int
 297 Rational::to_int () const
 298 {
 299   return num () / den ();
 300 }
 301
 302 int
 303 sign (Rational r)
 304 {
 305   return r.sign ();
 306 }
 307
 308 bool
 309 Rational::is_infinity () const
 310 {
 311   return sign_ == 2 || sign_ == -2;
 312 }