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 static
  57 int gcd (int a, int b)
  58 {
  59   int t;
  60   while ((t = a % b))
  61     {
  62       a = b;
  63       b = t;
  64     }
  65   return b;
  66 }
  67
  68 static
  69 int lcm (int a, int b)
  70 {
  71   return abs (a*b / gcd (a,b));
  72 }
  73
  74 void
  75 Rational::set_infinite (int s)
  76 {
  77   sign_ = ::sign (s) * 2;
  78 }
  79
  80 Rational
  81 Rational::operator - () const
  82 {
  83   Rational r(*this);
  84   r.negate ();
  85   return r;
  86 }
  87
  88 Rational
  89 Rational::div_rat (Rational div) const
  90 {
  91   Rational r (*this);
  92   r /= div;
  93   return r.trunc_rat ();
  94 }
  95
  96 Rational
  97 Rational::mod_rat (Rational div) const
  98 {
  99   Rational r (*this);
 100   r = (r / div - r.div_rat (div)) * div;
 101   return r;
 102 }
 103
 104 void
 105 Rational::normalise ()
 106 {
 107   if (!sign_)
 108     {
 109       den_ = 1;
 110       num_ = 0;
 111       return ;
 112     }
 113   if (!den_)
 114     sign_ = 2;
 115   if (!num_)
 116     sign_ = 0;
 117
 118   int g = gcd (num_ , den_);
 119
 120   num_ /= g;
 121   den_ /= g;
 122 }
 123
 124 int
 125 Rational::sign () const
 126 {
 127   return ::sign (sign_);
 128 }
 129
 130 bool
 131 Rational::infty_b () const
 132 {
 133   return abs (sign_) > 1;
 134 }
 135
 136 int
 137 Rational::compare (Rational const &r, Rational const &s)
 138 {
 139   if (r.sign_ < s.sign_)
 140     return -1;
 141   else if (r.sign_ > s.sign_)
 142     return 1;
 143   else if (r.infty_b ())
 144     return 0;
 145
 146   return  (r - s).sign ();
 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 (infty_b ())
 166     ;
 167   else if (r.infty_b ())
 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 /*
 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
 226 void
 227 Rational::invert ()
 228 {
 229   int r (num_);
 230   num_  = den_;
 231   den_ = r;
 232 }
 233
 234 Rational &
 235 Rational::operator *= (Rational r)
 236 {
 237   sign_ *= ::sign (r.sign_);
 238   if (r.infty_b ())
 239     {
 240       sign_ = sign () * 2;
 241       goto exit_func;
 242     }
 243
 244   num_ *= r.num_;
 245   den_ *= r.den_;
 246
 247   normalise ();
 248  exit_func:
 249   return *this;
 250 }
 251
 252 Rational &
 253 Rational::operator /= (Rational r)
 254 {
 255   r.invert ();
 256   return (*this *= r);
 257 }
 258
 259 void
 260 Rational::negate ()
 261 {
 262   sign_ *= -1;
 263 }
 264
 265 Rational&
 266 Rational::operator -= (Rational r)
 267 {
 268   r.negate ();
 269   return (*this += r);
 270 }
 271
 272 /*
 273   be paranoid about overiding libg++ stuff
 274  */
 275 Rational &
 276 Rational::operator = (Rational const &r)
 277 {
 278   copy (r);
 279   return *this;
 280 }
 281
 282 String
 283 Rational::str () const
 284 {
 285   if (infty_b ())
 286     {
 287       String s (sign_ > 0 ? "" : "-" );
 288       return String (s + "infinity");
 289     }
 290   String s = to_str (num ());
 291   if (den () != 1 && num ())
 292     s += "/" + to_str (den ());
 293   return s;
 294 }
 295
 296 int
 297 sign (Rational r)
 298 {
 299   return r.sign ();
 300 }