# Changeset 561f730

Ignore:
Timestamp:
May 14, 2017, 6:30:20 PM (6 years ago)
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
a32cfc90
Parents:
4c8f86b
Message:

first attempt converting rational numbers to generic type

Location:
src
Files:
4 edited

Unmodified
Removed
• ## src/libcfa/rational

 r4c8f86b // Created On       : Wed Apr  6 17:56:25 2016 // Last Modified By : Peter A. Buhr // Last Modified On : Mon May  1 08:25:06 2017 // Update Count     : 33 // Last Modified On : Sun May 14 16:49:13 2017 // Update Count     : 78 // #include "iostream" trait scalar( otype T ) { }; trait arithmetic( otype T | scalar( T ) ) { int !?( T ); int ?==?( T, T ); int ?!=?( T, T ); int ??( T, T ); int ?>=?( T, T ); void ?{}( T *, zero_t ); void ?{}( T *, one_t ); T +?( T ); T -?( T ); T ?+?( T, T ); T ?-?( T, T ); T ?*?( T, T ); T ?/?( T, T ); T ?%?( T, T ); T ?/=?( T *, T ); T abs( T ); }; // implementation typedef long int RationalImpl; forall ( otype RationalImpl | arithmetic( RationalImpl ) ) struct Rational { RationalImpl numerator, denominator;                                    // invariant: denominator > 0 RationalImpl numerator, denominator;                            // invariant: denominator > 0 }; // Rational // constants extern struct Rational 0; extern struct Rational 1; // constructors // constructors void ?{}( Rational * r ); void ?{}( Rational * r, RationalImpl n ); void ?{}( Rational * r, RationalImpl n, RationalImpl d ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r, RationalImpl n ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r, RationalImpl n, RationalImpl d ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r, zero_t ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r, one_t ); // getter for numerator/denominator RationalImpl numerator( Rational r ); RationalImpl denominator( Rational r ); [ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational src ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl numerator( Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl denominator( Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) [ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational(RationalImpl) src ); // setter for numerator/denominator RationalImpl numerator( Rational r, RationalImpl n ); RationalImpl denominator( Rational r, RationalImpl d ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl numerator( Rational(RationalImpl) r, RationalImpl n ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl denominator( Rational(RationalImpl) r, RationalImpl d ); // comparison int ?==?( Rational l, Rational r ); int ?!=?( Rational l, Rational r ); int ??( Rational l, Rational r ); int ?>=?( Rational l, Rational r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ?==?( Rational(RationalImpl) l, Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ?!=?( Rational(RationalImpl) l, Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ??( Rational(RationalImpl) l, Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ?>=?( Rational(RationalImpl) l, Rational(RationalImpl) r ); // arithmetic Rational -?( Rational r ); Rational ?+?( Rational l, Rational r ); Rational ?-?( Rational l, Rational r ); Rational ?*?( Rational l, Rational r ); Rational ?/?( Rational l, Rational r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) +?( Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) -?( Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?+?( Rational(RationalImpl) l, Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?-?( Rational(RationalImpl) l, Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?*?( Rational(RationalImpl) l, Rational(RationalImpl) r ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?/?( Rational(RationalImpl) l, Rational(RationalImpl) r ); // conversion double widen( Rational r ); Rational narrow( double f, RationalImpl md ); // forall ( otype RationalImpl | arithmetic( RationalImpl ) ) // double widen( Rational(RationalImpl) r ); // forall ( otype RationalImpl | arithmetic( RationalImpl ) ) // Rational(RationalImpl) narrow( double f, RationalImpl md ); // I/O forall( dtype istype | istream( istype ) ) istype * ?|?( istype *, Rational * ); forall( dtype ostype | ostream( ostype ) ) ostype * ?|?( ostype *, Rational ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) forall( dtype istype | istream( istype ) | { istype * ?|?( istype *, RationalImpl * ); } ) istype * ?|?( istype *, Rational(RationalImpl) * ); forall ( otype RationalImpl | arithmetic( RationalImpl ) ) forall( dtype ostype | ostream( ostype ) | { ostype * ?|?( ostype *, RationalImpl ); } ) ostype * ?|?( ostype *, Rational(RationalImpl ) ); #endif // RATIONAL_H
