home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / nihcl-3.0 / lib / Fraction.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-19  |  5.6 KB  |  259 lines
  1. /* Fraction.c -- implementation of fractions
  2.  
  3.     THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
  4.     "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
  5.     AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
  6.     CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
  7.     PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
  8.     RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
  9.  
  10. Author:
  11.     K. E. Gorlen
  12.     Bg. 12A, Rm. 2033
  13.     Computer Systems Laboratory
  14.     Division of Computer Research and Technology
  15.     National Institutes of Health
  16.     Bethesda, Maryland 20892
  17.     Phone: (301) 496-1111
  18.     uucp: uunet!nih-csl!kgorlen
  19.     Internet: kgorlen@alw.nih.gov
  20.     December, 1985
  21.  
  22. Function:
  23.     
  24. Implements a fraction as two integers, the numerator and the
  25. denominator.  WARNING -- this implementation is not suitable for serious
  26. numeric applications.  Reference: Knuth, "The Art of Computer
  27. Programming", Vol. 2, Section 4.5.
  28.  
  29. $Log:    Fraction.c,v $
  30.  * Revision 3.0  90/05/20  00:19:38  kgorlen
  31.  * Release for 1st edition.
  32.  * 
  33. */
  34.  
  35. #include "Fraction.h"
  36. #include <libc.h>
  37. #include <math.h>
  38. #include "nihclIO.h"
  39.  
  40. #define    THIS    Fraction
  41. #define    BASE    Object
  42. #define BASE_CLASSES BASE::desc()
  43. #define MEMBER_CLASSES
  44. #define VIRTUAL_BASE_CLASSES Object::desc()
  45.  
  46. DEFINE_CLASS(Fraction,1,"$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/Fraction.c,v 3.0 90/05/20 00:19:38 kgorlen Rel $",NULL,NULL);
  47.  
  48. extern const int NIHCL_ZERODEN,NIHCL_FCTNOV,NIHCL_FCTNUN;
  49.  
  50. int Fraction::gcd(int uu, int vv)
  51. /* gcd -- binary greatest common divisor algorithm
  52.  
  53. Algorithm B, p. 321.
  54.  
  55. */
  56. {
  57.     register int u=ABS(uu), v=ABS(vv);
  58.     register int k=0;
  59.     register int t;
  60.     if (u == 0) return v;
  61.     if (v == 0) return u;
  62.     while ((u&1) == 0 && (v&1) == 0) { u>>=1; v>>=1; k++; }
  63.     if (u&1) { t = -v; goto B4; }
  64.     else t = u;
  65.     do {
  66. B3:        t/=2;
  67. B4:        if ((t&1) == 0) goto B3;
  68.         if (t>0) u = t;
  69.         else v = -t;
  70.         t = u-v;
  71.     } while (t != 0);
  72.     return u<<k;
  73. }
  74.  
  75. Fraction::Fraction(int num, int den)
  76. /*
  77.     Construct a Fraction from the specified numerator and denominator.
  78. */
  79. {
  80.     n = num; d = den;
  81.     if (d == 0) setError(NIHCL_ZERODEN,DEFAULT,this,num,den);
  82.     if (n == 0) { d = 1; return; }
  83.     if (d < 0) { n = -n; d = -d; }
  84.     reduce();
  85. }
  86.  
  87. inline char* gcvt(double val, int dig, char* buf)
  88. {
  89.     sprintf(buf,"%*.lg",dig,val);
  90.     return buf;
  91. }
  92.  
  93. Fraction::Fraction(double x)
  94. /*
  95.     Construct a Fraction from a double.
  96. */
  97. {
  98.     char buf[20];
  99.     int exp;
  100.     double m = frexp(x,&exp);
  101.     register int k;
  102.     if (exp>=0) {
  103.         if (exp > (sizeof(int)*8-2)) setError(NIHCL_FCTNOV,DEFAULT,this,gcvt(x,20,buf));
  104.         k = (sizeof(int)*8-2);
  105.     }
  106.     else {
  107.         k = exp+(sizeof(int)*8-2);
  108.         if (k < 0) setError(NIHCL_FCTNUN,DEFAULT,this,gcvt(x,20,buf));
  109.     }
  110.     n = (int)(m*(1<<k));
  111.     d = 1 << (k-exp);
  112.     reduce();
  113. }
  114.  
  115. void Fraction::parseFraction(istream& strm)
  116. /*
  117.     Read a Fraction from an istream.
  118. */
  119. {
  120.     n = 0; d = 1;
  121.     strm >> n;
  122.     char slash;
  123.     strm >> slash;
  124.     if (slash == '/') {
  125.         strm >> d;
  126.         reduce();
  127.     }
  128.     else strm.putback(slash);
  129. }
  130.  
  131. Fraction::Fraction(istream& strm)    { parseFraction(strm); }
  132.  
  133. void Fraction::reduce()
  134. /*
  135.     Reduce a Fraction to lowest terms by dividing the numerator and
  136.     denominator by their gcd.
  137. */
  138. {
  139.     register int d1 = gcd(n,d);
  140.     if (d1 == 1) return;
  141.     n /= d1; d /= d1;
  142. }
  143.  
  144. Fraction operator+(const Fraction& u, const Fraction& v)
  145. {
  146.     register int d1 = Fraction::gcd(u.d,v.d);
  147.     if (d1 == 1) return Fraction(u.n*v.d+u.d*v.n, u.d*v.d, 0);
  148.     register int t = u.n*(v.d/d1) + v.n*(u.d/d1);
  149.     register int d2 = Fraction::gcd(t,d1);
  150.     return Fraction(t/d2, (u.d/d1)*(v.d/d2), 0);
  151. }
  152.  
  153. Fraction operator-(const Fraction& u, const Fraction& v)
  154. {
  155.     register int d1 = Fraction::gcd(u.d,v.d);
  156.     if (d1 == 1) return Fraction(u.n*v.d-u.d*v.n, u.d*v.d, 0);
  157.     register int t = u.n*(v.d/d1) - v.n*(u.d/d1);
  158.     register int d2 = Fraction::gcd(t,d1);
  159.     return Fraction(t/d2, (u.d/d1)*(v.d/d2), 0);
  160. }
  161.  
  162. bool operator<(const Fraction& u, const Fraction& v)
  163. {
  164.     register int d1 = Fraction::gcd(u.d,v.d);
  165.     if (d1 == 1) return u.n*v.d < u.d*v.n;
  166.     return u.n*(v.d/d1) < v.n*(u.d/d1);
  167. }
  168.  
  169. bool operator<=(const Fraction& u, const Fraction& v)
  170. {
  171.     if (u==v) return YES;
  172.     return u<v;
  173. }
  174.  
  175. Fraction operator*(const Fraction& u, const Fraction& v)
  176. {
  177.     register int d1 = Fraction::gcd(u.n, v.d);
  178.     register int d2 = Fraction::gcd(u.d, v.n);
  179.     return Fraction((u.n/d1)*(v.n/d2), (u.d/d2)*(v.d/d1), 0);
  180. }
  181.  
  182. Fraction operator/(const Fraction& u, const Fraction& v)
  183. {
  184.     if (v.n < 0) return u*Fraction(-v.d,-v.n, 0);
  185.     return u*Fraction(v.d,v.n,0);
  186. }
  187.  
  188. bool Fraction::between(const Fraction& min, const Fraction& max) const
  189. /*
  190.     Return YES if this Fraction is <= to max and >= to min.
  191. */
  192. {
  193.     return *this >= min && *this <= max;
  194. }
  195.  
  196. Fraction Fraction::max(const Fraction& f) const
  197. {
  198.     if (f < *this) return *this;
  199.     else return f;
  200. }
  201.  
  202. Fraction Fraction::min(const Fraction& f) const
  203. {
  204.     if (f > *this) return *this;
  205.     else return f;
  206. }
  207.  
  208. unsigned Fraction::hash() const    { return n^d; }
  209.  
  210. bool Fraction::isEqual(const Object& ob) const
  211. {
  212.     return ob.isSpecies(classDesc) && *this==castdown(ob);
  213. }
  214.  
  215. const Class* Fraction::species() const { return &classDesc; }
  216.  
  217. int Fraction::compare(const Object& ob) const
  218. {
  219.     assertArgSpecies(ob,classDesc,"compare");
  220.     const Fraction& f = castdown(ob);
  221.     if (*this == f) return 0;
  222.     if (*this < f) return -1;
  223.     return 1;
  224. }
  225.  
  226. void Fraction::deepenShallowCopy()    {}
  227.  
  228. void Fraction::printOn(ostream& strm) const
  229. {
  230.     if (n == 0 || d == 1) strm << n;
  231.     else strm << n << '/' << d;
  232. }
  233.  
  234. void Fraction::scanFrom(istream& strm)    { parseFraction(strm); }
  235.  
  236. Fraction::Fraction(OIOin& strm)
  237.     : BASE(strm)
  238. {
  239.     strm >> n >> d;
  240. }
  241.  
  242. void Fraction::storer(OIOout& strm) const
  243. {
  244.     BASE::storer(strm);
  245.     strm << n << d;
  246. }
  247.  
  248. Fraction::Fraction(OIOifd& fd)
  249.     : BASE(fd)
  250. {
  251.     fd >> n >> d;
  252. }
  253.  
  254. void Fraction::storer(OIOofd& fd) const
  255. {
  256.     BASE::storer(fd);
  257.     fd << n << d;
  258. }
  259.