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@xs4all.nl>
   7 */
   8
   9 #include "rational.hh"
  10
  11 #include <cmath>
  12 #include <cstdlib>
  13 using namespace std;
  14
  15 #include "string-convert.hh"
  16 #include "libc-extension.hh"
  17
  18 Rational::operator double () const
  19 {
  20   return ((double)sign_) * num_ / den_;
  21 }
  22
  23 Rational::operator bool () const
  24 {
  25   return sign_ && num_;
  26 }
  27
  28 #ifdef STREAM_SUPPORT
  29 ostream &
  30 operator << (ostream &o, Rational r)
  31 {
  32   o << r.string ();
  33   return o;
  34 }
  35 #endif
  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 Rational::Rational (int n)
  58 {
  59   sign_ = ::sign (n);
  60   num_ = abs (n);
  61   den_ = 1;
  62 }
  63
  64 static inline
  65 int gcd (int a, int b)
  66 {
  67   int t;
  68   while ((t = a % b))
  69     {
  70       a = b;
  71       b = t;
  72     }
  73   return b;
  74 }
  75
  76 void
  77 Rational::set_infinite (int s)
  78 {
  79   sign_ = ::sign (s) * 2;
  80 }
  81
  82 Rational
  83 Rational::operator - () const
  84 {
  85   Rational r (*this);
  86   r.negate ();
  87   return r;
  88 }
  89
  90 Rational
  91 Rational::div_rat (Rational div) const
  92 {
  93   Rational r (*this);
  94   r /= div;
  95   return r.trunc_rat ();
  96 }
  97
  98 Rational
  99 Rational::mod_rat (Rational div) const
 100 {
 101   Rational r (*this);
 102   r = (r / div - r.div_rat (div)) * div;
 103   return r;
 104 }
 105
 106 void
 107 Rational::normalise ()
 108 {
 109   if (!sign_)
 110     {
 111       den_ = 1;
 112       num_ = 0;
 113     }
 114   else if (!den_)
 115     {
 116       sign_ = 2;
 117       num_ = 1;
 118     }
 119   else if (!num_)
 120     {
 121       sign_ = 0;
 122       den_ = 1;
 123     }
 124   else
 125     {
 126       int g = gcd (num_, den_);
 127
 128       num_ /= g;
 129       den_ /= g;
 130     }
 131 }
 132 int
 133 Rational::sign () const
 134 {
 135   return ::sign (sign_);
 136 }
 137
 138 int
 139 Rational::compare (Rational const &r, Rational const &s)
 140 {
 141   if (r.sign_ < s.sign_)
 142     return -1;
 143   else if (r.sign_ > s.sign_)
 144     return 1;
 145   else if (r.is_infinity ())
 146     return 0;
 147   else if (r.sign_ == 0)
 148     return 0;
 149   return r.sign_ * ::sign (int (r.num_ * s.den_) - int (s.num_ * r.den_));
 150 }
 151
 152 int
 153 compare (Rational const &r, Rational const &s)
 154 {
 155   return Rational::compare (r, s);
 156 }
 157
 158 Rational &
 159 Rational::operator %= (Rational r)
 160 {
 161   *this = mod_rat (r);
 162   return *this;
 163 }
 164
 165 Rational &
 166 Rational::operator += (Rational r)
 167 {
 168   if (is_infinity ())
 169     ;
 170   else if (r.is_infinity ())
 171     *this = r;
 172   else
 173     {
 174       int lcm = (den_ / gcd (r.den_, den_)) * r.den_;
 175       int n = sign_ * num_ * (lcm / den_) + r.sign_ * r.num_ * (lcm / r.den_);
 176       int d = lcm;
 177       sign_ = ::sign (n) * ::sign (d);
 178       num_ = abs (n);
 179       den_ = abs (d);
 180       normalise ();
 181     }
 182   return *this;
 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 void
 227 Rational::invert ()
 228 {
 229   int r (num_);
 230   num_ = den_;
 231   den_ = r;
 232 }
 233
 234 Rational &
 235 Rational::operator *= (Rational r)
 236 {
 237   sign_ *= ::sign (r.sign_);
 238   if (r.is_infinity ())
 239     {
 240       sign_ = sign () * 2;
 241       goto exit_func;
 242     }
 243
 244   num_ *= r.num_;
 245   den_ *= r.den_;
 246
 247   normalise ();
 248  exit_func:
 249   return *this;
 250 }
 251
 252 Rational &
 253 Rational::operator /= (Rational r)
 254 {
 255   r.invert ();
 256   return (*this *= r);
 257 }
 258
 259 void
 260 Rational::negate ()
 261 {
 262   sign_ *= -1;
 263 }
 264
 265 Rational &
 266 Rational::operator -= (Rational r)
 267 {
 268   r.negate ();
 269   return (*this += r);
 270 }
 271
 272 String
 273 Rational::to_string () const
 274 {
 275   if (is_infinity ())
 276     {
 277       String s (sign_ > 0 ? "" : "-");
 278       return String (s + "infinity");
 279     }
 280
 281   String s = ::to_string (num ());
 282   if (den () != 1 && num ())
 283     s += "/" + ::to_string (den ());
 284   return s;
 285 }
 286
 287 int
 288 Rational::to_int () const
 289 {
 290   return (int) num () / den ();
 291 }
 292
 293 int
 294 sign (Rational r)
 295 {
 296   return r.sign ();
 297 }
 298
 299 bool
 300 Rational::is_infinity () const
 301 {
 302   return sign_ == 2 || sign_ == -2;
 303 }