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