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