flower/rational.cc

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