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