• ## src/libcfa/rational.c

 r4c8f86b // Created On       : Wed Apr  6 17:54:28 2016 // Last Modified By : Peter A. Buhr // Last Modified On : Thu Apr 27 17:05:06 2017 // Update Count     : 51 // Last Modified On : Sun May 14 17:25:19 2017 // Update Count     : 131 // #include "fstream" #include "stdlib" #include "math"                                                                                 // floor // constants struct Rational 0 = {0, 1}; struct Rational 1 = {1, 1}; // helper routines // Calculate greatest common denominator of two numbers, the first of which may be negative. Used to reduce rationals. // alternative: https://en.wikipedia.org/wiki/Binary_GCD_algorithm forall ( otype RationalImpl | arithmetic( RationalImpl ) ) static RationalImpl gcd( RationalImpl a, RationalImpl b ) { for ( ;; ) {                                                                            // Euclid's algorithm RationalImpl r = a % b; if ( r == 0 ) break; if ( r == (RationalImpl){0} ) break; a = b; b = r; } // gcd static RationalImpl simplify( RationalImpl *n, RationalImpl *d ) { if ( *d == 0 ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) static RationalImpl simplify( RationalImpl * n, RationalImpl * d ) { if ( *d == (RationalImpl){0} ) { serr | "Invalid rational number construction: denominator cannot be equal to 0." | endl; exit( EXIT_FAILURE ); } // exit if ( *d < 0 ) { *d = -*d; *n = -*n; }                           // move sign to numerator if ( *d < (RationalImpl){0} ) { *d = -*d; *n = -*n; } // move sign to numerator return gcd( abs( *n ), *d );                                            // simplify } // Rationalnumber::simplify // constructors void ?{}( Rational * r ) { r{ 0, 1 }; forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r ) { r{ (RationalImpl){0}, (RationalImpl){1} }; } // rational void ?{}( Rational * r, RationalImpl n ) { r{ n, 1 }; forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r, RationalImpl n ) { r{ n, (RationalImpl){1} }; } // rational void ?{}( Rational * r, RationalImpl n, RationalImpl d ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) void ?{}( Rational(RationalImpl) * r, RationalImpl n, RationalImpl d ) { RationalImpl t = simplify( &n, &d );                            // simplify r->numerator = n / t; // getter for numerator/denominator RationalImpl numerator( Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl numerator( Rational(RationalImpl) r ) { return r.numerator; } // numerator RationalImpl denominator( Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl denominator( Rational(RationalImpl) r ) { return r.denominator; } // denominator [ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational src ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) [ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational(RationalImpl) src ) { return *dest = src.[ numerator, denominator ]; } // setter for numerator/denominator RationalImpl numerator( Rational r, RationalImpl n ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl numerator( Rational(RationalImpl) r, RationalImpl n ) { RationalImpl prev = r.numerator; RationalImpl t = gcd( abs( n ), r.denominator );                // simplify } // numerator RationalImpl denominator( Rational r, RationalImpl d ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) RationalImpl denominator( Rational(RationalImpl) r, RationalImpl d ) { RationalImpl prev = r.denominator; RationalImpl t = simplify( &r.numerator, &d );                  // simplify // comparison int ?==?( Rational l, Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ?==?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { return l.numerator * r.denominator == l.denominator * r.numerator; } // ?==? int ?!=?( Rational l, Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ?!=?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { return ! ( l == r ); } // ?!=? int ??( Rational l, Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ?>?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { return ! ( l <= r ); } // ?>? int ?>=?( Rational l, Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) int ?>=?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { return ! ( l < r ); } // ?>=? // arithmetic Rational -?( Rational r ) { Rational t = { -r.numerator, r.denominator }; forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) +?( Rational(RationalImpl) r ) { Rational(RationalImpl) t = { r.numerator, r.denominator }; return t; } // +? forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) -?( Rational(RationalImpl) r ) { Rational(RationalImpl) t = { -r.numerator, r.denominator }; return t; } // -? Rational ?+?( Rational l, Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?+?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { if ( l.denominator == r.denominator ) {                         // special case Rational t = { l.numerator + r.numerator, l.denominator }; Rational(RationalImpl) t = { l.numerator + r.numerator, l.denominator }; return t; } else { Rational t = { l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator }; Rational(RationalImpl) t = { l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator }; return t; } // if } // ?+? Rational ?-?( Rational l, Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?-?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { if ( l.denominator == r.denominator ) {                         // special case Rational t = { l.numerator - r.numerator, l.denominator }; Rational(RationalImpl) t = { l.numerator - r.numerator, l.denominator }; return t; } else { Rational t = { l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator }; Rational(RationalImpl) t = { l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator }; return t; } // if } // ?-? Rational ?*?( Rational l, Rational r ) { Rational t = { l.numerator * r.numerator, l.denominator * r.denominator }; forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?*?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { Rational(RationalImpl) t = { l.numerator * r.numerator, l.denominator * r.denominator }; return t; } // ?*? Rational ?/?( Rational l, Rational r ) { if ( r.numerator < 0 ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) Rational(RationalImpl) ?/?( Rational(RationalImpl) l, Rational(RationalImpl) r ) { if ( r.numerator < (RationalImpl){0} ) { r.numerator = -r.numerator; r.denominator = -r.denominator; } // if Rational t = { l.numerator * r.denominator, l.denominator * r.numerator }; Rational(RationalImpl) t = { l.numerator * r.denominator, l.denominator * r.numerator }; return t; } // ?/? // conversion double widen( Rational r ) { return (double)r.numerator / (double)r.denominator; } // widen // http://www.ics.uci.edu/~eppstein/numth/frap.c Rational narrow( double f, RationalImpl md ) { if ( md <= 1 ) {                                                                        // maximum fractional digits too small? return (Rational){ f, 1};                                               // truncate fraction } // if // continued fraction coefficients RationalImpl m00 = 1, m11 = 1, m01 = 0, m10 = 0; RationalImpl ai, t; // find terms until denom gets too big for ( ;; ) { ai = (RationalImpl)f; if ( ! (m10 * ai + m11 <= md) ) break; t = m00 * ai + m01; m01 = m00; m00 = t; t = m10 * ai + m11; m11 = m10; m10 = t; t = (double)ai; if ( f == t ) break;                                                          // prevent division by zero f = 1 / (f - t); if ( f > (double)0x7FFFFFFF ) break;                          // representation failure } return (Rational){ m00, m10 }; } // narrow // forall ( otype RationalImpl | arithmetic( RationalImpl ) ) // double widen( Rational(RationalImpl) r ) { //      return (double)r.numerator / (double)r.denominator; // } // widen // // http://www.ics.uci.edu/~eppstein/numth/frap.c // forall ( otype RationalImpl | arithmetic( RationalImpl ) ) // Rational(RationalImpl) narrow( double f, RationalImpl md ) { //      if ( md <= 1 ) {                                                                        // maximum fractional digits too small? //              return (Rational(RationalImpl)){ f, 1};                 // truncate fraction //      } // if //      // continued fraction coefficients //      RationalImpl m00 = 1, m11 = 1, m01 = 0, m10 = 0; //      RationalImpl ai, t; //      // find terms until denom gets too big //      for ( ;; ) { //              ai = (RationalImpl)f; //        if ( ! (m10 * ai + m11 <= md) ) break; //              t = m00 * ai + m01; //              m01 = m00; //              m00 = t; //              t = m10 * ai + m11; //              m11 = m10; //              m10 = t; //              t = (double)ai; //        if ( f == t ) break;                                                          // prevent division by zero //        f = 1 / (f - (double)t); //        if ( f > (double)0x7FFFFFFF ) break;                          // representation failure //      } //      return (Rational(RationalImpl)){ m00, m10 }; // } // narrow // I/O forall( dtype istype | istream( istype ) ) istype * ?|?( istype *is, Rational *r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) forall( dtype istype | istream( istype ) | { istype * ?|?( istype *, RationalImpl * ); } ) istype * ?|?( istype * is, Rational(RationalImpl) * r ) { RationalImpl t; is | &(r->numerator) | &(r->denominator); } // ?|? forall( dtype ostype | ostream( ostype ) ) ostype * ?|?( ostype *os, Rational r ) { forall ( otype RationalImpl | arithmetic( RationalImpl ) ) forall( dtype ostype | ostream( ostype ) | { ostype * ?|?( ostype *, RationalImpl ); } ) ostype * ?|?( ostype * os, Rational(RationalImpl ) r ) { return os | r.numerator | '/' | r.denominator; } // ?|?
