# source:src/libcfa/rational.c@d1ab5331

Last change on this file since d1ab5331 was d1ab5331, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

add constructors to rational type

• 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 : Wed May  4 14:16:14 2016
14// Update Count     : 25
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
55void ?{}( Rational * r ) {
56    r{ 0, 1 };
57} // rational
58
59void ?{}( Rational * r, long int n ) {
60    r{ n, 1 };
61} // rational
62
63void ?{}( Rational * r, long int n, long int d ) {
64    long int t = simplify( &n, &d );                                    // simplify
65    r->numerator = n / t;
66        r->denominator = d / t;
67} // rational
68
69
70// getter/setter for numerator/denominator
71
72long int numerator( Rational r ) {
73    return r.numerator;
74} // numerator
75
76long int numerator( Rational r, long int n ) {
77    long int prev = r.numerator;
78    long int t = gcd( abs( n ), r.denominator );                // simplify
79    r.numerator = n / t;
80    r.denominator = r.denominator / t;
81    return prev;
82} // numerator
83
84long int denominator( Rational r ) {
85    return r.denominator;
86} // denominator
87
88long int denominator( Rational r, long int d ) {
89    long int prev = r.denominator;
90    long int t = simplify( &r.numerator, &d );                  // simplify
91    r.numerator = r.numerator / t;
92    r.denominator = d / t;
93    return prev;
94} // denominator
95
96
97// comparison
98
99int ?==?( Rational l, Rational r ) {
100    return l.numerator * r.denominator == l.denominator * r.numerator;
101} // ?==?
102
103int ?!=?( Rational l, Rational r ) {
104    return ! ( l == r );
105} // ?!=?
106
107int ?<?( Rational l, Rational r ) {
108    return l.numerator * r.denominator < l.denominator * r.numerator;
109} // ?<?
110
111int ?<=?( Rational l, Rational r ) {
112    return l < r || l == r;
113} // ?<=?
114
115int ?>?( Rational l, Rational r ) {
116    return ! ( l <= r );
117} // ?>?
118
119int ?>=?( Rational l, Rational r ) {
120    return ! ( l < r );
121} // ?>=?
122
123
124// arithmetic
125
126Rational -?( Rational r ) {
127        Rational t = { -r.numerator, r.denominator };
128    return t;
129} // -?
130
131Rational ?+?( Rational l, Rational r ) {
132    if ( l.denominator == r.denominator ) {                             // special case
133                Rational t = { l.numerator + r.numerator, l.denominator };
134                return t;
135    } else {
136                Rational t = { l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator };
137                return t;
138    } // if
139} // ?+?
140
141Rational ?-?( Rational l, Rational r ) {
142    if ( l.denominator == r.denominator ) {                             // special case
143                Rational t = { l.numerator - r.numerator, l.denominator };
144                return t;
145    } else {
146                Rational t = { l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator };
147                return t;
148    } // if
149} // ?-?
150
151Rational ?*?( Rational l, Rational r ) {
152    Rational t = { l.numerator * r.numerator, l.denominator * r.denominator };
153        return t;
154} // ?*?
155
156Rational ?/?( Rational l, Rational r ) {
157    if ( r.numerator < 0 ) {
158                r.numerator = -r.numerator;
159                r.denominator = -r.denominator;
160        } // if
161        Rational t = { l.numerator * r.denominator, l.denominator * r.numerator };
162    return t;
163} // ?/?
164
165
166// conversion
167
168double widen( Rational r ) {
169        return (double)r.numerator / (double)r.denominator;
170} // widen
171
172// https://rosettacode.org/wiki/Convert_decimal_number_to_rational#C
173Rational narrow( double f, long int md ) {
174        if ( md <= 1 ) {                                                                        // maximum fractional digits too small?
175                return (Rational){ f, 1};                                               // truncate fraction
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        return (Rational){ neg ? -h[1] : h[1], k[1] };
202} // narrow
203
204
205// I/O
206
207forall( dtype istype | istream( istype ) )
208istype * ?|?( istype *is, Rational *r ) {
209        long int t;
210    is | &(r->numerator) | &(r->denominator);
211        t = simplify( &(r->numerator), &(r->denominator) );
212    r->numerator /= t;
213    r->denominator /= t;
214    return is;
215} // ?|?
216
217forall( dtype ostype | ostream( ostype ) )
218ostype * ?|?( ostype *os, Rational r ) {
219    return os | r.numerator | '/' | r.denominator;
220} // ?|?
221
222// Local Variables: //
223// tab-width: 4 //
224// End: //
Note: See TracBrowser for help on using the repository browser.