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 bool () const
  16 {
  17   return sign_;
  18 }
  19
  20 Rational::operator int () const
  21 {
  22   return sign_ * num_ / den_;
  23 }
  24
  25 Rational::operator double () const
  26 {
  27   return (double)sign_ * num_ / den_;
  28 }
  29
  30 ostream &
  31 operator << (ostream &o, Rational r)
  32 {
  33   o <<  r.str ();
  34   return o;
  35 }
  36
  37 Rational
  38 Rational::trunc_rat () const
  39 {
  40   return Rational (num_ - (num_ % den_), den_);
  41 }
  42
  43 Rational::Rational ()
  44 {
  45   sign_ = 0;
  46   num_ = den_ = 1;
  47 }
  48
  49 Rational::Rational (int n, int d)
  50 {
  51   sign_ = ::sign (n) * ::sign (d);
  52   num_ = abs (n);
  53   den_ = abs (d);
  54   normalise ();
  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       return ;
 113     }
 114   if (!den_)
 115     sign_ = 2;
 116   if (!num_)
 117     sign_ = 0;
 118
 119   int g = gcd (num_ , den_);
 120
 121   num_ /= g;
 122   den_ /= g;
 123 }
 124
 125 int
 126 Rational::sign () const
 127 {
 128   return ::sign (sign_);
 129 }
 130
 131 bool
 132 Rational::infty_b () const
 133 {
 134   return abs (sign_) > 1;
 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
 147   return (r - s).sign ();
 148 }
 149
 150 int
 151 compare (Rational const &r, Rational const &s)
 152 {
 153   return Rational::compare (r, s );
 154 }
 155
 156 Rational &
 157 Rational::operator %= (Rational r)
 158 {
 159   *this = r.mod_rat (r);
 160   return *this;
 161 }
 162
 163 Rational &
 164 Rational::operator += (Rational r)
 165 {
 166   if (infty_b ())
 167     ;
 168   else if (r.infty_b ())
 169     {
 170       *this = r;
 171     }
 172   else
 173     {
 174       int n = sign_ * num_ *r.den_ + r.sign_ * den_ * r.num_;
 175       int d = den_ * r.den_;
 176       sign_ =  ::sign (n) * ::sign (d);
 177       num_ = abs (n);
 178       den_ = abs (d);
 179       normalise ();
 180     }
 181   return *this;
 182 }
 183
 184
 185 /*
 186   copied from libg++ 2.8.0
 187  */
 188 Rational::Rational (double x)
 189 {
 190   if (x != 0.0)
 191     {
 192       sign_ = ::sign (x);
 193       x *= sign_;
 194
 195       int expt;
 196       double mantissa = frexp (x, &expt);
 197
 198       const int FACT = 1 << 20;
 199
 200       /*
 201         Thanks to Afie for this too simple  idea.
 202
 203         do not blindly substitute by libg++ code, since that uses
 204         arbitrary-size integers.  The rationals would overflow too
 205         easily.
 206       */
 207
 208       num_ = (unsigned int) (mantissa * FACT);
 209       den_ = (unsigned int) FACT;
 210       normalise ();
 211       if (expt < 0)
 212         den_ <<= -expt;
 213       else
 214         num_ <<= expt;
 215       normalise ();
 216     }
 217   else
 218     {
 219       num_ = 0;
 220       den_ = 1;
 221       sign_ =0;
 222       normalise ();
 223     }
 224 }
 225
 226
 227 void
 228 Rational::invert ()
 229 {
 230   int r (num_);
 231   num_  = den_;
 232   den_ = r;
 233 }
 234
 235 Rational &
 236 Rational::operator *= (Rational r)
 237 {
 238   sign_ *= ::sign (r.sign_);
 239   if (r.infty_b ())
 240     {
 241       sign_ = sign () * 2;
 242       goto exit_func;
 243     }
 244
 245   num_ *= r.num_;
 246   den_ *= r.den_;
 247
 248   normalise ();
 249  exit_func:
 250   return *this;
 251 }
 252
 253 Rational &
 254 Rational::operator /= (Rational r)
 255 {
 256   r.invert ();
 257   return (*this *= r);
 258 }
 259
 260 void
 261 Rational::negate ()
 262 {
 263   sign_ *= -1;
 264 }
 265
 266 Rational&
 267 Rational::operator -= (Rational r)
 268 {
 269   r.negate ();
 270   return (*this += r);
 271 }
 272
 273 /*
 274   be paranoid about overiding libg++ stuff
 275  */
 276 Rational &
 277 Rational::operator = (Rational const &r)
 278 {
 279   copy (r);
 280   return *this;
 281 }
 282
 283 String
 284 Rational::str () const
 285 {
 286   if (infty_b ())
 287     {
 288       String s (sign_ > 0 ? "" : "-" );
 289       return String (s + "infinity");
 290     }
 291   String s = to_str (num ());
 292   if (den () != 1 && num ())
 293     s += "/" + to_str (den ());
 294   return s;
 295 }
 296
 297 int
 298 sign (Rational r)
 299 {
 300   return r.sign ();
 301 }