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 >= 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}