flower/rational.cc

   1 /*
   2   rational.cc -- implement Rational
   3
   4   source file of the Flower Library
   5
   6   (c) 1997--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "rational.hh"
  10
  11 #include <cmath>
  12 #include <cstdlib>
  13
  14 #include "string-convert.hh"
  15 #include "libc-extension.hh"
  16
  17 Rational::operator double () const
  18 {
  19   return ((double)sign_) * num_ / den_;
  20 }
  21
  22 Rational::operator bool () const
  23 {
  24   return sign_ && num_;
  25 }
  26
  27 #ifdef STREAM_SUPPORT
  28 ostream &
  29 operator << (ostream &o, Rational r)
  30 {
  31   o << r.string ();
  32   return o;
  33 }
  34 #endif
  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 Rational::Rational (int n)
  57 {
  58   sign_ = ::sign (n);
  59   num_ = abs (n);
  60   den_ = 1;
  61 }
  62
  63 static inline
  64 int gcd (int a, int b)
  65 {
  66   int t;
  67   while ((t = a % b))
  68     {
  69       a = b;
  70       b = t;
  71     }
  72   return 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.is_infinity ())
 145     return 0;
 146   else if (r.sign_ == 0)
 147     return 0;
 148   return r.sign_ * ::sign (int (r.num_ * s.den_) - int (s.num_ * r.den_));
 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 = mod_rat (r);
 161   return *this;
 162 }
 163
 164 Rational &
 165 Rational::operator += (Rational r)
 166 {
 167   if (is_infinity ())
 168     ;
 169   else if (r.is_infinity ())
 170     *this = r;
 171   else
 172     {
 173       int lcm = (den_ / gcd (r.den_, den_)) * r.den_;
 174       int n = sign_ * num_ * (lcm / den_) + r.sign_ * r.num_ * (lcm / r.den_);
 175       int d = lcm;
 176       sign_ = ::sign (n) * ::sign (d);
 177       num_ = abs (n);
 178       den_ = abs (d);
 179       normalise ();
 180     }
 181   return *this;
 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 void
 226 Rational::invert ()
 227 {
 228   int r (num_);
 229   num_ = den_;
 230   den_ = r;
 231 }
 232
 233 Rational &
 234 Rational::operator *= (Rational r)
 235 {
 236   sign_ *= ::sign (r.sign_);
 237   if (r.is_infinity ())
 238     {
 239       sign_ = sign () * 2;
 240       goto exit_func;
 241     }
 242
 243   num_ *= r.num_;
 244   den_ *= r.den_;
 245
 246   normalise ();
 247  exit_func:
 248   return *this;
 249 }
 250
 251 Rational &
 252 Rational::operator /= (Rational r)
 253 {
 254   r.invert ();
 255   return (*this *= r);
 256 }
 257
 258 void
 259 Rational::negate ()
 260 {
 261   sign_ *= -1;
 262 }
 263
 264 Rational &
 265 Rational::operator -= (Rational r)
 266 {
 267   r.negate ();
 268   return (*this += r);
 269 }
 270
 271 String
 272 Rational::to_string () const
 273 {
 274   if (is_infinity ())
 275     {
 276       String s (sign_ > 0 ? "" : "-");
 277       return String (s + "infinity");
 278     }
 279
 280   String s = ::to_string (num ());
 281   if (den () != 1 && num ())
 282     s += "/" + ::to_string (den ());
 283   return s;
 284 }
 285
 286 int
 287 Rational::to_int () const
 288 {
 289   return num () / den ();
 290 }
 291
 292 int
 293 sign (Rational r)
 294 {
 295   return r.sign ();
 296 }
 297
 298 bool
 299 Rational::is_infinity () const
 300 {
 301   return sign_ == 2 || sign_ == -2;
 302 }