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
   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 #ifdef STREAM_SUPPORT
  23 ostream &
  24 operator << (ostream &o, Rational r)
  25 {
  26   o <<  r.string ();
  27   return o;
  28 }
  29 #endif
  30
  31
  32 Rational
  33 Rational::trunc_rat () const
  34 {
  35   return Rational (num_ - (num_ % den_), den_);
  36 }
  37
  38 Rational::Rational ()
  39 {
  40   sign_ = 0;
  41   num_ = den_ = 1;
  42 }
  43
  44 Rational::Rational (int n, int d)
  45 {
  46   sign_ = ::sign (n) * ::sign (d);
  47   num_ = abs (n);
  48   den_ = abs (d);
  49   normalise ();
  50 }
  51
  52 Rational::Rational (int n)
  53 {
  54   sign_ = ::sign (n);
  55   num_ = abs (n);
  56   den_= 1;
  57 }
  58
  59 static inline
  60 int gcd (int a, int b)
  61 {
  62   int t;
  63   while ((t = a % b))
  64     {
  65       a = b;
  66       b = t;
  67     }
  68   return b;
  69 }
  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.is_infinity ())
 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 (is_infinity ())
 168     ;
 169   else if (r.is_infinity ())
 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.is_infinity ())
 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 String
 275 Rational::to_string () const
 276 {
 277   if (is_infinity ())
 278     {
 279       String s (sign_ > 0 ? "" : "-" );
 280       return String (s + "infinity");
 281     }
 282
 283   String s = ::to_string (num ());
 284   if (den () != 1 && num ())
 285     s += "/" + ::to_string (den ());
 286   return s;
 287 }
 288
 289 int
 290 Rational::to_int () const
 291 {
 292   return num () / den ();
 293 }
 294
 295 int
 296 sign (Rational r)
 297 {
 298   return r.sign ();
 299 }
 300
 301 bool
 302 Rational::is_infinity () const
 303 {
 304   return sign_ == 2 || sign_ == -2;
 305 }