flower/rational.cc

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