flower/rational.cc

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