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       return r.sign_ * ::sign  (int (r.num_ * s.den_) - int (s.num_ * r.den_));
 148     }
 149 }
 150
 151 int
 152 compare (Rational const &r, Rational const &s)
 153 {
 154   return Rational::compare (r, s );
 155 }
 156
 157 Rational &
 158 Rational::operator %= (Rational r)
 159 {
 160   *this = r.mod_rat (r);
 161   return *this;
 162 }
 163
 164 Rational &
 165 Rational::operator += (Rational r)
 166 {
 167   if (infty_b ())
 168     ;
 169   else if (r.infty_b ())
 170     {
 171       *this = r;
 172     }
 173   else
 174     {
 175       int n = sign_ * num_ *r.den_ + r.sign_ * den_ * r.num_;
 176       int d = den_ * r.den_;
 177       sign_ =  ::sign (n) * ::sign (d);
 178       num_ = abs (n);
 179       den_ = abs (d);
 180       normalise ();
 181     }
 182   return *this;
 183 }
 184
 185
 186 /*
 187   copied from libg++ 2.8.0
 188  */
 189 Rational::Rational (double x)
 190 {
 191   if (x != 0.0)
 192     {
 193       sign_ = ::sign (x);
 194       x *= sign_;
 195
 196       int expt;
 197       double mantissa = frexp (x, &expt);
 198
 199       const int FACT = 1 << 20;
 200
 201       /*
 202         Thanks to Afie for this too simple  idea.
 203
 204         do not blindly substitute by libg++ code, since that uses
 205         arbitrary-size integers.  The rationals would overflow too
 206         easily.
 207       */
 208
 209       num_ = (unsigned int) (mantissa * FACT);
 210       den_ = (unsigned int) FACT;
 211       normalise ();
 212       if (expt < 0)
 213         den_ <<= -expt;
 214       else
 215         num_ <<= expt;
 216       normalise ();
 217     }
 218   else
 219     {
 220       num_ = 0;
 221       den_ = 1;
 222       sign_ =0;
 223       normalise ();
 224     }
 225 }
 226
 227
 228 void
 229 Rational::invert ()
 230 {
 231   int r (num_);
 232   num_  = den_;
 233   den_ = r;
 234 }
 235
 236 Rational &
 237 Rational::operator *= (Rational r)
 238 {
 239   sign_ *= ::sign (r.sign_);
 240   if (r.infty_b ())
 241     {
 242       sign_ = sign () * 2;
 243       goto exit_func;
 244     }
 245
 246   num_ *= r.num_;
 247   den_ *= r.den_;
 248
 249   normalise ();
 250  exit_func:
 251   return *this;
 252 }
 253
 254 Rational &
 255 Rational::operator /= (Rational r)
 256 {
 257   r.invert ();
 258   return (*this *= r);
 259 }
 260
 261 void
 262 Rational::negate ()
 263 {
 264   sign_ *= -1;
 265 }
 266
 267 Rational&
 268 Rational::operator -= (Rational r)
 269 {
 270   r.negate ();
 271   return (*this += r);
 272 }
 273
 274 /*
 275   be paranoid about overiding libg++ stuff
 276  */
 277 Rational &
 278 Rational::operator = (Rational const &r)
 279 {
 280   copy (r);
 281   return *this;
 282 }
 283
 284 String
 285 Rational::str () const
 286 {
 287   if (infty_b ())
 288     {
 289       String s (sign_ > 0 ? "" : "-" );
 290       return String (s + "infinity");
 291     }
 292   String s = to_str (num ());
 293   if (den () != 1 && num ())
 294     s += "/" + to_str (den ());
 295   return s;
 296 }
 297
 298 int
 299 Rational::to_int () const
 300 {
 301   return num () / den ();
 302 }
 303
 304 int
 305 sign (Rational r)
 306 {
 307   return r.sign ();
 308 }