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 <a href="http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/fraction/Fraction.html">Commons Math</a> -->
005  * see <a target="_blank" href="http://commons.apache.org/proper/commons-math/userguide/fraction.html">Commons Math</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 href="http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math4/fraction/BigFraction.html"><code>BigFraction</code></a>.<br>
117     * <br>
118     * <b>Description copied from interface: {@link JxnCloneableAlgebra}</b><br>
119     * {@inheritDoc}
120     */
121   public JxnCloneableAlgebra cloneThis()
122   {
123      return new MyFractionAlgebra( numerator, denominator );
124   }
125
126
127// --- reflection methods ---
128
129   /** Adds {@code opnd} to this.
130     * @return this
131     */
132   public MyFractionAlgebra add( MyFractionAlgebra opnd )
133   {
134   // numerator = numerator*((MyFractionAlgebra)opnd).denominator + denominator*((MyFractionAlgebra)opnd).numerator;
135   // denominator= denominator*((MyFractionAlgebra)opnd).denominator;
136      if( DEBUG ) System.out.println( "add(0): " + this + " " + opnd );
137      long g = gcd( denominator, opnd.denominator );
138      long n1 = opnd.denominator / g * numerator;
139      long n2 = denominator / g * opnd.numerator;
140      if( DEBUG ) System.out.println( "add(1): " + g + " " + n1 + " " + n2 );
141      if( Math.abs(n1) > Integer.MAX_VALUE || Math.abs(n2) > Integer.MAX_VALUE )
142      {
143         throw new KmgFormelException( "integer overflow for: " + this + " (+) " + opnd );
144      }
145      long num = n1 + n2;
146      long den = denominator / g * opnd.denominator;
147      if( DEBUG ) System.out.println( "add(2): " + num + " " + den );
148      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
149      {
150         throw new KmgFormelException( "integer overflow for: " + this + " (+) " + opnd );
151      }
152      numerator = (int)num;
153      denominator  = (int)den;
154      reduce();
155      return this;
156   }
157   
158/* Subtracts opnd from this (Implementation not necesary, if constructor MyFractionAlgebra(int) exists).
159   public MyFractionAlgebra sub( MyFractionAlgebra opnd )
160   {
161   // numerator = numerator*((MyFractionAlgebra)opnd).denominator - denominator*((MyFractionAlgebra)opnd).numerator;
162   // denominator= denominator*((MyFractionAlgebra)opnd).denominator;
163      long g = gcd( denominator, opnd.denominator );
164      long n1 = opnd.denominator / g * numerator;
165      long n2 = denominator / g * opnd.numerator;
166      if( Math.abs(n1) > Integer.MAX_VALUE || Math.abs(n2) > Integer.MAX_VALUE )
167      {
168         throw new KmgFormelException( "integer overflow for: " + this + " (-) " + opnd );
169      }
170      long num = n1 - n2;
171      long den = denominator / g * opnd.denominator;
172      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
173      {
174         throw new KmgFormelException( "integer overflow for: " + this + " (-) " + opnd );
175      }
176      numerator = (int)num;
177      denominator  = (int)den;
178      reduce();
179      return this;
180   }
181*/
182   
183   /** (Post)Multiplies this by {@code opnd}.
184     * @return this
185     */
186   public MyFractionAlgebra mul( MyFractionAlgebra opnd )
187   {
188   // numerator = numerator*((MyFractionAlgebra)opnd).numerator;
189   // denominator= denominator*((MyFractionAlgebra)opnd).denominator;
190      long g1 = gcd( numerator, opnd.denominator );
191      long g2 = gcd( denominator,  opnd.numerator );
192      long num  = numerator / g1 * ( opnd.numerator / g2 );
193      long den  = denominator  / g2 * ( opnd.denominator  / g1 );
194      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
195      {
196         throw new KmgFormelException( "integer overflow for: " + this + " (*) " + opnd );
197      }
198      numerator = (int)num;
199      denominator  = (int)den;
200      reduce();
201      return this;
202   }
203
204/* Divides this by opnd (Implementation not necessary, if method inv() exists).
205   public MyFractionAlgebra div( MyFractionAlgebra opnd )
206   {
207   // numerator = numerator*((MyFractionAlgebra)opnd).denominator;
208   // denominator = denominator*((MyFractionAlgebra)opnd).numerator;
209      long g1 = gcd( numerator, ((MyFractionAlgebra)opnd).numerator );
210      long g2 = gcd( denominator,  ((MyFractionAlgebra)opnd).denominator );
211      long num  = numerator / g1 * ( ((MyFractionAlgebra)opnd).denominator  / g2 );
212      long den  = denominator  / g2 * ( ((MyFractionAlgebra)opnd).numerator / g1 );
213      if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE )
214      {
215         throw new KmgFormelException( "integer overflow for: " + this + " (/) " + opnd );
216      }
217      numerator = (int)num;
218      denominator  = (int)den;
219      reduce();
220      return this;
221   }
222*/
223
224   /** Replaces this by its reciprocal.
225     * @return this
226     */
227   public MyFractionAlgebra inv()
228   {
229      int temp = numerator;
230      numerator = denominator;
231      denominator = temp;
232      return this;
233   }
234   
235   /** Replaces this by its power of {@code exponent}.
236     * @return this
237     */
238   public MyFractionAlgebra pow( int exponent )
239   {
240      if( exponent < 0 )
241      {
242         int tmp = numerator;
243         numerator   = power( denominator, -exponent );
244         denominator = power( tmp, -exponent );
245      }
246      else
247      {
248         numerator   = power( numerator, exponent );
249         denominator = power( denominator, exponent );
250      }
251   // reduce();  // not neccessary
252      return this;
253   }
254
255
256// --- overwriten methods ---
257
258   /** Fractions are equal, if both numerator and denominator are equal. */
259// public boolean equals( MyFractionAlgebra other )  // geht nicht
260   public boolean equals( Object other )
261   {
262      if( numerator != ((MyFractionAlgebra)other).numerator ) return false;
263      if( denominator  != ((MyFractionAlgebra)other).denominator  ) return false;
264      return true;
265   }
266   
267/* TODO: equals => gleicher Hashcode
268   public int hashCode()
269   {
270      return ...
271   }
272*/
273
274   /** Returns a string representation of the fraction. */
275   public String toString()
276   {
277      return numerator + " / " + denominator + " = " + doubleValue();
278   }
279   
280   
281// --- other reflection methods ---
282
283   /** Returns the greatest common divisor (gcd) of {@code m} and {@code n}. */
284   public static int gcd( int m, int n )
285   {
286//    if( m > n )
287//       return gcd( m - n, n );
288//    else if( n > m )
289//       return gcd( m, n - m );
290//    else
291//       return m;
292
293      if( n == 0 ) return 0;
294
295      for(;;)
296      {
297         int mn = m % n;
298         if( mn == 0 ) return Math.abs(n);
299         m = n;
300         n = mn;
301      }
302   }
303   
304   
305// --- internal methods ---
306
307   /** Reduces the fraction: devides numerator and denominator by their greatest common divisor. */
308   protected void reduce()  // reduce
309   {
310      int g = gcd( numerator, denominator );
311      if ( g == 0 ) return;
312      if( denominator < 0 ) g = -g;
313      numerator /= g;
314      denominator /= g;
315   }
316   
317   /** power.
318     * @param exponent must be &gt;= 0
319     */
320   protected int power( int base, int exponent )
321   {
322      if( exponent < 0 ) throw new KmgFormelException( "negative exponent not allowed" );
323      int exp = exponent;
324      
325      long result = 1;
326      while( exp > 0 )
327      {
328         result *= base;
329         if( Math.abs( result ) > Integer.MAX_VALUE ) throw new KmgFormelException( "integer overflow for: " + this + " ^ " + exponent );
330         exp--;
331      }
332      
333      return (int)result;
334   }
335}