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   return r.sign_ * ::sign (int (r.num_ * s.den_) - int (s.num_ * r.den_));
 144 }
 145
 146 int
 147 compare (Rational const &r, Rational const &s)
 148 {
 149   return Rational::compare (r, s);
 150 }
 151
 152 Rational &
 153 Rational::operator %= (Rational r)
 154 {
 155   *this = mod_rat (r);
 156   return *this;
 157 }
 158
 159 Rational &
 160 Rational::operator += (Rational r)
 161 {
 162   if (is_infinity ())
 163     ;
 164   else if (r.is_infinity ())
 165     *this = r;
 166   else
 167     {
 168       int n = sign_ * num_ * r.den_ + r.sign_ * den_ * r.num_;
 169       int d = den_ * r.den_;
 170       sign_ = ::sign (n) * ::sign (d);
 171       num_ = abs (n);
 172       den_ = abs (d);
 173       normalise ();
 174     }
 175   return *this;
 176 }
 177
 178 /*
 179   copied from libg++ 2.8.0
 180 */
 181 Rational::Rational (double x)
 182 {
 183   if (x != 0.0)
 184     {
 185       sign_ = ::sign (x);
 186       x *= sign_;
 187
 188       int expt;
 189       double mantissa = frexp (x, &expt);
 190
 191       const int FACT = 1 << 20;
 192
 193       /*
 194         Thanks to Afie for this too simple  idea.
 195
 196         do not blindly substitute by libg++ code, since that uses
 197         arbitrary-size integers.  The rationals would overflow too
 198         easily.
 199       */
 200
 201       num_ = (unsigned int) (mantissa * FACT);
 202       den_ = (unsigned int) FACT;
 203       normalise ();
 204       if (expt < 0)
 205         den_ <<= -expt;
 206       else
 207         num_ <<= expt;
 208       normalise ();
 209     }
 210   else
 211     {
 212       num_ = 0;
 213       den_ = 1;
 214       sign_ = 0;
 215       normalise ();
 216     }
 217 }
 218
 219 void
 220 Rational::invert ()
 221 {
 222   int r (num_);
 223   num_ = den_;
 224   den_ = r;
 225 }
 226
 227 Rational &
 228 Rational::operator *= (Rational r)
 229 {
 230   sign_ *= ::sign (r.sign_);
 231   if (r.is_infinity ())
 232     {
 233       sign_ = sign () * 2;
 234       goto exit_func;
 235     }
 236
 237   num_ *= r.num_;
 238   den_ *= r.den_;
 239
 240   normalise ();
 241  exit_func:
 242   return *this;
 243 }
 244
 245 Rational &
 246 Rational::operator /= (Rational r)
 247 {
 248   r.invert ();
 249   return (*this *= r);
 250 }
 251
 252 void
 253 Rational::negate ()
 254 {
 255   sign_ *= -1;
 256 }
 257
 258 Rational &
 259 Rational::operator -= (Rational r)
 260 {
 261   r.negate ();
 262   return (*this += r);
 263 }
 264
 265 String
 266 Rational::to_string () const
 267 {
 268   if (is_infinity ())
 269     {
 270       String s (sign_ > 0 ? "" : "-");
 271       return String (s + "infinity");
 272     }
 273
 274   String s = ::to_string (num ());
 275   if (den () != 1 && num ())
 276     s += "/" + ::to_string (den ());
 277   return s;
 278 }
 279
 280 int
 281 Rational::to_int () const
 282 {
 283   return num () / den ();
 284 }
 285
 286 int
 287 sign (Rational r)
 288 {
 289   return r.sign ();
 290 }
 291
 292 bool
 293 Rational::is_infinity () const
 294 {
 295   return sign_ == 2 || sign_ == -2;
 296 }