source: src/libcfa/rational.c @ 6e991d6

aaron-thesisarm-ehcleanup-dtorsctordeferred_resndemanglergc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newstringwith_gc
Last change on this file since 6e991d6 was 6e991d6, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

add -fgnu89-inline flag to compile, cleanup swap example I/O, stdlib fixes, start math library

  • Property mode set to 100644
File size: 5.5 KB
Line 
1//                               -*- Mode: C -*-
2//
3// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
4//
5// The contents of this file are covered under the licence agreement in the
6// file "LICENCE" distributed with Cforall.
7//
8// rational.c --
9//
10// Author           : Peter A. Buhr
11// Created On       : Wed Apr  6 17:54:28 2016
12// Last Modified By : Peter A. Buhr
13// Last Modified On : Thu Apr 21 07:33:03 2016
14// Update Count     : 22
15//
16
17#include "rational"
18#include "fstream"
19#include "stdlib"
20#include "math"                                                                                 // floor
21
22
23// constants
24
25struct Rational 0 = {0, 1};
26struct Rational 1 = {1, 1};
27
28
29// helper routines
30
31// Calculate greatest common denominator of two numbers, the first of which may be negative. Used to reduce rationals.
32// alternative: https://en.wikipedia.org/wiki/Binary_GCD_algorithm
33static long int gcd( long int a, long int b ) {
34    for ( ;; ) {                                                                                // Euclid's algorithm
35                long int r = a % b;
36          if ( r == 0 ) break;
37                a = b;
38                b = r;
39    } // for
40        return b;
41} // gcd
42
43static long int simplify( long int *n, long int *d ) {
44    if ( *d == 0 ) {
45                serr | "Invalid rational number construction: denominator cannot be equal to 0." | endl;
46                exit( EXIT_FAILURE );
47    } // exit
48    if ( *d < 0 ) { *d = -*d; *n = -*n; }                               // move sign to numerator
49    return gcd( abs( *n ), *d );                                                // simplify
50} // Rationalnumber::simplify
51
52
53// constructors
54
55Rational rational() {
56    return (Rational){ 0, 1 };
57} // rational
58
59Rational rational( long int n ) {
60    return (Rational){ n, 1 };
61} // rational
62
63Rational rational( long int n, long int d ) {
64    long int t = simplify( &n, &d );                                    // simplify
65    return (Rational){ n / t, d / t };
66} // rational
67
68
69// getter/setter for numerator/denominator
70
71long int numerator( Rational r ) {
72    return r.numerator;
73} // numerator
74
75long int numerator( Rational r, long int n ) {
76    long int prev = r.numerator;
77    long int t = gcd( abs( n ), r.denominator );                // simplify
78    r.numerator = n / t;
79    r.denominator = r.denominator / t;
80    return prev;
81} // numerator
82
83long int denominator( Rational r ) {
84    return r.denominator;
85} // denominator
86
87long int denominator( Rational r, long int d ) {
88    long int prev = r.denominator;
89    long int t = simplify( &r.numerator, &d );                  // simplify
90    r.numerator = r.numerator / t;
91    r.denominator = d / t;
92    return prev;
93} // denominator
94
95
96// comparison
97
98int ?==?( Rational l, Rational r ) {
99    return l.numerator * r.denominator == l.denominator * r.numerator;
100} // ?==?
101
102int ?!=?( Rational l, Rational r ) {
103    return ! ( l == r );
104} // ?!=?
105
106int ?<?( Rational l, Rational r ) {
107    return l.numerator * r.denominator < l.denominator * r.numerator;
108} // ?<?
109
110int ?<=?( Rational l, Rational r ) {
111    return l < r || l == r;
112} // ?<=?
113
114int ?>?( Rational l, Rational r ) {
115    return ! ( l <= r );
116} // ?>?
117
118int ?>=?( Rational l, Rational r ) {
119    return ! ( l < r );
120} // ?>=?
121
122
123// arithmetic
124
125Rational -?( Rational r ) {
126        Rational t = { -r.numerator, r.denominator };
127    return t;
128} // -?
129
130Rational ?+?( Rational l, Rational r ) {
131    if ( l.denominator == r.denominator ) {                             // special case
132                Rational t = { l.numerator + r.numerator, l.denominator };
133                return t;
134    } else {
135                Rational t = { l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator };
136                return t;
137    } // if
138} // ?+?
139
140Rational ?-?( Rational l, Rational r ) {
141    if ( l.denominator == r.denominator ) {                             // special case
142                Rational t = { l.numerator - r.numerator, l.denominator };
143                return t;
144    } else {
145                Rational t = { l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator };
146                return t;
147    } // if
148} // ?-?
149
150Rational ?*?( Rational l, Rational r ) {
151    Rational t = { l.numerator * r.numerator, l.denominator * r.denominator };
152        return t;
153} // ?*?
154
155Rational ?/?( Rational l, Rational r ) {
156    if ( r.numerator < 0 ) {
157                r.numerator = -r.numerator;
158                r.denominator = -r.denominator;
159        } // if
160        Rational t = { l.numerator * r.denominator, l.denominator * r.numerator };
161    return t;
162} // ?/?
163
164
165// conversion
166
167double widen( Rational r ) {
168        return (double)r.numerator / (double)r.denominator;
169} // widen
170
171// https://rosettacode.org/wiki/Convert_decimal_number_to_rational#C
172Rational narrow( double f, long int md ) {
173        if ( md <= 1 ) {                                                                        // maximum fractional digits too small?
174                Rational t = rational( f, 1 );                                  // truncate fraction
175                return t;
176        } // if
177
178        // continued fraction coefficients
179        long int a, h[3] = { 0, 1, 0 }, k[3] = { 1, 0, 0 };
180        long int x, d, n = 1;
181        int i, neg = 0;
182 
183        if ( f < 0 ) { neg = 1; f = -f; }
184        while ( f != floor( f ) ) { n <<= 1; f *= 2; }
185        d = f;
186 
187        // continued fraction and check denominator each step
188        for (i = 0; i < 64; i++) {
189                a = n ? d / n : 0;
190          if (i && !a) break;
191                x = d; d = n; n = x % n;
192                x = a;
193                if (k[1] * a + k[0] >= md) {
194                        x = (md - k[0]) / k[1];
195                  if ( ! (x * 2 >= a || k[1] >= md) ) break;
196                        i = 65;
197                } // if
198                h[2] = x * h[1] + h[0]; h[0] = h[1]; h[1] = h[2];
199                k[2] = x * k[1] + k[0]; k[0] = k[1]; k[1] = k[2];
200        } // for
201        Rational t = rational( neg ? -h[1] : h[1], k[1] );
202        return t;
203} // narrow
204
205
206// I/O
207
208forall( dtype istype | istream( istype ) )
209istype * ?|?( istype *is, Rational *r ) {
210        long int t;
211    is | &(r->numerator) | &(r->denominator);
212        t = simplify( &(r->numerator), &(r->denominator) );
213    r->numerator /= t;
214    r->denominator /= t;
215    return is;
216} // ?|?
217
218forall( dtype ostype | ostream( ostype ) )
219ostype * ?|?( ostype *os, Rational r ) {
220    return os | r.numerator | '/' | r.denominator;
221} // ?|?
222
223// Local Variables: //
224// tab-width: 4 //
225// End: //
Note: See TracBrowser for help on using the repository browser.