Changeset 561f730 for src/libcfa


Ignore:
Timestamp:
May 14, 2017, 6:30:20 PM (8 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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:
4c8f86b3
Message:

first attempt converting rational numbers to generic type

Location:
src/libcfa
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/libcfa/rational

    r4c8f86b3 r561f730  
    1212// Created On       : Wed Apr  6 17:56:25 2016
    1313// Last Modified By : Peter A. Buhr
    14 // Last Modified On : Mon May  1 08:25:06 2017
    15 // Update Count     : 33
     14// Last Modified On : Sun May 14 16:49:13 2017
     15// Update Count     : 78
    1616//
    1717
    … …  
    2121#include "iostream"
    2222
     23trait scalar( otype T ) {
     24};
     25
     26trait arithmetic( otype T | scalar( T ) ) {
     27        int !?( T );
     28        int ?==?( T, T );
     29        int ?!=?( T, T );
     30        int ?<?( T, T );
     31        int ?<=?( T, T );
     32        int ?>?( T, T );
     33        int ?>=?( T, T );
     34        void ?{}( T *, zero_t );
     35        void ?{}( T *, one_t );
     36        T +?( T );
     37        T -?( T );
     38        T ?+?( T, T );
     39        T ?-?( T, T );
     40        T ?*?( T, T );
     41        T ?/?( T, T );
     42        T ?%?( T, T );
     43        T ?/=?( T *, T );
     44        T abs( T );
     45};
     46
    2347// implementation
    24 typedef long int RationalImpl;
     48
     49forall ( otype RationalImpl | arithmetic( RationalImpl ) )
    2550struct Rational {
    26         RationalImpl numerator, denominator;                                    // invariant: denominator > 0
     51        RationalImpl numerator, denominator;                            // invariant: denominator > 0
    2752}; // Rational
    2853
    29 // constants
    30 extern struct Rational 0;
    31 extern struct Rational 1;
     54// constructors
    3255
    33 // constructors
    34 void ?{}( Rational * r );
    35 void ?{}( Rational * r, RationalImpl n );
    36 void ?{}( Rational * r, RationalImpl n, RationalImpl d );
     56forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     57void ?{}( Rational(RationalImpl) * r );
     58
     59forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     60void ?{}( Rational(RationalImpl) * r, RationalImpl n );
     61
     62forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     63void ?{}( Rational(RationalImpl) * r, RationalImpl n, RationalImpl d );
     64
     65forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     66void ?{}( Rational(RationalImpl) * r, zero_t );
     67
     68forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     69void ?{}( Rational(RationalImpl) * r, one_t );
    3770
    3871// getter for numerator/denominator
    39 RationalImpl numerator( Rational r );
    40 RationalImpl denominator( Rational r );
    41 [ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational src );
     72
     73forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     74RationalImpl numerator( Rational(RationalImpl) r );
     75
     76forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     77RationalImpl denominator( Rational(RationalImpl) r );
     78forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     79[ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational(RationalImpl) src );
     80
    4281// setter for numerator/denominator
    43 RationalImpl numerator( Rational r, RationalImpl n );
    44 RationalImpl denominator( Rational r, RationalImpl d );
     82
     83forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     84RationalImpl numerator( Rational(RationalImpl) r, RationalImpl n );
     85
     86forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     87RationalImpl denominator( Rational(RationalImpl) r, RationalImpl d );
    4588
    4689// comparison
    47 int ?==?( Rational l, Rational r );
    48 int ?!=?( Rational l, Rational r );
    49 int ?<?( Rational l, Rational r );
    50 int ?<=?( Rational l, Rational r );
    51 int ?>?( Rational l, Rational r );
    52 int ?>=?( Rational l, Rational r );
     90
     91forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     92int ?==?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     93
     94forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     95int ?!=?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     96
     97forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     98int ?<?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     99
     100forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     101int ?<=?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     102
     103forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     104int ?>?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     105
     106forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     107int ?>=?( Rational(RationalImpl) l, Rational(RationalImpl) r );
    53108
    54109// arithmetic
    55 Rational -?( Rational r );
    56 Rational ?+?( Rational l, Rational r );
    57 Rational ?-?( Rational l, Rational r );
    58 Rational ?*?( Rational l, Rational r );
    59 Rational ?/?( Rational l, Rational r );
     110
     111forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     112Rational(RationalImpl) +?( Rational(RationalImpl) r );
     113
     114forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     115Rational(RationalImpl) -?( Rational(RationalImpl) r );
     116
     117forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     118Rational(RationalImpl) ?+?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     119
     120forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     121Rational(RationalImpl) ?-?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     122
     123forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     124Rational(RationalImpl) ?*?( Rational(RationalImpl) l, Rational(RationalImpl) r );
     125
     126forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     127Rational(RationalImpl) ?/?( Rational(RationalImpl) l, Rational(RationalImpl) r );
    60128
    61129// conversion
    62 double widen( Rational r );
    63 Rational narrow( double f, RationalImpl md );
     130// forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     131// double widen( Rational(RationalImpl) r );
     132// forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     133// Rational(RationalImpl) narrow( double f, RationalImpl md );
    64134
    65135// I/O
    66 forall( dtype istype | istream( istype ) ) istype * ?|?( istype *, Rational * );
    67 forall( dtype ostype | ostream( ostype ) ) ostype * ?|?( ostype *, Rational );
     136forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     137forall( dtype istype | istream( istype ) | { istype * ?|?( istype *, RationalImpl * ); } )
     138istype * ?|?( istype *, Rational(RationalImpl) * );
     139
     140forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     141forall( dtype ostype | ostream( ostype ) | { ostype * ?|?( ostype *, RationalImpl ); } )
     142ostype * ?|?( ostype *, Rational(RationalImpl ) );
    68143
    69144#endif // RATIONAL_H

  • src/libcfa/rational.c

    r4c8f86b3 r561f730  
    1010// Created On       : Wed Apr  6 17:54:28 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Apr 27 17:05:06 2017
    13 // Update Count     : 51
     12// Last Modified On : Sun May 14 17:25:19 2017
     13// Update Count     : 131
    1414//
    1515
    … …  
    1717#include "fstream"
    1818#include "stdlib"
    19 #include "math"                                                                                 // floor
    20 
    21 
    22 // constants
    23 
    24 struct Rational 0 = {0, 1};
    25 struct Rational 1 = {1, 1};
    26 
    2719
    2820// helper routines
    … …  
    3022// Calculate greatest common denominator of two numbers, the first of which may be negative. Used to reduce rationals.
    3123// alternative: https://en.wikipedia.org/wiki/Binary_GCD_algorithm
     24forall ( otype RationalImpl | arithmetic( RationalImpl ) )
    3225static RationalImpl gcd( RationalImpl a, RationalImpl b ) {
    3326        for ( ;; ) {                                                                            // Euclid's algorithm
    3427                RationalImpl r = a % b;
    35           if ( r == 0 ) break;
     28          if ( r == (RationalImpl){0} ) break;
    3629                a = b;
    3730                b = r;
    … …  
    4033} // gcd
    4134
    42 static RationalImpl simplify( RationalImpl *n, RationalImpl *d ) {
    43         if ( *d == 0 ) {
     35forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     36static RationalImpl simplify( RationalImpl * n, RationalImpl * d ) {
     37        if ( *d == (RationalImpl){0} ) {
    4438                serr | "Invalid rational number construction: denominator cannot be equal to 0." | endl;
    4539                exit( EXIT_FAILURE );
    4640        } // exit
    47         if ( *d < 0 ) { *d = -*d; *n = -*n; }                           // move sign to numerator
     41        if ( *d < (RationalImpl){0} ) { *d = -*d; *n = -*n; } // move sign to numerator
    4842        return gcd( abs( *n ), *d );                                            // simplify
    4943} // Rationalnumber::simplify
    … …  
    5246// constructors
    5347
    54 void ?{}( Rational * r ) {
    55         r{ 0, 1 };
     48forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     49void ?{}( Rational(RationalImpl) * r ) {
     50        r{ (RationalImpl){0}, (RationalImpl){1} };
    5651} // rational
    5752
    58 void ?{}( Rational * r, RationalImpl n ) {
    59         r{ n, 1 };
     53forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     54void ?{}( Rational(RationalImpl) * r, RationalImpl n ) {
     55        r{ n, (RationalImpl){1} };
    6056} // rational
    6157
    62 void ?{}( Rational * r, RationalImpl n, RationalImpl d ) {
     58forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     59void ?{}( Rational(RationalImpl) * r, RationalImpl n, RationalImpl d ) {
    6360        RationalImpl t = simplify( &n, &d );                            // simplify
    6461        r->numerator = n / t;
    … …  
    6966// getter for numerator/denominator
    7067
    71 RationalImpl numerator( Rational r ) {
     68forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     69RationalImpl numerator( Rational(RationalImpl) r ) {
    7270        return r.numerator;
    7371} // numerator
    7472
    75 RationalImpl denominator( Rational r ) {
     73forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     74RationalImpl denominator( Rational(RationalImpl) r ) {
    7675        return r.denominator;
    7776} // denominator
    7877
    79 [ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational src ) {
     78forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     79[ RationalImpl, RationalImpl ] ?=?( * [ RationalImpl, RationalImpl ] dest, Rational(RationalImpl) src ) {
    8080        return *dest = src.[ numerator, denominator ];
    8181}
    … …  
    8383// setter for numerator/denominator
    8484
    85 RationalImpl numerator( Rational r, RationalImpl n ) {
     85forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     86RationalImpl numerator( Rational(RationalImpl) r, RationalImpl n ) {
    8687        RationalImpl prev = r.numerator;
    8788        RationalImpl t = gcd( abs( n ), r.denominator );                // simplify
    … …  
    9192} // numerator
    9293
    93 RationalImpl denominator( Rational r, RationalImpl d ) {
     94forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     95RationalImpl denominator( Rational(RationalImpl) r, RationalImpl d ) {
    9496        RationalImpl prev = r.denominator;
    9597        RationalImpl t = simplify( &r.numerator, &d );                  // simplify
    … …  
    102104// comparison
    103105
    104 int ?==?( Rational l, Rational r ) {
     106forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     107int ?==?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
    105108        return l.numerator * r.denominator == l.denominator * r.numerator;
    106109} // ?==?
    107110
    108 int ?!=?( Rational l, Rational r ) {
     111forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     112int ?!=?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
    109113        return ! ( l == r );
    110114} // ?!=?
    111115
    112 int ?<?( Rational l, Rational r ) {
     116forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     117int ?<?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
    113118        return l.numerator * r.denominator < l.denominator * r.numerator;
    114119} // ?<?
    115120
    116 int ?<=?( Rational l, Rational r ) {
    117         return l < r || l == r;
     121forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     122int ?<=?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
     123        return l.numerator * r.denominator <= l.denominator * r.numerator;
    118124} // ?<=?
    119125
    120 int ?>?( Rational l, Rational r ) {
     126forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     127int ?>?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
    121128        return ! ( l <= r );
    122129} // ?>?
    123130
    124 int ?>=?( Rational l, Rational r ) {
     131forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     132int ?>=?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
    125133        return ! ( l < r );
    126134} // ?>=?
    … …  
    129137// arithmetic
    130138
    131 Rational -?( Rational r ) {
    132         Rational t = { -r.numerator, r.denominator };
     139forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     140Rational(RationalImpl) +?( Rational(RationalImpl) r ) {
     141        Rational(RationalImpl) t = { r.numerator, r.denominator };
     142        return t;
     143} // +?
     144
     145forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     146Rational(RationalImpl) -?( Rational(RationalImpl) r ) {
     147        Rational(RationalImpl) t = { -r.numerator, r.denominator };
    133148        return t;
    134149} // -?
    135150
    136 Rational ?+?( Rational l, Rational r ) {
     151forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     152Rational(RationalImpl) ?+?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
    137153        if ( l.denominator == r.denominator ) {                         // special case
    138                 Rational t = { l.numerator + r.numerator, l.denominator };
     154                Rational(RationalImpl) t = { l.numerator + r.numerator, l.denominator };
    139155                return t;
    140156        } else {
    141                 Rational t = { l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator };
     157                Rational(RationalImpl) t = { l.numerator * r.denominator + l.denominator * r.numerator, l.denominator * r.denominator };
    142158                return t;
    143159        } // if
    144160} // ?+?
    145161
    146 Rational ?-?( Rational l, Rational r ) {
     162forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     163Rational(RationalImpl) ?-?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
    147164        if ( l.denominator == r.denominator ) {                         // special case
    148                 Rational t = { l.numerator - r.numerator, l.denominator };
     165                Rational(RationalImpl) t = { l.numerator - r.numerator, l.denominator };
    149166                return t;
    150167        } else {
    151                 Rational t = { l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator };
     168                Rational(RationalImpl) t = { l.numerator * r.denominator - l.denominator * r.numerator, l.denominator * r.denominator };
    152169                return t;
    153170        } // if
    154171} // ?-?
    155172
    156 Rational ?*?( Rational l, Rational r ) {
    157         Rational t = { l.numerator * r.numerator, l.denominator * r.denominator };
     173forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     174Rational(RationalImpl) ?*?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
     175        Rational(RationalImpl) t = { l.numerator * r.numerator, l.denominator * r.denominator };
    158176        return t;
    159177} // ?*?
    160178
    161 Rational ?/?( Rational l, Rational r ) {
    162         if ( r.numerator < 0 ) {
     179forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     180Rational(RationalImpl) ?/?( Rational(RationalImpl) l, Rational(RationalImpl) r ) {
     181        if ( r.numerator < (RationalImpl){0} ) {
    163182                r.numerator = -r.numerator;
    164183                r.denominator = -r.denominator;
    165184        } // if
    166         Rational t = { l.numerator * r.denominator, l.denominator * r.numerator };
     185        Rational(RationalImpl) t = { l.numerator * r.denominator, l.denominator * r.numerator };
    167186        return t;
    168187} // ?/?
    … …  
    171190// conversion
    172191
    173 double widen( Rational r ) {
    174         return (double)r.numerator / (double)r.denominator;
    175 } // widen
    176 
    177 // http://www.ics.uci.edu/~eppstein/numth/frap.c
    178 Rational narrow( double f, RationalImpl md ) {
    179         if ( md <= 1 ) {                                                                        // maximum fractional digits too small?
    180                 return (Rational){ f, 1};                                               // truncate fraction
    181         } // if
    182 
    183         // continued fraction coefficients
    184         RationalImpl m00 = 1, m11 = 1, m01 = 0, m10 = 0;
    185         RationalImpl ai, t;
    186 
    187         // find terms until denom gets too big
    188         for ( ;; ) {
    189                 ai = (RationalImpl)f;
    190           if ( ! (m10 * ai + m11 <= md) ) break;
    191                 t = m00 * ai + m01;
    192                 m01 = m00;
    193                 m00 = t;
    194                 t = m10 * ai + m11;
    195                 m11 = m10;
    196                 m10 = t;
    197                 t = (double)ai;
    198           if ( f == t ) break;                                                          // prevent division by zero
    199                 f = 1 / (f - t);
    200           if ( f > (double)0x7FFFFFFF ) break;                          // representation failure
    201         }
    202         return (Rational){ m00, m10 };
    203 } // narrow
     192// forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     193// double widen( Rational(RationalImpl) r ) {
     194//      return (double)r.numerator / (double)r.denominator;
     195// } // widen
     196
     197// // http://www.ics.uci.edu/~eppstein/numth/frap.c
     198// forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     199// Rational(RationalImpl) narrow( double f, RationalImpl md ) {
     200//      if ( md <= 1 ) {                                                                        // maximum fractional digits too small?
     201//              return (Rational(RationalImpl)){ f, 1};                 // truncate fraction
     202//      } // if
     203
     204//      // continued fraction coefficients
     205//      RationalImpl m00 = 1, m11 = 1, m01 = 0, m10 = 0;
     206//      RationalImpl ai, t;
     207
     208//      // find terms until denom gets too big
     209//      for ( ;; ) {
     210//              ai = (RationalImpl)f;
     211//        if ( ! (m10 * ai + m11 <= md) ) break;
     212//              t = m00 * ai + m01;
     213//              m01 = m00;
     214//              m00 = t;
     215//              t = m10 * ai + m11;
     216//              m11 = m10;
     217//              m10 = t;
     218//              t = (double)ai;
     219//        if ( f == t ) break;                                                          // prevent division by zero
     220//        f = 1 / (f - (double)t);
     221//        if ( f > (double)0x7FFFFFFF ) break;                          // representation failure
     222//      }
     223//      return (Rational(RationalImpl)){ m00, m10 };
     224// } // narrow
    204225
    205226
    206227// I/O
    207228
    208 forall( dtype istype | istream( istype ) )
    209 istype * ?|?( istype *is, Rational *r ) {
     229forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     230forall( dtype istype | istream( istype ) | { istype * ?|?( istype *, RationalImpl * ); } )
     231istype * ?|?( istype * is, Rational(RationalImpl) * r ) {
    210232        RationalImpl t;
    211233        is | &(r->numerator) | &(r->denominator);
    … …  
    216238} // ?|?
    217239
    218 forall( dtype ostype | ostream( ostype ) )
    219 ostype * ?|?( ostype *os, Rational r ) {
     240forall ( otype RationalImpl | arithmetic( RationalImpl ) )
     241forall( dtype ostype | ostream( ostype ) | { ostype * ?|?( ostype *, RationalImpl ); } )
     242ostype * ?|?( ostype * os, Rational(RationalImpl ) r ) {
    220243        return os | r.numerator | '/' | r.denominator;
    221244} // ?|?
Note: See TracChangeset for help on using the changeset viewer.