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 target="_top" href="../programmer_examples/commons_math_examples/0_CommonsMath_README.html">Commons Math</a> → 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, Comparable<MyFractionAlgebra> 010{ 011 static final boolean DEBUG = false; 012 013 protected int numerator; 014 protected int denominator; 015 016 /** Records if the fraction representation with int numerator and denomonator is exact or an approximation. 017 * Is internally changed, if during calculations intermedeate results cannot be exactly represented with int numerator and denominator. 018 * @see #toString 019 */ 020 protected boolean exact = true; 021 022 /** Constructs a new Fraction object. */ 023 public MyFractionAlgebra( int numerator, int denominator ) 024 { 025 // if( denominator == 0 ) throw new KmgFormelException( "invalid denominator: " + denominator ); 026 if( denominator == 0 ) KmgFormelInterpreter.errorExit( "invalid denominator: " + denominator ); 027 028 this.numerator = numerator; 029 this.denominator = denominator; 030 reduce(); 031 } 032 033 /** Equivalent to {@code new MyFractionAlgebra( numerator, 1 )}. <br> 034 * Required for mixed operations: int <i>op</i> fraction, fraction <i>op</i> int 035 */ 036 public MyFractionAlgebra( int numerator ) 037 { 038 this( numerator, 1 ); 039 } 040 041 /** Finds a fraction that represents {@code x}, using the continued fraction algorithm. <br> 042 * Required for mixed operations: double <i>op</i> fraction, fraction <i>op</i> double. 043 * @see <a target="_blank" href="https://en.wikipedia.org/wiki/Continued_fraction">continued fraction</a> 044 */ 045 public MyFractionAlgebra( double x ) 046 { 047 // boolean DEBUG = true; 048 049 if( x == 0 ) 050 { 051 numerator = 0; 052 denominator = 1; 053 return; 054 } 055 056 // Kettenbruchalgorithmus (continued fraction) 057 int nPrev = 0; 058 int dPrev = 1; 059 double ax = Math.abs(x); 060 numerator = 1; 061 denominator = 0; 062 063 if( DEBUG ) System.out.println( getClass().getName() + "( " + x + " )" ); 064 065 while( true ) 066 { 067 if( ax > Integer.MAX_VALUE ) break; 068 int ai = (int)Math.floor( ax ); 069 // if( DEBUG ) System.out.print( " " + ai ); 070 071 long nNext = ai * (long)numerator; 072 long dNext = ai * (long)denominator; 073 if( nNext > Integer.MAX_VALUE ) break; 074 if( dNext > Integer.MAX_VALUE ) break; 075 076 nNext += nPrev; 077 dNext += dPrev; 078 if( nNext > Integer.MAX_VALUE ) break; 079 if( dNext > Integer.MAX_VALUE ) break; 080 081 nPrev = numerator; 082 dPrev = denominator; 083 numerator = (int)nNext; 084 denominator = (int)dNext; 085 086 ax %= 1.; 087 if( DEBUG ) System.out.println( " " + ai + ", " + ax ); 088 if( ax == 0. ) break; 089 ax = 1. / ax; 090 } 091 092 exact = ax == 0.; 093 094 if( x < 0. ) numerator = -numerator; 095 reduce(); // required? 096 if( DEBUG ) System.out.println( " => " + this ); 097 098 if( Math.abs( x - doubleValue() ) > Math.abs(x) * 2./Integer.MAX_VALUE ) 099 { 100 throw new KmgFormelException( "unable to convert " + x + " to " + getClass() + ": " + this ); 101 } 102 } 103 104 /** Returns the internally stored numerator. */ 105 public int getNumerator() 106 { 107 return numerator; 108 } 109 110 /** Returns the internally stored denominator. */ 111 public int getDenominator() 112 { 113 return denominator; 114 } 115 116 /** Returns, if the fraction (with int numerator and denominator) is exact (otherwise it is an approximation). 117 * @see #exact 118 */ 119 public boolean isExact() 120 { 121 return exact; 122 } 123 124 /** Declares that this fraction instance is considered exact. 125 * @return this 126 * @see #exact 127 */ 128 public MyFractionAlgebra setExact( boolean exact ) 129 { 130 this.exact = exact; 131 return this; 132 } 133 134 /** Returns this fraction as double. */ 135 public double doubleValue() 136 { 137 return (double)numerator / denominator; 138 } 139 140 141// --- interface methods --- 142 143 /** <b>Note:</b> {@code MyFractionAlgebra} implements {@link JxnCloneableAlgebra} only for demonstration. 144 * As {@code MyFractionAlgebra} has only 2 int members {@code numerator} and {@code denominator} it 145 * should better be implemented as <i>immutable</i> like {@code java.math.}{@link java.math.BigInteger} 146 * or <!-- <a target="_blank" href="http://commons.apache.org/proper/commons-math/userguide/fraction.html">CommonsMath</a> --> 147 * <a target="_top" href="../programmer_examples/commons_math_examples/0_CommonsMath_README.html">Commons Math</a> → 148 * <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> 149 * <!-- <a href="http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math4/fraction/BigFraction.html"><code>BigFraction</code></a> -->.<br> 150 * <br> 151 * <b>Description copied from interface: {@link JxnCloneableAlgebra}</b><br> 152 * {@inheritDoc} 153 */ 154 public JxnCloneableAlgebra cloneThis() 155 { 156 MyFractionAlgebra result = new MyFractionAlgebra( numerator, denominator ); 157 result.exact = exact; 158 return result; 159 } 160 161 162// --- reflection methods --- 163 164 /** Adds {@code opnd} to this. 165 * @return this 166 */ 167 public MyFractionAlgebra add( MyFractionAlgebra opnd ) 168 { 169 // numerator = numerator*((MyFractionAlgebra)opnd).denominator + denominator*((MyFractionAlgebra)opnd).numerator; 170 // denominator= denominator*((MyFractionAlgebra)opnd).denominator; 171 if( DEBUG ) System.out.println( "add(0): " + this + " " + opnd ); 172 173 long g = gcd( denominator, opnd.denominator ); 174 long n1 = opnd.denominator / g * numerator; 175 long n2 = denominator / g * opnd.numerator; 176 long num = n1 + n2; 177 long den = denominator / g * opnd.denominator; 178 if( DEBUG ) System.out.println( "add(1): " + g + " " + n1 + " " + n2 + " -> " + num + " " + den ); 179 180 if( Math.abs(n1) > Integer.MAX_VALUE || Math.abs(n2) > Integer.MAX_VALUE 181 || Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE ) 182 { 183 // throw new KmgFormelException( "integer overflow for: " + this + " (+) " + opnd ); 184 MyFractionAlgebra tmp = new MyFractionAlgebra( (double)num / den ); 185 numerator = tmp.numerator; 186 denominator = tmp.denominator; 187 exact = false; 188 return this; 189 } 190 191 numerator = (int)num; 192 denominator = (int)den; 193 reduce(); 194 exact &= opnd.exact; 195 return this; 196 } 197 198/* Subtracts opnd from this (Implementation not necessary, if constructor MyFractionAlgebra(int) exists). 199 public MyFractionAlgebra sub( MyFractionAlgebra opnd ) 200 { 201 // numerator = numerator*((MyFractionAlgebra)opnd).denominator - denominator*((MyFractionAlgebra)opnd).numerator; 202 // denominator= denominator*((MyFractionAlgebra)opnd).denominator; 203 long g = gcd( denominator, opnd.denominator ); 204 long n1 = opnd.denominator / g * numerator; 205 long n2 = denominator / g * opnd.numerator; 206 if( Math.abs(n1) > Integer.MAX_VALUE || Math.abs(n2) > Integer.MAX_VALUE ) 207 { 208 throw new KmgFormelException( "integer overflow for: " + this + " (-) " + opnd ); 209 } 210 long num = n1 - n2; 211 long den = denominator / g * opnd.denominator; 212 if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE ) 213 { 214 throw new KmgFormelException( "integer overflow for: " + this + " (-) " + opnd ); 215 } 216 numerator = (int)num; 217 denominator = (int)den; 218 reduce(); 219 return this; 220 } 221*/ 222 223 /** (Post)Multiplies this by {@code opnd}. 224 * @return this 225 */ 226 public MyFractionAlgebra mul( MyFractionAlgebra opnd ) 227 { 228 // numerator = numerator*((MyFractionAlgebra)opnd).numerator; 229 // denominator= denominator*((MyFractionAlgebra)opnd).denominator; 230 if( numerator == 0 ) return this; 231 if( opnd.numerator == 0 ) 232 { 233 numerator = 0; 234 denominator = 1; 235 exact &= opnd.exact; 236 return this; 237 } 238 239 long g1 = gcd( numerator, opnd.denominator ); 240 long g2 = gcd( denominator, opnd.numerator ); 241 if( g1 == 0 || g2 == 0 ) // required? 242 { 243 System.out.println( g1 + " " + g2 ); 244 numerator = 0; 245 denominator = 1; 246 return this; 247 } 248 249 long num = numerator / g1 * ( opnd.numerator / g2 ); 250 long den = denominator / g2 * ( opnd.denominator / g1 ); 251 if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE ) 252 { 253 // throw new KmgFormelException( "integer overflow for: " + this + " (*) " + opnd ); 254 MyFractionAlgebra tmp = new MyFractionAlgebra( (double)num / den ); 255 numerator = tmp.numerator; 256 denominator = tmp.denominator; 257 exact = false; 258 return this; 259 } 260 261 numerator = (int)num; 262 denominator = (int)den; 263 reduce(); // required? 264 exact &= opnd.exact; 265 return this; 266 } 267 268/* Divides this by opnd (Implementation not necessary, if method inv() exists). 269 public MyFractionAlgebra div( MyFractionAlgebra opnd ) 270 { 271 return mul( new MyFractionAlgebra( opnd.denominator, opnd.numerator ) ); 272 /* 273 // numerator = numerator*((MyFractionAlgebra)opnd).denominator; 274 // denominator = denominator*((MyFractionAlgebra)opnd).numerator; 275 long g1 = gcd( numerator, ((MyFractionAlgebra)opnd).numerator ); 276 long g2 = gcd( denominator, ((MyFractionAlgebra)opnd).denominator ); 277 long num = numerator / g1 * ( ((MyFractionAlgebra)opnd).denominator / g2 ); 278 long den = denominator / g2 * ( ((MyFractionAlgebra)opnd).numerator / g1 ); 279 if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE ) 280 { 281 throw new KmgFormelException( "integer overflow for: " + this + " (/) " + opnd ); 282 } 283 numerator = (int)num; 284 denominator = (int)den; 285 reduce(); 286 return this; 287 } 288 */ 289 290 /** Replaces this by its reciprocal. 291 * @return this 292 */ 293 public MyFractionAlgebra inv() 294 { 295 if( numerator == 0 ) KmgFormelInterpreter.errorExit( "invalid numerator: " + numerator ); 296 297 int temp = numerator; 298 numerator = denominator; 299 denominator = temp; 300 return this; 301 } 302 303 /** Replaces this by its power of {@code exponent}. 304 * @return this 305 */ 306 public MyFractionAlgebra pow( int exponent ) 307 { 308 double num, den; 309 if( exponent > 0 ) 310 { 311 num = Math.pow( numerator, exponent ); 312 den = Math.pow( denominator, exponent ); 313 } 314 else if( exponent < 0 ) 315 { 316 if( numerator == 0 ) KmgFormelInterpreter.errorExit( "invalid numerator: " + numerator + " for exponent: " + exponent ); 317 318 num = Math.pow( denominator, -exponent ); 319 den = Math.pow( numerator, -exponent ); 320 } 321 else // exponent == 0 322 { 323 numerator = 1; 324 denominator = 1; 325 exact = true; 326 return this; 327 } 328 329 if( Math.abs(num) > Integer.MAX_VALUE || Math.abs(den) > Integer.MAX_VALUE ) 330 { 331 MyFractionAlgebra tmp = new MyFractionAlgebra( (double)num / den ); 332 numerator = tmp.numerator; 333 denominator = tmp.denominator; 334 exact = false; 335 return this; 336 } 337 338 numerator = (int)Math.round( num ); 339 denominator = (int)Math.round( den ); 340 if( exact ) exact = ( numerator == num ) && ( denominator == den ); 341 // reduce(); // not necessary 342 return this; 343 } 344 345 346// --- overwriten methods --- 347 348/* TODO: equals => gleicher Hashcode 349 public int hashCode() 350 { 351 return ... 352 } 353*/ 354 355 /** Fractions are equal, if both numerator and denominator are equal. <br> 356 * (the exactness-information is not required to be equal) 357 */ 358// public boolean equals( MyFractionAlgebra other ) // geht nicht 359 public boolean equals( Object other ) 360 { 361 if( numerator != ((MyFractionAlgebra)other).numerator ) return false; 362 if( denominator != ((MyFractionAlgebra)other).denominator ) return false; 363 return true; 364 } 365 366 /** Returns -1 if {@code this < other}, +1 if {@code other > this}, else 0. */ 367 public int compareTo( MyFractionAlgebra other ) 368 { 369 double x = doubleValue(); 370 // double y = ((MyFractionAlgebra)other).doubleValue(); 371 double y = other.doubleValue(); 372 373 if( x < y ) return -1; 374 if( x > y ) return +1; 375 return 0; 376 } 377 378 /** Returns a string representation of the fraction. <br> 379 * <br> 380 * Shows the fraction as <code>"<i>numerator</i> / <i>denominator</i> = <i>double-value</i>"</code>, if int valued numerator and denominator allow 381 * an exact representation of the fraction, e.g. {@code "1 / 8 = 0.125"}. However, if the fraction is an approximation, it is formatted as 382 * <code>"<i>double-value</i> ~ <i>numerator</i> / <i>denominator</i>"</code> e.g. {@code "0.3 ~ 3 / 10"} (there is no exact binary representation 383 * of the decimal {@code 0.3}).<br> 384 * Note the difference: 385 * <pre> 386 * f1 = @{@link #MyFractionAlgebra(int, int) MyFractionAlgebra}( 3, 10 ) ! exact fraction 387 * = 3 / 10 = 0.3 (MyFractionAlgebra) 388 * f2 = @{@link #MyFractionAlgebra(double) MyFractionAlgebra}( 0.3 ) ! approximation of the double {@code 0.3} 389 * = 0.3 ~ 3 / 10 (MyFractionAlgebra) </pre> 390 * The resulting fraction instances {@code f1} and {@code f2} are equal, but only {@code f1} considers itself exact. 391 * A Calculation with fraction instances transfers the exactness-information to its result. 392 * @see #exact 393 */ 394 public String toString() 395 { 396 if( exact ) return numerator + " / " + denominator + " = " + doubleValue(); 397 // return doubleValue() + " \u2248 " + numerator + " / " + denominator; // asymp wird zu klein dargestellt 398 return doubleValue() + " ~ " + numerator + " / " + denominator; 399 } 400 401 402// --- other reflection methods --- 403 404 /** Returns the greatest common divisor (gcd) of {@code m} and {@code n}. */ 405 public static int gcd( int m, int n ) 406 { 407// if( m > n ) 408// return gcd( m - n, n ); 409// else if( n > m ) 410// return gcd( m, n - m ); 411// else 412// return m; 413 414 if( n == 0 ) return 0; 415 416 for(;;) 417 { 418 int mn = m % n; 419 if( mn == 0 ) return Math.abs(n); 420 m = n; 421 n = mn; 422 } 423 } 424 425 426// --- internal methods --- 427 428 /** Reduces the fraction: devides numerator and denominator by their greatest common divisor. */ 429 protected void reduce() // reduce 430 { 431 int g = gcd( numerator, denominator ); 432 if ( g == 0 ) return; 433 if( denominator < 0 ) g = -g; 434 numerator /= g; 435 denominator /= g; 436 } 437 438 /** power. 439 * @param exponent must be >= 0 440 */ 441 protected int power( int base, int exponent ) // no more needed 442 { 443 if( exponent < 0 ) throw new KmgFormelException( "negative exponent not allowed" ); 444 int exp = exponent; 445 446 long result = 1; 447 while( exp > 0 ) 448 { 449 result *= base; 450 if( Math.abs( result ) > Integer.MAX_VALUE ) throw new KmgFormelException( "integer overflow for: " + this + " ^ " + exponent ); 451 exp--; 452 } 453 454 return (int)result; 455 } 456 457 /** Test. */ 458 public static void main( String [] args ) 459 { 460 for( int n = 1; n <= Integer.MAX_VALUE; n++ ) 461 { 462 MyFractionAlgebra sqrt_n = new MyFractionAlgebra( Math.sqrt(n) ); 463 if( sqrt_n.mul( sqrt_n ).equals( new MyFractionAlgebra(n) ) == false ) 464 { 465 System.out.println( n + " " + sqrt_n ); // 1073741825 1.073741824E9 ~ 1073741824 / 1 466 break; 467 } 468 if( n % 10_000_000 == 0 ) System.out.println( n + " " + sqrt_n ); 469 } 470 System.out.println( Integer.MAX_VALUE ); 471 } 472}