• ## src/tests/.expect/rational.txt

 r4c8f86b 3/1 4/3 conversion 0.75 0.142857142857143 3.14159292035398 3/4 1/7 355/113 decompose more tests
• ## src/tests/rational.c

 r4c8f86b // Created On       : Mon Mar 28 08:43:12 2016 // Last Modified By : Peter A. Buhr // Last Modified On : Tue May  2 22:11:05 2017 // Update Count     : 41 // Last Modified On : Sun May 14 18:10:28 2017 // Update Count     : 57 // #include #include #include #include #include // UNNECESSARY, FIX ME void ?{}( int * this ) { *this = 0; } void ?{}( int * this, zero_t ) { *this = 0; } void ?{}( int * this, one_t ) { *this = 1; } int main() { sout | "constructor" | endl; Rational a = { 3 }, b = { 4 }, c; Rational(int) a = { 3 }, b = { 4 }, c; sout | a | b | c | endl; a = (Rational){ 4, 8 }; b = (Rational){ 5, 7 }; a = (Rational(int)){ 4, 8 }; b = (Rational(int)){ 5, 7 }; sout | a | b | endl; a = (Rational){ -2, -3 }; b = (Rational){ 3, -2 }; a = (Rational(int)){ -2, -3 }; b = (Rational(int)){ 3, -2 }; sout | a | b | endl; a = (Rational){ -2, 3 }; b = (Rational){ 3, 2 }; a = (Rational(int)){ -2, 3 }; b = (Rational(int)){ 3, 2 }; sout | a | b | endl; sout | "logical" | endl; a = (Rational){ -2 }; b = (Rational){ -3, 2 }; a = (Rational(int)){ -2 }; b = (Rational(int)){ -3, 2 }; sout | a | b | endl; //      sout | a == 1 | endl; // FIX ME sout | a / b | endl; sout | "conversion" | endl; a = (Rational){ 3, 4 }; sout | widen( a ) | endl; a = (Rational){ 1, 7 }; sout | widen( a ) | endl; a = (Rational){ 355, 113 }; sout | widen( a ) | endl; sout | narrow( 0.75, 4 ) | endl; sout | narrow( 0.14285714285714, 16 ) | endl; sout | narrow( 3.14159265358979, 256 ) | endl; //      sout | "conversion" | endl; //      a = (Rational(int)){ 3, 4 }; //      sout | widen( a ) | endl; //      a = (Rational(int)){ 1, 7 }; //      sout | widen( a ) | endl; //      a = (Rational(int)){ 355, 113 }; //      sout | widen( a ) | endl; //      sout | narrow( 0.75, 4 ) | endl; //      sout | narrow( 0.14285714285714, 16 ) | endl; //      sout | narrow( 3.14159265358979, 256 ) | endl; sout | "decompose" | endl; RationalImpl n, d; int n, d; //      [n, d] = a; //      sout | a | n | d | endl; sout | "more tests" | endl; Rational x = { 1, 2 }, y = { 2 }; Rational(int) x = { 1, 2 }, y = { 2 }; sout | x - y | endl; sout | x > y | endl; sout | y | denominator( y, -2 ) | y | endl; Rational z = { 0, 5 }; Rational(int) z = { 0, 5 }; sout | z | endl; sout | x | numerator( x, 0 ) | x | endl; x = (Rational){ 1, MAX } + (Rational){ 1, MAX }; x = (Rational(int)){ 1, MAX } + (Rational(int)){ 1, MAX }; sout | x | endl; x = (Rational){ 3, MAX } + (Rational){ 2, MAX }; x = (Rational(int)){ 3, MAX } + (Rational(int)){ 2, MAX }; sout | x | endl;
Note: See TracChangeset for help on using the changeset viewer.