001/** Simple implementation of a fraction algebra (example of a <i>user defined algebra</i>). <br>
002  * Stores numerator and denominator with int precision. Allows mixed operations with int and double.<br>
003  * For a may be more elaborate implementation 
004  * see &nbsp;<a target="_top" href="../programmer_examples/commons_math_examples/0_CommonsMath_README.html">Commons Math</a> &rarr;
005  * <a target="_blank" href="http://commons.apache.org/proper/commons-math/javadocs/api-3.6.1/index.html?org/apache/commons/math3/fraction/BigFraction.html"><code>BigFraction</code></a>
006  * <!-- <a target="_blank" href="http://commons.apache.org/proper/commons-math/apidocs/index.html?org/apache/commons/math4/fraction/BigFraction.html"><code>BigFraction</code></a>.-->
007  * @see <a target="_top" href="../programmer_examples/MyFractionAlgebra_UserDefinedAlgebra.html">user defined algebra</a>
008  */
009public class MyFractionAlgebra implements JxnCloneableAlgebra
010{
011   static final boolean DEBUG = false;
012   
013   private int numerator;
014   private int denominator;
015
016   /** Constructs a new Fraction object. */
017   public MyFractionAlgebra( int numerator, int denominator )
018   {
019      this.numerator = numerator;
020      this.denominator = denominator;
021      reduce();
022   }
023
024   /** Equivalent to {@code new MyFractionAlgebra( numerator, 1 )}. <br>
025     * Required for mixed operations: int <i>op</i> fraction, fraction <i>op</i> int
026     */
027   public MyFractionAlgebra( int numerator )
028   {
029      this( numerator, 1 );
030   }
031
032   /** Finds a fraction that represents {@code x}, using the continued fraction algorithm. <br>
033     * Required for mixed operations: double <i>op</i> fraction, fraction <i>op</i> double.
034     * @see <a target="_blank" href="https://en.wikipedia.org/wiki/Continued_fraction">continued fraction</a>
035     */
036   public MyFractionAlgebra( double x )
037   {
038      if( x == 0 )
039      {
040         numerator = 0;
041         denominator  = 1;
042         return;
043      }
044
045      // Kettenbruchalgorithmus (continued fraction)
046      int zPrev = 0;
047      int nPrev = 1;
048      double ax = Math.abs(x);
049      numerator = 1;
050      denominator = 0;
051      
052      if( DEBUG ) System.out.print( x );
053
054      while( true )
055      {
056         if( ax > Integer.MAX_VALUE ) break;
057         int ai = (int)Math.floor( ax );
058         if( DEBUG ) System.out.print( " " + ai );
059         
060         long zNext = ai * (long)numerator;
061         long nNext = ai * (long)denominator;
062         if( zNext > Integer.MAX_VALUE ) break;
063         if( nNext > Integer.MAX_VALUE ) break;
064
065         zNext += zPrev;
066         nNext += nPrev;
067         if( zNext > Integer.MAX_VALUE ) break;
068         if( nNext > Integer.MAX_VALUE ) break;
069
070         zPrev = numerator;
071         nPrev = denominator;
072         numerator = (int)zNext;
073         denominator  = (int)nNext;
074
075         ax %= 1.;
076         if( ax == 0. ) break;
077         ax = 1. / ax;
078      }
079      
080      if( x < 0. ) numerator = -numerator;
081      reduce();
082      if( DEBUG ) System.out.println( " => " + this );
083
084      if( Math.abs( x - doubleValue() ) > Math.abs(x) * 2./Integer.MAX_VALUE )
085      {
086         System.out.println( "??? (3) " + this + " <> " + x );
087         throw new KmgFormelException( "unable to convert " + x + " to " + getClass() );
088      }
089   }
090
091   /** Returns the internally stored numerator. */
092   public int getNumerator()
093   {
094      return numerator;
095   }
096   
097   /** Returns the internally stored denominator. */
098   public int getDenominator()
099   {
100      return denominator;
101   }
102
103   /** Returns this fraction as double. */
104   public double doubleValue()
105   {
106      return (double)numerator / denominator;
107   }
108
109
110// --- interface methods ---
111
112   /** <b>Note:</b> {@code MyFractionAlgebra} implements {@link JxnCloneableAlgebra} only for demonstration.
113     * As {@code MyFractionAlgebra} has only 2 int members {@code numerator} and {@code denominator} it
114     * should better be implemented as <i>immutable</i> like {@code java.math.}{@link java.math.BigInteger} 
115     * or <!-- <a target="_blank" href="http://commons.apache.org/proper/commons-math/userguide/fraction.html">CommonsMath</a>  -->
116     * <a target="_top" href="../programmer_examples/commons_math_examples/0_CommonsMath_README.html">Commons Math</a> &rarr;
117     * <a target="_blank" href="http://commons.apache.org/proper/commons-math/javadocs/api-3.6.1/index.html?org/apache/commons/math3/fraction/BigFraction.html"><code>BigFraction</code></a>
118     * <!-- <a href="http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math4/fraction/BigFraction.html"><code>BigFraction</code></a> -->.<br>
119     * <br>
120     * <b>Description copied from interface: {@link JxnCloneableAlgebra}</b><br>
121     * {@inheritDoc}
122     */
123   public JxnCloneableAlgebra cloneThis()
124   {
125      return new MyFractionAlgebra( numerator, denominator );
126   }
127
128
129// --- reflection methods ---
130
131   /** Adds {@code opnd} to this.
132     * @return this
133     */
134   public MyFractionAlgebra add( MyFractionAlgebra opnd )
135   {
136   // numerator = numerator*((MyFractionAlgebra)opnd).denominator + denominator*((MyFractionAlgebra)opnd).numerator;
137   // denominator= denominator*((MyFractionAlgebra)opnd).denominator;
138      if( DEBUG ) System.out.println( "add(0): " + this + " " + opnd );
139      long g = gcd( denominator, opnd.denominator );
140      long n1 = opnd.denominator / g * numerator;
141      long n2 = denominator / g * opnd.numerator;
142      if( DEBUG ) System.out.println( "add(1): " + g + " " + n1 + " " + n2 );
143      if( Math.abs(n1) > Integer.MAX_VALUE || Math.abs(n2) > Integer.MAX_VALUE )
144      {
145         throw new KmgFormelException( "integer overflow for: " + this + " (+) " + opnd );
146      }
147      long num = n1 + n2;
148      long den = denominator / g * opnd.denominator;
149      if( DEBUG ) System.out.println( "add(2): " + num + " " + den );
150      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
151      {
152         throw new KmgFormelException( "integer overflow for: " + this + " (+) " + opnd );
153      }
154      numerator = (int)num;
155      denominator  = (int)den;
156      reduce();
157      return this;
158   }
159   
160/* Subtracts opnd from this (Implementation not necesary, if constructor MyFractionAlgebra(int) exists).
161   public MyFractionAlgebra sub( MyFractionAlgebra opnd )
162   {
163   // numerator = numerator*((MyFractionAlgebra)opnd).denominator - denominator*((MyFractionAlgebra)opnd).numerator;
164   // denominator= denominator*((MyFractionAlgebra)opnd).denominator;
165      long g = gcd( denominator, opnd.denominator );
166      long n1 = opnd.denominator / g * numerator;
167      long n2 = denominator / g * opnd.numerator;
168      if( Math.abs(n1) > Integer.MAX_VALUE || Math.abs(n2) > Integer.MAX_VALUE )
169      {
170         throw new KmgFormelException( "integer overflow for: " + this + " (-) " + opnd );
171      }
172      long num = n1 - n2;
173      long den = denominator / g * opnd.denominator;
174      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
175      {
176         throw new KmgFormelException( "integer overflow for: " + this + " (-) " + opnd );
177      }
178      numerator = (int)num;
179      denominator  = (int)den;
180      reduce();
181      return this;
182   }
183*/
184   
185   /** (Post)Multiplies this by {@code opnd}.
186     * @return this
187     */
188   public MyFractionAlgebra mul( MyFractionAlgebra opnd )
189   {
190   // numerator = numerator*((MyFractionAlgebra)opnd).numerator;
191   // denominator= denominator*((MyFractionAlgebra)opnd).denominator;
192      long g1 = gcd( numerator, opnd.denominator );
193      long g2 = gcd( denominator,  opnd.numerator );
194      long num  = numerator / g1 * ( opnd.numerator / g2 );
195      long den  = denominator  / g2 * ( opnd.denominator  / g1 );
196      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
197      {
198         throw new KmgFormelException( "integer overflow for: " + this + " (*) " + opnd );
199      }
200      numerator = (int)num;
201      denominator  = (int)den;
202      reduce();
203      return this;
204   }
205
206/* Divides this by opnd (Implementation not necessary, if method inv() exists).
207   public MyFractionAlgebra div( MyFractionAlgebra opnd )
208   {
209   // numerator = numerator*((MyFractionAlgebra)opnd).denominator;
210   // denominator = denominator*((MyFractionAlgebra)opnd).numerator;
211      long g1 = gcd( numerator, ((MyFractionAlgebra)opnd).numerator );
212      long g2 = gcd( denominator,  ((MyFractionAlgebra)opnd).denominator );
213      long num  = numerator / g1 * ( ((MyFractionAlgebra)opnd).denominator  / g2 );
214      long den  = denominator  / g2 * ( ((MyFractionAlgebra)opnd).numerator / g1 );
215      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
216      {
217         throw new KmgFormelException( "integer overflow for: " + this + " (/) " + opnd );
218      }
219      numerator = (int)num;
220      denominator  = (int)den;
221      reduce();
222      return this;
223   }
224*/
225
226   /** Replaces this by its reciprocal.
227     * @return this
228     */
229   public MyFractionAlgebra inv()
230   {
231      int temp = numerator;
232      numerator = denominator;
233      denominator = temp;
234      return this;
235   }
236   
237   /** Replaces this by its power of {@code exponent}.
238     * @return this
239     */
240   public MyFractionAlgebra pow( int exponent )
241   {
242      if( exponent < 0 )
243      {
244         int tmp = numerator;
245         numerator   = power( denominator, -exponent );
246         denominator = power( tmp, -exponent );
247      }
248      else
249      {
250         numerator   = power( numerator, exponent );
251         denominator = power( denominator, exponent );
252      }
253   // reduce();  // not neccessary
254      return this;
255   }
256
257
258// --- overwriten methods ---
259
260   /** Fractions are equal, if both numerator and denominator are equal. */
261// public boolean equals( MyFractionAlgebra other )  // geht nicht
262   public boolean equals( Object other )
263   {
264      if( numerator != ((MyFractionAlgebra)other).numerator ) return false;
265      if( denominator != ((MyFractionAlgebra)other).denominator ) return false;
266      return true;
267   }
268   
269/* TODO: equals => gleicher Hashcode
270   public int hashCode()
271   {
272      return ...
273   }
274*/
275
276   /** Returns a string representation of the fraction. */
277   public String toString()
278   {
279      return numerator + " / " + denominator + " = " + doubleValue();
280   }
281   
282   
283// --- other reflection methods ---
284
285   /** Returns the greatest common divisor (gcd) of {@code m} and {@code n}. */
286   public static int gcd( int m, int n )
287   {
288//    if( m > n )
289//       return gcd( m - n, n );
290//    else if( n > m )
291//       return gcd( m, n - m );
292//    else
293//       return m;
294
295      if( n == 0 ) return 0;
296
297      for(;;)
298      {
299         int mn = m % n;
300         if( mn == 0 ) return Math.abs(n);
301         m = n;
302         n = mn;
303      }
304   }
305   
306   
307// --- internal methods ---
308
309   /** Reduces the fraction: devides numerator and denominator by their greatest common divisor. */
310   protected void reduce()  // reduce
311   {
312      int g = gcd( numerator, denominator );
313      if ( g == 0 ) return;
314      if( denominator < 0 ) g = -g;
315      numerator /= g;
316      denominator /= g;
317   }
318   
319   /** power.
320     * @param exponent must be &gt;= 0
321     */
322   protected int power( int base, int exponent )
323   {
324      if( exponent < 0 ) throw new KmgFormelException( "negative exponent not allowed" );
325      int exp = exponent;
326      
327      long result = 1;
328      while( exp > 0 )
329      {
330         result *= base;
331         if( Math.abs( result ) > Integer.MAX_VALUE ) throw new KmgFormelException( "integer overflow for: " + this + " ^ " + exponent );
332         exp--;
333      }
334      
335      return (int)result;
336   }
337}