flower/rational.cc

   1 /*
   2   rational.cc -- implement Rational
   3
   4   source file of the Flower Library
   5
   6   (c) 1997--2004 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.string ();
  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 #if 0
  70 static
  71 int lcm (int a, int b)
  72 {
  73   return abs (a*b / gcd (a,b));
  74 }
  75 #endif
  76
  77 void
  78 Rational::set_infinite (int s)
  79 {
  80   sign_ = ::sign (s) * 2;
  81 }
  82
  83 Rational
  84 Rational::operator - () const
  85 {
  86   Rational r (*this);
  87   r.negate ();
  88   return r;
  89 }
  90
  91 Rational
  92 Rational::div_rat (Rational div) const
  93 {
  94   Rational r (*this);
  95   r /= div;
  96   return r.trunc_rat ();
  97 }
  98
  99 Rational
 100 Rational::mod_rat (Rational div) const
 101 {
 102   Rational r (*this);
 103   r = (r / div - r.div_rat (div)) * div;
 104   return r;
 105 }
 106
 107 void
 108 Rational::normalise ()
 109 {
 110   if (!sign_)
 111     {
 112       den_ = 1;
 113       num_ = 0;
 114     }
 115   else if (!den_)
 116     {
 117       sign_ = 2;
 118       num_ = 1;
 119     }
 120   else if (!num_)
 121     {
 122       sign_ = 0;
 123       den_ = 1;
 124     }
 125   else
 126     {
 127       int g = gcd (num_ , den_);
 128
 129       num_ /= g;
 130       den_ /= g;
 131     }
 132 }
 133 int
 134 Rational::sign () const
 135 {
 136   return ::sign (sign_);
 137 }
 138
 139 int
 140 Rational::compare (Rational const &r, Rational const &s)
 141 {
 142   if (r.sign_ < s.sign_)
 143     return -1;
 144   else if (r.sign_ > s.sign_)
 145     return 1;
 146   else if (r.is_infinity ())
 147     return 0;
 148   else if (r.sign_ == 0)
 149     return 0;
 150   else
 151     {
 152       return r.sign_ * ::sign  (int (r.num_ * s.den_) - int (s.num_ * r.den_));
 153     }
 154 }
 155
 156 int
 157 compare (Rational const &r, Rational const &s)
 158 {
 159   return Rational::compare (r, s );
 160 }
 161
 162 Rational &
 163 Rational::operator %= (Rational r)
 164 {
 165   *this = r.mod_rat (r);
 166   return *this;
 167 }
 168
 169 Rational &
 170 Rational::operator += (Rational r)
 171 {
 172   if (is_infinity ())
 173     ;
 174   else if (r.is_infinity ())
 175     {
 176       *this = r;
 177     }
 178   else
 179     {
 180       int n = sign_ * num_ *r.den_ + r.sign_ * den_ * r.num_;
 181       int d = den_ * r.den_;
 182       sign_ =  ::sign (n) * ::sign (d);
 183       num_ = abs (n);
 184       den_ = abs (d);
 185       normalise ();
 186     }
 187   return *this;
 188 }
 189
 190
 191 /*
 192   copied from libg++ 2.8.0
 193  */
 194 Rational::Rational (double x)
 195 {
 196   if (x != 0.0)
 197     {
 198       sign_ = ::sign (x);
 199       x *= sign_;
 200
 201       int expt;
 202       double mantissa = frexp (x, &expt);
 203
 204       const int FACT = 1 << 20;
 205
 206       /*
 207         Thanks to Afie for this too simple  idea.
 208
 209         do not blindly substitute by libg++ code, since that uses
 210         arbitrary-size integers.  The rationals would overflow too
 211         easily.
 212       */
 213
 214       num_ = (unsigned int) (mantissa * FACT);
 215       den_ = (unsigned int) FACT;
 216       normalise ();
 217       if (expt < 0)
 218         den_ <<= -expt;
 219       else
 220         num_ <<= expt;
 221       normalise ();
 222     }
 223   else
 224     {
 225       num_ = 0;
 226       den_ = 1;
 227       sign_ =0;
 228       normalise ();
 229     }
 230 }
 231
 232
 233 void
 234 Rational::invert ()
 235 {
 236   int r (num_);
 237   num_  = den_;
 238   den_ = r;
 239 }
 240
 241 Rational &
 242 Rational::operator *= (Rational r)
 243 {
 244   sign_ *= ::sign (r.sign_);
 245   if (r.is_infinity ())
 246     {
 247       sign_ = sign () * 2;
 248       goto exit_func;
 249     }
 250
 251   num_ *= r.num_;
 252   den_ *= r.den_;
 253
 254   normalise ();
 255  exit_func:
 256   return *this;
 257 }
 258
 259 Rational &
 260 Rational::operator /= (Rational r)
 261 {
 262   r.invert ();
 263   return (*this *= r);
 264 }
 265
 266 void
 267 Rational::negate ()
 268 {
 269   sign_ *= -1;
 270 }
 271
 272 Rational&
 273 Rational::operator -= (Rational r)
 274 {
 275   r.negate ();
 276   return (*this += r);
 277 }
 278
 279 String
 280 Rational::to_string () const
 281 {
 282   if (is_infinity ())
 283     {
 284       String s (sign_ > 0 ? "" : "-" );
 285       return String (s + "infinity");
 286     }
 287
 288   String s = ::to_string (num ());
 289   if (den () != 1 && num ())
 290     s += "/" + ::to_string (den ());
 291   return s;
 292 }
 293
 294 int
 295 Rational::to_int () const
 296 {
 297   return num () / den ();
 298 }
 299
 300 int
 301 sign (Rational r)
 302 {
 303   return r.sign ();
 304 }
 305
 306 bool
 307 Rational::is_infinity () const
 308 {
 309   return sign_ == 2 || sign_ == -2;
 310 }