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 #ifdef STREAM_SUPPORT
  21 ostream &
  22 operator << (ostream &o, Rational r)
  23 {
  24   o <<  r.str ();
  25   return o;
  26 }
  27 #endif
  28
  29
  30 Rational
  31 Rational::trunc_rat () const
  32 {
  33   return Rational (num_ - (num_ % den_), den_);
  34 }
  35
  36 Rational::Rational ()
  37 {
  38   sign_ = 0;
  39   num_ = den_ = 1;
  40 }
  41
  42 Rational::Rational (int n, int d)
  43 {
  44   sign_ = ::sign (n) * ::sign (d);
  45   num_ = abs (n);
  46   den_ = abs (d);
  47   normalise ();
  48 }
  49
  50 Rational::Rational (int n)
  51 {
  52   sign_ = ::sign (n);
  53   num_ = abs (n);
  54   den_= 1;
  55 }
  56
  57 static
  58 int gcd (int a, int b)
  59 {
  60   int t;
  61   while ((t = a % b))
  62     {
  63       a = b;
  64       b = t;
  65     }
  66   return b;
  67 }
  68
  69 static
  70 int lcm (int a, int b)
  71 {
  72   return abs (a*b / gcd (a,b));
  73 }
  74
  75 void
  76 Rational::set_infinite (int s)
  77 {
  78   sign_ = ::sign (s) * 2;
  79 }
  80
  81 Rational
  82 Rational::operator - () const
  83 {
  84   Rational r (*this);
  85   r.negate ();
  86   return r;
  87 }
  88
  89 Rational
  90 Rational::div_rat (Rational div) const
  91 {
  92   Rational r (*this);
  93   r /= div;
  94   return r.trunc_rat ();
  95 }
  96
  97 Rational
  98 Rational::mod_rat (Rational div) const
  99 {
 100   Rational r (*this);
 101   r = (r / div - r.div_rat (div)) * div;
 102   return r;
 103 }
 104
 105 void
 106 Rational::normalise ()
 107 {
 108   if (!sign_)
 109     {
 110       den_ = 1;
 111       num_ = 0;
 112     }
 113   else if (!den_)
 114     {
 115       sign_ = 2;
 116       num_ = 1;
 117     }
 118   else if (!num_)
 119     {
 120       sign_ = 0;
 121       den_ = 1;
 122     }
 123   else
 124     {
 125       int g = gcd (num_ , den_);
 126
 127       num_ /= g;
 128       den_ /= g;
 129     }
 130 }
 131 int
 132 Rational::sign () const
 133 {
 134   return ::sign (sign_);
 135 }
 136
 137 int
 138 Rational::compare (Rational const &r, Rational const &s)
 139 {
 140   if (r.sign_ < s.sign_)
 141     return -1;
 142   else if (r.sign_ > s.sign_)
 143     return 1;
 144   else if (r.infty_b ())
 145     return 0;
 146   else if (r.sign_ == 0)
 147     return 0;
 148   else
 149     {
 150       return r.sign_ * ::sign  (int (r.num_ * s.den_) - int (s.num_ * r.den_));
 151     }
 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 String
 278 Rational::str () const
 279 {
 280   if (infty_b ())
 281     {
 282       String s (sign_ > 0 ? "" : "-" );
 283       return String (s + "infinity");
 284     }
 285   String s = to_str (num ());
 286   if (den () != 1 && num ())
 287     s += "/" + to_str (den ());
 288   return s;
 289 }
 290
 291 int
 292 Rational::to_int () const
 293 {
 294   return num () / den ();
 295 }
 296
 297 int
 298 sign (Rational r)
 299 {
 300   return r.sign ();
 301 }