Changeset 5dc4c7e for libcfa/src/rational.cfa
- Timestamp:
- Jul 20, 2021, 6:30:29 PM (3 years ago)
- Branches:
- ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- d30804a
- Parents:
- 8477fc4
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/rational.cfa
r8477fc4 r5dc4c7e 10 10 // Created On : Wed Apr 6 17:54:28 2016 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sat Feb 8 17:56:36 202013 // Update Count : 1 8712 // Last Modified On : Tue Jul 20 16:30:06 2021 13 // Update Count : 193 14 14 // 15 15 … … 18 18 #include "stdlib.hfa" 19 19 20 forall( RationalImpl | arithmetic( RationalImpl) ) {20 forall( T | Arithmetic( T ) ) { 21 21 // helper routines 22 22 23 23 // Calculate greatest common denominator of two numbers, the first of which may be negative. Used to reduce 24 24 // rationals. alternative: https://en.wikipedia.org/wiki/Binary_GCD_algorithm 25 static RationalImpl gcd( RationalImpl a, RationalImplb ) {25 static T gcd( T a, T b ) { 26 26 for ( ;; ) { // Euclid's algorithm 27 RationalImplr = a % b;28 if ( r == ( RationalImpl){0} ) break;27 T r = a % b; 28 if ( r == (T){0} ) break; 29 29 a = b; 30 30 b = r; … … 33 33 } // gcd 34 34 35 static RationalImpl simplify( RationalImpl & n, RationalImpl& d ) {36 if ( d == ( RationalImpl){0} ) {35 static T simplify( T & n, T & d ) { 36 if ( d == (T){0} ) { 37 37 abort | "Invalid rational number construction: denominator cannot be equal to 0."; 38 38 } // exit 39 if ( d < ( RationalImpl){0} ) { d = -d; n = -n; } // move sign to numerator39 if ( d < (T){0} ) { d = -d; n = -n; } // move sign to numerator 40 40 return gcd( abs( n ), d ); // simplify 41 41 } // Rationalnumber::simplify … … 43 43 // constructors 44 44 45 void ?{}( Rational(RationalImpl) & r ) { 46 r{ (RationalImpl){0}, (RationalImpl){1} }; 47 } // rational 48 49 void ?{}( Rational(RationalImpl) & r, RationalImpl n ) { 50 r{ n, (RationalImpl){1} }; 51 } // rational 52 53 void ?{}( Rational(RationalImpl) & r, RationalImpl n, RationalImpl d ) { 54 RationalImpl t = simplify( n, d ); // simplify 45 void ?{}( Rational(T) & r, zero_t ) { 46 r{ (T){0}, (T){1} }; 47 } // rational 48 49 void ?{}( Rational(T) & r, one_t ) { 50 r{ (T){1}, (T){1} }; 51 } // rational 52 53 void ?{}( Rational(T) & r ) { 54 r{ (T){0}, (T){1} }; 55 } // rational 56 57 void ?{}( Rational(T) & r, T n ) { 58 r{ n, (T){1} }; 59 } // rational 60 61 void ?{}( Rational(T) & r, T n, T d ) { 62 T t = simplify( n, d ); // simplify 55 63 r.[numerator, denominator] = [n / t, d / t]; 56 64 } // rational 57 65 58 void ?{}( Rational(RationalImpl) & r, zero_t ) {59 r{ (RationalImpl){0}, (RationalImpl){1} };60 } // rational61 62 void ?{}( Rational(RationalImpl) & r, one_t ) {63 r{ (RationalImpl){1}, (RationalImpl){1} };64 } // rational65 66 66 // getter for numerator/denominator 67 67 68 RationalImpl numerator( Rational(RationalImpl) r ) {68 T numerator( Rational(T) r ) { 69 69 return r.numerator; 70 70 } // numerator 71 71 72 RationalImpl denominator( Rational(RationalImpl) r ) {72 T denominator( Rational(T) r ) { 73 73 return r.denominator; 74 74 } // denominator 75 75 76 [ RationalImpl, RationalImpl ] ?=?( & [ RationalImpl, RationalImpl ] dest, Rational(RationalImpl) src ) {76 [ T, T ] ?=?( & [ T, T ] dest, Rational(T) src ) { 77 77 return dest = src.[ numerator, denominator ]; 78 78 } // ?=? … … 80 80 // setter for numerator/denominator 81 81 82 RationalImpl numerator( Rational(RationalImpl) r, RationalImpln ) {83 RationalImplprev = r.numerator;84 RationalImplt = gcd( abs( n ), r.denominator ); // simplify82 T numerator( Rational(T) r, T n ) { 83 T prev = r.numerator; 84 T t = gcd( abs( n ), r.denominator ); // simplify 85 85 r.[numerator, denominator] = [n / t, r.denominator / t]; 86 86 return prev; 87 87 } // numerator 88 88 89 RationalImpl denominator( Rational(RationalImpl) r, RationalImpld ) {90 RationalImplprev = r.denominator;91 RationalImplt = simplify( r.numerator, d ); // simplify89 T denominator( Rational(T) r, T d ) { 90 T prev = r.denominator; 91 T t = simplify( r.numerator, d ); // simplify 92 92 r.[numerator, denominator] = [r.numerator / t, d / t]; 93 93 return prev; … … 96 96 // comparison 97 97 98 int ?==?( Rational( RationalImpl) l, Rational(RationalImpl) r ) {98 int ?==?( Rational(T) l, Rational(T) r ) { 99 99 return l.numerator * r.denominator == l.denominator * r.numerator; 100 100 } // ?==? 101 101 102 int ?!=?( Rational( RationalImpl) l, Rational(RationalImpl) r ) {102 int ?!=?( Rational(T) l, Rational(T) r ) { 103 103 return ! ( l == r ); 104 104 } // ?!=? 105 105 106 int ?<?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { 106 int ?!=?( Rational(T) l, zero_t ) { 107 return ! ( l == (Rational(T)){ 0 } ); 108 } // ?!=? 109 110 int ?<?( Rational(T) l, Rational(T) r ) { 107 111 return l.numerator * r.denominator < l.denominator * r.numerator; 108 112 } // ?<? 109 113 110 int ?<=?( Rational( RationalImpl) l, Rational(RationalImpl) r ) {114 int ?<=?( Rational(T) l, Rational(T) r ) { 111 115 return l.numerator * r.denominator <= l.denominator * r.numerator; 112 116 } // ?<=? 113 117 114 int ?>?( Rational( RationalImpl) l, Rational(RationalImpl) r ) {118 int ?>?( Rational(T) l, Rational(T) r ) { 115 119 return ! ( l <= r ); 116 120 } // ?>? 117 121 118 int ?>=?( Rational( RationalImpl) l, Rational(RationalImpl) r ) {122 int ?>=?( Rational(T) l, Rational(T) r ) { 119 123 return ! ( l < r ); 120 124 } // ?>=? … … 122 126 // arithmetic 123 127 124 Rational( RationalImpl) +?( Rational(RationalImpl) r ) {125 return (Rational( RationalImpl)){ r.numerator, r.denominator };128 Rational(T) +?( Rational(T) r ) { 129 return (Rational(T)){ r.numerator, r.denominator }; 126 130 } // +? 127 131 128 Rational( RationalImpl) -?( Rational(RationalImpl) r ) {129 return (Rational( RationalImpl)){ -r.numerator, r.denominator };132 Rational(T) -?( Rational(T) r ) { 133 return (Rational(T)){ -r.numerator, r.denominator }; 130 134 } // -? 131 135 132 Rational( RationalImpl) ?+?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {136 Rational(T) ?+?( Rational(T) l, Rational(T) r ) { 133 137 if ( l.denominator == r.denominator ) { // special case 134 return (Rational( RationalImpl)){ l.numerator + r.numerator, l.denominator };138 return (Rational(T)){ l.numerator + r.numerator, l.denominator }; 135 139 } else { 136 return (Rational( RationalImpl)){ l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator };140 return (Rational(T)){ l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator }; 137 141 } // if 138 142 } // ?+? 139 143 140 Rational(RationalImpl) ?-?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { 144 Rational(T) ?+=?( Rational(T) & l, Rational(T) r ) { 145 l = l + r; 146 return l; 147 } // ?+? 148 149 Rational(T) ?+=?( Rational(T) & l, one_t ) { 150 l = l + (Rational(T)){ 1 }; 151 return l; 152 } // ?+? 153 154 Rational(T) ?-?( Rational(T) l, Rational(T) r ) { 141 155 if ( l.denominator == r.denominator ) { // special case 142 return (Rational( RationalImpl)){ l.numerator - r.numerator, l.denominator };156 return (Rational(T)){ l.numerator - r.numerator, l.denominator }; 143 157 } else { 144 return (Rational( RationalImpl)){ l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator };158 return (Rational(T)){ l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator }; 145 159 } // if 146 160 } // ?-? 147 161 148 Rational(RationalImpl) ?*?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { 149 return (Rational(RationalImpl)){ l.numerator * r.numerator, l.denominator * r.denominator }; 162 Rational(T) ?-=?( Rational(T) & l, Rational(T) r ) { 163 l = l - r; 164 return l; 165 } // ?-? 166 167 Rational(T) ?-=?( Rational(T) & l, one_t ) { 168 l = l - (Rational(T)){ 1 }; 169 return l; 170 } // ?-? 171 172 Rational(T) ?*?( Rational(T) l, Rational(T) r ) { 173 return (Rational(T)){ l.numerator * r.numerator, l.denominator * r.denominator }; 150 174 } // ?*? 151 175 152 Rational(RationalImpl) ?/?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { 153 if ( r.numerator < (RationalImpl){0} ) { 176 Rational(T) ?*=?( Rational(T) & l, Rational(T) r ) { 177 return l = l * r; 178 } // ?*? 179 180 Rational(T) ?/?( Rational(T) l, Rational(T) r ) { 181 if ( r.numerator < (T){0} ) { 154 182 r.[numerator, denominator] = [-r.numerator, -r.denominator]; 155 183 } // if 156 return (Rational( RationalImpl)){ l.numerator * r.denominator, l.denominator * r.numerator };184 return (Rational(T)){ l.numerator * r.denominator, l.denominator * r.numerator }; 157 185 } // ?/? 158 186 187 Rational(T) ?/=?( Rational(T) & l, Rational(T) r ) { 188 return l = l / r; 189 } // ?/? 190 159 191 // I/O 160 192 161 forall( istype & | istream( istype ) | { istype & ?|?( istype &, RationalImpl& ); } )162 istype & ?|?( istype & is, Rational( RationalImpl) & r ) {193 forall( istype & | istream( istype ) | { istype & ?|?( istype &, T & ); } ) 194 istype & ?|?( istype & is, Rational(T) & r ) { 163 195 is | r.numerator | r.denominator; 164 RationalImplt = simplify( r.numerator, r.denominator );196 T t = simplify( r.numerator, r.denominator ); 165 197 r.numerator /= t; 166 198 r.denominator /= t; … … 168 200 } // ?|? 169 201 170 forall( ostype & | ostream( ostype ) | { ostype & ?|?( ostype &, RationalImpl); } ) {171 ostype & ?|?( ostype & os, Rational( RationalImpl) r ) {202 forall( ostype & | ostream( ostype ) | { ostype & ?|?( ostype &, T ); } ) { 203 ostype & ?|?( ostype & os, Rational(T) r ) { 172 204 return os | r.numerator | '/' | r.denominator; 173 205 } // ?|? 174 206 175 void ?|?( ostype & os, Rational( RationalImpl) r ) {207 void ?|?( ostype & os, Rational(T) r ) { 176 208 (ostype &)(os | r); ends( os ); 177 209 } // ?|? … … 179 211 } // distribution 180 212 181 forall( RationalImpl | arithmetic( RationalImpl ) | { RationalImpl ?\?( RationalImpl, unsigned long ); } ) 182 Rational(RationalImpl) ?\?( Rational(RationalImpl) x, long int y ) { 183 if ( y < 0 ) { 184 return (Rational(RationalImpl)){ x.denominator \ -y, x.numerator \ -y }; 185 } else { 186 return (Rational(RationalImpl)){ x.numerator \ y, x.denominator \ y }; 187 } // if 188 } 213 forall( T | Arithmetic( T ) | { T ?\?( T, unsigned long ); } ) { 214 Rational(T) ?\?( Rational(T) x, long int y ) { 215 if ( y < 0 ) { 216 return (Rational(T)){ x.denominator \ -y, x.numerator \ -y }; 217 } else { 218 return (Rational(T)){ x.numerator \ y, x.denominator \ y }; 219 } // if 220 } // ?\? 221 222 Rational(T) ?\=?( Rational(T) & x, long int y ) { 223 return x = x \ y; 224 } // ?\? 225 } // distribution 189 226 190 227 // conversion 191 228 192 forall( RationalImpl | arithmetic( RationalImpl ) | { double convert( RationalImpl); } )193 double widen( Rational( RationalImpl) r ) {229 forall( T | Arithmetic( T ) | { double convert( T ); } ) 230 double widen( Rational(T) r ) { 194 231 return convert( r.numerator ) / convert( r.denominator ); 195 232 } // widen 196 233 197 forall( RationalImpl | arithmetic( RationalImpl ) | { double convert( RationalImpl ); RationalImplconvert( double ); } )198 Rational( RationalImpl) narrow( double f, RationalImplmd ) {234 forall( T | Arithmetic( T ) | { double convert( T ); T convert( double ); } ) 235 Rational(T) narrow( double f, T md ) { 199 236 // http://www.ics.uci.edu/~eppstein/numth/frap.c 200 if ( md <= ( RationalImpl){1} ) { // maximum fractional digits too small?201 return (Rational( RationalImpl)){ convert( f ), (RationalImpl){1}}; // truncate fraction237 if ( md <= (T){1} ) { // maximum fractional digits too small? 238 return (Rational(T)){ convert( f ), (T){1}}; // truncate fraction 202 239 } // if 203 240 204 241 // continued fraction coefficients 205 RationalImplm00 = {1}, m11 = { 1 }, m01 = { 0 }, m10 = { 0 };206 RationalImplai, t;242 T m00 = {1}, m11 = { 1 }, m01 = { 0 }, m10 = { 0 }; 243 T ai, t; 207 244 208 245 // find terms until denom gets too big … … 221 258 if ( f > (double)0x7FFFFFFF ) break; // representation failure 222 259 } // for 223 return (Rational( RationalImpl)){ m00, m10 };260 return (Rational(T)){ m00, m10 }; 224 261 } // narrow 225 262
Note: See TracChangeset
for help on using the changeset viewer.