001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.numbers.fraction;
018
019import java.io.Serializable;
020import java.math.BigDecimal;
021import java.math.BigInteger;
022import java.math.RoundingMode;
023import java.util.Objects;
024import org.apache.commons.numbers.core.NativeOperators;
025
026/**
027 * Representation of a rational number using arbitrary precision.
028 *
029 * <p>The number is expressed as the quotient {@code p/q} of two {@link BigInteger}s,
030 * a numerator {@code p} and a non-zero denominator {@code q}.
031 *
032 * <p>This class is immutable.
033 *
034 * <a href="https://en.wikipedia.org/wiki/Rational_number">Rational number</a>
035 */
036public final class BigFraction
037    extends Number
038    implements Comparable<BigFraction>,
039               NativeOperators<BigFraction>,
040               Serializable {
041    /** A fraction representing "0". */
042    public static final BigFraction ZERO = new BigFraction(BigInteger.ZERO);
043
044    /** A fraction representing "1". */
045    public static final BigFraction ONE = new BigFraction(BigInteger.ONE);
046
047    /** Serializable version identifier. */
048    private static final long serialVersionUID = 20190701L;
049
050    /** The default iterations used for convergence. */
051    private static final int DEFAULT_MAX_ITERATIONS = 100;
052
053    /** Message for non-finite input double argument to factory constructors. */
054    private static final String NOT_FINITE = "Not finite: ";
055
056    /** The overflow limit for conversion from a double (2^31). */
057    private static final long OVERFLOW = 1L << 31;
058
059    /** The numerator of this fraction reduced to lowest terms. */
060    private final BigInteger numerator;
061
062    /** The denominator of this fraction reduced to lowest terms. */
063    private final BigInteger denominator;
064
065    /**
066     * Private constructor: Instances are created using factory methods.
067     *
068     * <p>This constructor should only be invoked when the fraction is known
069     * to be non-zero; otherwise use {@link #ZERO}. This avoids creating
070     * the zero representation {@code 0 / -1}.
071     *
072     * @param num Numerator, must not be {@code null}.
073     * @param den Denominator, must not be {@code null}.
074     * @throws ArithmeticException if the denominator is zero.
075     */
076    private BigFraction(BigInteger num, BigInteger den) {
077        if (den.signum() == 0) {
078            throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
079        }
080
081        // reduce numerator and denominator by greatest common denominator
082        final BigInteger gcd = num.gcd(den);
083        if (BigInteger.ONE.compareTo(gcd) < 0) {
084            numerator = num.divide(gcd);
085            denominator = den.divide(gcd);
086        } else {
087            numerator = num;
088            denominator = den;
089        }
090    }
091
092    /**
093     * Private constructor: Instances are created using factory methods.
094     *
095     * <p>This sets the denominator to 1.
096     *
097     * @param num Numerator (must not be null).
098     */
099    private BigFraction(BigInteger num) {
100        numerator = num;
101        denominator = BigInteger.ONE;
102    }
103
104    /**
105     * Create a fraction given the double value and either the maximum
106     * error allowed or the maximum number of denominator digits.
107     *
108     * <p>
109     * NOTE: This method is called with:
110     * </p>
111     * <ul>
112     *  <li>EITHER a valid epsilon value and the maxDenominator set to
113     *      Integer.MAX_VALUE (that way the maxDenominator has no effect)
114     *  <li>OR a valid maxDenominator value and the epsilon value set to
115     *      zero (that way epsilon only has effect if there is an exact
116     *      match before the maxDenominator value is reached).
117     * </ul>
118     * <p>
119     * It has been done this way so that the same code can be reused for
120     * both scenarios. However this could be confusing to users if it
121     * were part of the public API and this method should therefore remain
122     * PRIVATE.
123     * </p>
124     *
125     * <p>
126     * See JIRA issue ticket MATH-181 for more details:
127     *     https://issues.apache.org/jira/browse/MATH-181
128     * </p>
129     *
130     * @param value Value to convert to a fraction.
131     * @param epsilon Maximum error allowed.
132     * The resulting fraction is within {@code epsilon} of {@code value},
133     * in absolute terms.
134     * @param maxDenominator Maximum denominator value allowed.
135     * @param maxIterations Maximum number of convergents.
136     * @return a new instance.
137     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
138     * @throws ArithmeticException if the continued fraction failed to converge.
139     */
140    private static BigFraction from(final double value,
141                                    final double epsilon,
142                                    final int maxDenominator,
143                                    final int maxIterations) {
144        if (!Double.isFinite(value)) {
145            throw new IllegalArgumentException(NOT_FINITE + value);
146        }
147        if (value == 0) {
148            return ZERO;
149        }
150
151        // Remove sign, this is restored at the end.
152        // (Assumes the value is not zero and thus signum(value) is not zero).
153        final double absValue = Math.abs(value);
154        double r0 = absValue;
155        long a0 = (long) Math.floor(r0);
156        if (a0 > OVERFLOW) {
157            throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, a0, 1);
158        }
159
160        // check for (almost) integer arguments, which should not go to iterations.
161        if (r0 - a0 <= epsilon) {
162            // Restore the sign.
163            if (value < 0) {
164                a0 = -a0;
165            }
166            return new BigFraction(BigInteger.valueOf(a0));
167        }
168
169        // Support 2^31 as maximum denominator.
170        // This is negative as an integer so convert to long.
171        final long maxDen = Math.abs((long) maxDenominator);
172
173        long p0 = 1;
174        long q0 = 0;
175        long p1 = a0;
176        long q1 = 1;
177
178        long p2 = 0;
179        long q2 = 1;
180
181        int n = 0;
182        boolean stop = false;
183        do {
184            ++n;
185            final double r1 = 1.0 / (r0 - a0);
186            final long a1 = (long) Math.floor(r1);
187            p2 = (a1 * p1) + p0;
188            q2 = (a1 * q1) + q0;
189            if (Long.compareUnsigned(p2, OVERFLOW) > 0 ||
190                Long.compareUnsigned(q2, OVERFLOW) > 0) {
191                // In maxDenominator mode, fall-back to the previous valid fraction.
192                if (epsilon == 0) {
193                    p2 = p1;
194                    q2 = q1;
195                    break;
196                }
197                throw new FractionException(FractionException.ERROR_CONVERSION_OVERFLOW, value, p2, q2);
198            }
199
200            final double convergent = (double) p2 / (double) q2;
201            if (n < maxIterations &&
202                Math.abs(convergent - absValue) > epsilon &&
203                q2 < maxDen) {
204                p0 = p1;
205                p1 = p2;
206                q0 = q1;
207                q1 = q2;
208                a0 = a1;
209                r0 = r1;
210            } else {
211                stop = true;
212            }
213        } while (!stop);
214
215        if (n >= maxIterations) {
216            throw new FractionException(FractionException.ERROR_CONVERSION, value, maxIterations);
217        }
218
219        // Use p2 / q2 or p1 / q1 if q2 has grown too large in maxDenominator mode
220        long num;
221        long den;
222        if (q2 <= maxDen) {
223            num = p2;
224            den = q2;
225        } else {
226            num = p1;
227            den = q1;
228        }
229
230        // Restore the sign.
231        if (Math.signum(num) * Math.signum(den) != Math.signum(value)) {
232            num = -num;
233        }
234
235        return new BigFraction(BigInteger.valueOf(num),
236                               BigInteger.valueOf(den));
237    }
238
239    /**
240     * Create a fraction given the double value.
241     * <p>
242     * This factory method behaves <em>differently</em> to the method
243     * {@link #from(double, double, int)}. It converts the double value
244     * exactly, considering its internal bits representation. This works for all
245     * values except NaN and infinities and does not requires any loop or
246     * convergence threshold.
247     * </p>
248     * <p>
249     * Since this conversion is exact and since double numbers are sometimes
250     * approximated, the fraction created may seem strange in some cases. For example,
251     * calling {@code from(1.0 / 3.0)} does <em>not</em> create
252     * the fraction \( \frac{1}{3} \), but the fraction \( \frac{6004799503160661}{18014398509481984} \)
253     * because the double number passed to the method is not exactly \( \frac{1}{3} \)
254     * (which cannot be represented exactly in IEEE754).
255     * </p>
256     *
257     * @param value Value to convert to a fraction.
258     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite.
259     * @return a new instance.
260     *
261     * @see #from(double,double,int)
262     */
263    public static BigFraction from(final double value) {
264        if (!Double.isFinite(value)) {
265            throw new IllegalArgumentException(NOT_FINITE + value);
266        }
267        if (value == 0) {
268            return ZERO;
269        }
270
271        final long bits = Double.doubleToLongBits(value);
272        final long sign = bits & 0x8000000000000000L;
273        final long exponent = bits & 0x7ff0000000000000L;
274        final long mantissa = bits & 0x000fffffffffffffL;
275
276        // Compute m and k such that value = m * 2^k
277        long m;
278        int k;
279
280        if (exponent == 0) {
281            // Subnormal number, the effective exponent bias is 1022, not 1023.
282            // Note: mantissa is never zero as that case has been eliminated.
283            m = mantissa;
284            k = -1074;
285        } else {
286            // Normalized number: Add the implicit most significant bit.
287            m = mantissa | 0x0010000000000000L;
288            k = ((int) (exponent >> 52)) - 1075; // Exponent bias is 1023.
289        }
290        if (sign != 0) {
291            m = -m;
292        }
293        while ((m & 0x001ffffffffffffeL) != 0 &&
294               (m & 0x1) == 0) {
295            m >>= 1;
296            ++k;
297        }
298
299        return k < 0 ?
300            new BigFraction(BigInteger.valueOf(m),
301                            BigInteger.ZERO.flipBit(-k)) :
302            new BigFraction(BigInteger.valueOf(m).multiply(BigInteger.ZERO.flipBit(k)),
303                            BigInteger.ONE);
304    }
305
306    /**
307     * Create a fraction given the double value and maximum error allowed.
308     * <p>
309     * References:
310     * <ul>
311     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
312     * Continued Fraction</a> equations (11) and (22)-(26)</li>
313     * </ul>
314     *
315     * @param value Value to convert to a fraction.
316     * @param epsilon Maximum error allowed. The resulting fraction is within
317     * {@code epsilon} of {@code value}, in absolute terms.
318     * @param maxIterations Maximum number of convergents.
319     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite;
320     * {@code epsilon} is not positive; or {@code maxIterations < 1}.
321     * @throws ArithmeticException if the continued fraction failed to converge.
322     * @return a new instance.
323     */
324    public static BigFraction from(final double value,
325                                   final double epsilon,
326                                   final int maxIterations) {
327        if (maxIterations < 1) {
328            throw new IllegalArgumentException("Max iterations must be strictly positive: " + maxIterations);
329        }
330        if (epsilon >= 0) {
331            return from(value, epsilon, Integer.MIN_VALUE, maxIterations);
332        }
333        throw new IllegalArgumentException("Epsilon must be positive: " + maxIterations);
334    }
335
336    /**
337     * Create a fraction given the double value and maximum denominator.
338     *
339     * <p>
340     * References:
341     * <ul>
342     * <li><a href="http://mathworld.wolfram.com/ContinuedFraction.html">
343     * Continued Fraction</a> equations (11) and (22)-(26)</li>
344     * </ul>
345     *
346     * <p>Note: The magnitude of the {@code maxDenominator} is used allowing use of
347     * {@link Integer#MIN_VALUE} for a supported maximum denominator of 2<sup>31</sup>.
348     *
349     * @param value Value to convert to a fraction.
350     * @param maxDenominator Maximum allowed value for denominator.
351     * @throws IllegalArgumentException if the given {@code value} is NaN or infinite
352     * or {@code maxDenominator} is zero.
353     * @throws ArithmeticException if the continued fraction failed to converge.
354     * @return a new instance.
355     */
356    public static BigFraction from(final double value,
357                                   final int maxDenominator) {
358        if (maxDenominator == 0) {
359            // Re-use the zero denominator message
360            throw new IllegalArgumentException(FractionException.ERROR_ZERO_DENOMINATOR);
361        }
362        return from(value, 0, maxDenominator, DEFAULT_MAX_ITERATIONS);
363    }
364
365    /**
366     * Create a fraction given the numerator. The denominator is {@code 1}.
367     *
368     * @param num
369     *            the numerator.
370     * @return a new instance.
371     */
372    public static BigFraction of(final int num) {
373        if (num == 0) {
374            return ZERO;
375        }
376        return new BigFraction(BigInteger.valueOf(num));
377    }
378
379    /**
380     * Create a fraction given the numerator. The denominator is {@code 1}.
381     *
382     * @param num Numerator.
383     * @return a new instance.
384     */
385    public static BigFraction of(final long num) {
386        if (num == 0) {
387            return ZERO;
388        }
389        return new BigFraction(BigInteger.valueOf(num));
390    }
391
392    /**
393     * Create a fraction given the numerator. The denominator is {@code 1}.
394     *
395     * @param num Numerator.
396     * @return a new instance.
397     * @throws NullPointerException if numerator is null.
398     */
399    public static BigFraction of(final BigInteger num) {
400        Objects.requireNonNull(num, "numerator");
401        if (num.signum() == 0) {
402            return ZERO;
403        }
404        return new BigFraction(num);
405    }
406
407    /**
408     * Create a fraction given the numerator and denominator.
409     * The fraction is reduced to lowest terms.
410     *
411     * @param num Numerator.
412     * @param den Denominator.
413     * @return a new instance.
414     * @throws ArithmeticException if {@code den} is zero.
415     */
416    public static BigFraction of(final int num, final int den) {
417        if (num == 0) {
418            return ZERO;
419        }
420        return new BigFraction(BigInteger.valueOf(num), BigInteger.valueOf(den));
421    }
422
423    /**
424     * Create a fraction given the numerator and denominator.
425     * The fraction is reduced to lowest terms.
426     *
427     * @param num Numerator.
428     * @param den Denominator.
429     * @return a new instance.
430     * @throws ArithmeticException if {@code den} is zero.
431     */
432    public static BigFraction of(final long num, final long den) {
433        if (num == 0) {
434            return ZERO;
435        }
436        return new BigFraction(BigInteger.valueOf(num), BigInteger.valueOf(den));
437    }
438
439    /**
440     * Create a fraction given the numerator and denominator.
441     * The fraction is reduced to lowest terms.
442     *
443     * @param num Numerator.
444     * @param den Denominator.
445     * @return a new instance.
446     * @throws NullPointerException if numerator or denominator are null.
447     * @throws ArithmeticException if the denominator is zero.
448     */
449    public static BigFraction of(final BigInteger num, final BigInteger den) {
450        if (num.signum() == 0) {
451            return ZERO;
452        }
453        return new BigFraction(num, den);
454    }
455
456    /**
457     * Returns a {@code BigFraction} instance representing the specified string {@code s}.
458     *
459     * <p>If {@code s} is {@code null}, then a {@code NullPointerException} is thrown.
460     *
461     * <p>The string must be in a format compatible with that produced by
462     * {@link #toString() BigFraction.toString()}.
463     * The format expects an integer optionally followed by a {@code '/'} character and
464     * and second integer. Leading and trailing spaces are allowed around each numeric part.
465     * Each numeric part is parsed using {@link BigInteger#BigInteger(String)}. The parts
466     * are interpreted as the numerator and optional denominator of the fraction. If absent
467     * the denominator is assumed to be "1".
468     *
469     * <p>Examples of valid strings and the equivalent {@code BigFraction} are shown below:
470     *
471     * <pre>
472     * "0"                 = BigFraction.of(0)
473     * "42"                = BigFraction.of(42)
474     * "0 / 1"             = BigFraction.of(0, 1)
475     * "1 / 3"             = BigFraction.of(1, 3)
476     * "-4 / 13"           = BigFraction.of(-4, 13)</pre>
477     *
478     * <p>Note: The fraction is returned in reduced form and the numerator and denominator
479     * may not match the values in the input string. For this reason the result of
480     * {@code BigFraction.parse(s).toString().equals(s)} may not be {@code true}.
481     *
482     * @param s String representation.
483     * @return an instance.
484     * @throws NullPointerException if the string is null.
485     * @throws NumberFormatException if the string does not contain a parsable fraction.
486     * @see BigInteger#BigInteger(String)
487     * @see #toString()
488     */
489    public static BigFraction parse(String s) {
490        final String stripped = s.replace(",", "");
491        final int slashLoc = stripped.indexOf('/');
492        // if no slash, parse as single number
493        if (slashLoc == -1) {
494            return of(new BigInteger(stripped.trim()));
495        }
496        final BigInteger num = new BigInteger(stripped.substring(0, slashLoc).trim());
497        final BigInteger denom = new BigInteger(stripped.substring(slashLoc + 1).trim());
498        return of(num, denom);
499    }
500
501    @Override
502    public BigFraction zero() {
503        return ZERO;
504    }
505
506    @Override
507    public BigFraction one() {
508        return ONE;
509    }
510
511    /**
512     * Access the numerator as a {@code BigInteger}.
513     *
514     * @return the numerator as a {@code BigInteger}.
515     */
516    public BigInteger getNumerator() {
517        return numerator;
518    }
519
520    /**
521     * Access the numerator as an {@code int}.
522     *
523     * @return the numerator as an {@code int}.
524     */
525    public int getNumeratorAsInt() {
526        return numerator.intValue();
527    }
528
529    /**
530     * Access the numerator as a {@code long}.
531     *
532     * @return the numerator as a {@code long}.
533     */
534    public long getNumeratorAsLong() {
535        return numerator.longValue();
536    }
537
538    /**
539     * Access the denominator as a {@code BigInteger}.
540     *
541     * @return the denominator as a {@code BigInteger}.
542     */
543    public BigInteger getDenominator() {
544        return denominator;
545    }
546
547    /**
548     * Access the denominator as an {@code int}.
549     *
550     * @return the denominator as an {@code int}.
551     */
552    public int getDenominatorAsInt() {
553        return denominator.intValue();
554    }
555
556    /**
557     * Access the denominator as a {@code long}.
558     *
559     * @return the denominator as a {@code long}.
560     */
561    public long getDenominatorAsLong() {
562        return denominator.longValue();
563    }
564
565    /**
566     * Retrieves the sign of this fraction.
567     *
568     * @return -1 if the value is strictly negative, 1 if it is strictly
569     * positive, 0 if it is 0.
570     */
571    public int signum() {
572        return numerator.signum() * denominator.signum();
573    }
574
575    /**
576     * Returns the absolute value of this fraction.
577     *
578     * @return the absolute value.
579     */
580    public BigFraction abs() {
581        return signum() >= 0 ?
582            this :
583            negate();
584    }
585
586    @Override
587    public BigFraction negate() {
588        return new BigFraction(numerator.negate(), denominator);
589    }
590
591    /**
592     * {@inheritDoc}
593     *
594     * <p>Raises an exception if the fraction is equal to zero.
595     *
596     * @throws ArithmeticException if the current numerator is {@code zero}
597     */
598    @Override
599    public BigFraction reciprocal() {
600        return new BigFraction(denominator, numerator);
601    }
602
603    /**
604     * Returns the {@code double} value closest to this fraction.
605     *
606     * @return the fraction as a {@code double}.
607     */
608    @Override
609    public double doubleValue() {
610        return Double.longBitsToDouble(toFloatingPointBits(11, 52));
611    }
612
613    /**
614     * Returns the {@code float} value closest to this fraction.
615     *
616     * @return the fraction as a {@code double}.
617     */
618    @Override
619    public float floatValue() {
620        return Float.intBitsToFloat((int) toFloatingPointBits(8, 23));
621    }
622
623    /**
624     * Returns the whole number part of the fraction.
625     *
626     * @return the largest {@code int} value that is not larger than this fraction.
627     */
628    @Override
629    public int intValue() {
630        return numerator.divide(denominator).intValue();
631    }
632
633    /**
634     * Returns the whole number part of the fraction.
635     *
636     * @return the largest {@code long} value that is not larger than this fraction.
637     */
638    @Override
639    public long longValue() {
640        return numerator.divide(denominator).longValue();
641    }
642
643    /**
644     * Returns the {@code BigDecimal} representation of this fraction.
645     * This calculates the fraction as numerator divided by denominator.
646     *
647     * @return the fraction as a {@code BigDecimal}.
648     * @throws ArithmeticException
649     *             if the exact quotient does not have a terminating decimal
650     *             expansion.
651     * @see BigDecimal
652     */
653    public BigDecimal bigDecimalValue() {
654        return new BigDecimal(numerator).divide(new BigDecimal(denominator));
655    }
656
657    /**
658     * Returns the {@code BigDecimal} representation of this fraction.
659     * This calculates the fraction as numerator divided by denominator
660     * following the passed rounding mode.
661     *
662     * @param roundingMode Rounding mode to apply.
663     * @return the fraction as a {@code BigDecimal}.
664     * @see BigDecimal
665     */
666    public BigDecimal bigDecimalValue(RoundingMode roundingMode) {
667        return new BigDecimal(numerator).divide(new BigDecimal(denominator), roundingMode);
668    }
669
670    /**
671     * Returns the {@code BigDecimal} representation of this fraction.
672     * This calculates the fraction as numerator divided by denominator
673     * following the passed scale and rounding mode.
674     *
675     * @param scale
676     *            scale of the {@code BigDecimal} quotient to be returned.
677     *            see {@link BigDecimal} for more information.
678     * @param roundingMode Rounding mode to apply.
679     * @return the fraction as a {@code BigDecimal}.
680     * @throws ArithmeticException if {@code roundingMode} == {@link RoundingMode#UNNECESSARY} and
681     *      the specified scale is insufficient to represent the result of the division exactly.
682     * @see BigDecimal
683     */
684    public BigDecimal bigDecimalValue(final int scale, RoundingMode roundingMode) {
685        return new BigDecimal(numerator).divide(new BigDecimal(denominator), scale, roundingMode);
686    }
687
688    /**
689     * Adds the specified {@code value} to this fraction, returning
690     * the result in reduced form.
691     *
692     * @param value Value to add.
693     * @return {@code this + value}.
694     */
695    public BigFraction add(final int value) {
696        return add(BigInteger.valueOf(value));
697    }
698
699    /**
700     * Adds the specified {@code value} to this fraction, returning
701     * the result in reduced form.
702     *
703     * @param value Value to add.
704     * @return {@code this + value}.
705     */
706    public BigFraction add(final long value) {
707        return add(BigInteger.valueOf(value));
708    }
709
710    /**
711     * Adds the specified {@code value} to this fraction, returning
712     * the result in reduced form.
713     *
714     * @param value Value to add.
715     * @return {@code this + value}.
716     */
717    public BigFraction add(final BigInteger value) {
718        if (value.signum() == 0) {
719            return this;
720        }
721        if (isZero()) {
722            return of(value);
723        }
724
725        return of(numerator.add(denominator.multiply(value)), denominator);
726    }
727
728    /**
729     * Adds the specified {@code value} to this fraction, returning
730     * the result in reduced form.
731     *
732     * @param value Value to add.
733     * @return {@code this + value}.
734     */
735    @Override
736    public BigFraction add(final BigFraction value) {
737        if (value.isZero()) {
738            return this;
739        }
740        if (isZero()) {
741            return value;
742        }
743
744        final BigInteger num;
745        final BigInteger den;
746
747        if (denominator.equals(value.denominator)) {
748            num = numerator.add(value.numerator);
749            den = denominator;
750        } else {
751            num = (numerator.multiply(value.denominator)).add((value.numerator).multiply(denominator));
752            den = denominator.multiply(value.denominator);
753        }
754
755        if (num.signum() == 0) {
756            return ZERO;
757        }
758
759        return new BigFraction(num, den);
760    }
761
762    /**
763     * Subtracts the specified {@code value} from this fraction, returning
764     * the result in reduced form.
765     *
766     * @param value Value to subtract.
767     * @return {@code this - value}.
768     */
769    public BigFraction subtract(final int value) {
770        return subtract(BigInteger.valueOf(value));
771    }
772
773    /**
774     * Subtracts the specified {@code value} from this fraction, returning
775     * the result in reduced form.
776     *
777     * @param value Value to subtract.
778     * @return {@code this - value}.
779     */
780    public BigFraction subtract(final long value) {
781        return subtract(BigInteger.valueOf(value));
782    }
783
784    /**
785     * Subtracts the specified {@code value} from this fraction, returning
786     * the result in reduced form.
787     *
788     * @param value Value to subtract.
789     * @return {@code this - value}.
790     */
791    public BigFraction subtract(final BigInteger value) {
792        if (value.signum() == 0) {
793            return this;
794        }
795        if (isZero()) {
796            return of(value.negate());
797        }
798
799        return of(numerator.subtract(denominator.multiply(value)), denominator);
800    }
801
802    /**
803     * Subtracts the specified {@code value} from this fraction, returning
804     * the result in reduced form.
805     *
806     * @param value Value to subtract.
807     * @return {@code this - value}.
808     */
809    @Override
810    public BigFraction subtract(final BigFraction value) {
811        if (value.isZero()) {
812            return this;
813        }
814        if (isZero()) {
815            return value.negate();
816        }
817
818        final BigInteger num;
819        final BigInteger den;
820        if (denominator.equals(value.denominator)) {
821            num = numerator.subtract(value.numerator);
822            den = denominator;
823        } else {
824            num = (numerator.multiply(value.denominator)).subtract((value.numerator).multiply(denominator));
825            den = denominator.multiply(value.denominator);
826        }
827
828        if (num.signum() == 0) {
829            return ZERO;
830        }
831
832        return new BigFraction(num, den);
833    }
834
835    /**
836     * Multiply this fraction by the passed {@code value}, returning
837     * the result in reduced form.
838     *
839     * @param value Value to multiply by.
840     * @return {@code this * value}.
841     */
842    @Override
843    public BigFraction multiply(final int value) {
844        if (value == 0 || isZero()) {
845            return ZERO;
846        }
847
848        return multiply(BigInteger.valueOf(value));
849    }
850
851    /**
852     * Multiply this fraction by the passed {@code value}, returning
853     * the result in reduced form.
854     *
855     * @param value Value to multiply by.
856     * @return {@code this * value}.
857     */
858    public BigFraction multiply(final long value) {
859        if (value == 0 || isZero()) {
860            return ZERO;
861        }
862
863        return multiply(BigInteger.valueOf(value));
864    }
865
866    /**
867     * Multiply this fraction by the passed {@code value}, returning
868     * the result in reduced form.
869     *
870     * @param value Value to multiply by.
871     * @return {@code this * value}.
872     */
873    public BigFraction multiply(final BigInteger value) {
874        if (value.signum() == 0 || isZero()) {
875            return ZERO;
876        }
877        return new BigFraction(value.multiply(numerator), denominator);
878    }
879
880    /**
881     * Multiply this fraction by the passed {@code value}, returning
882     * the result in reduced form.
883     *
884     * @param value Value to multiply by.
885     * @return {@code this * value}.
886     */
887    @Override
888    public BigFraction multiply(final BigFraction value) {
889        if (value.isZero() || isZero()) {
890            return ZERO;
891        }
892        return new BigFraction(numerator.multiply(value.numerator),
893                               denominator.multiply(value.denominator));
894    }
895
896    /**
897     * Divide this fraction by the passed {@code value}, returning
898     * the result in reduced form.
899     *
900     * @param value Value to divide by
901     * @return {@code this / value}.
902     * @throws ArithmeticException if the value to divide by is zero
903     */
904    public BigFraction divide(final int value) {
905        return divide(BigInteger.valueOf(value));
906    }
907
908    /**
909     * Divide this fraction by the passed {@code value}, returning
910     * the result in reduced form.
911     *
912     * @param value Value to divide by
913     * @return {@code this / value}.
914     * @throws ArithmeticException if the value to divide by is zero
915     */
916    public BigFraction divide(final long value) {
917        return divide(BigInteger.valueOf(value));
918    }
919
920    /**
921     * Divide this fraction by the passed {@code value}, returning
922     * the result in reduced form.
923     *
924     * @param value Value to divide by
925     * @return {@code this / value}.
926     * @throws ArithmeticException if the value to divide by is zero
927     */
928    public BigFraction divide(final BigInteger value) {
929        if (value.signum() == 0) {
930            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
931        }
932        if (isZero()) {
933            return ZERO;
934        }
935        return new BigFraction(numerator, denominator.multiply(value));
936    }
937
938    /**
939     * Divide this fraction by the passed {@code value}, returning
940     * the result in reduced form.
941     *
942     * @param value Value to divide by
943     * @return {@code this / value}.
944     * @throws ArithmeticException if the value to divide by is zero
945     */
946    @Override
947    public BigFraction divide(final BigFraction value) {
948        if (value.isZero()) {
949            throw new FractionException(FractionException.ERROR_DIVIDE_BY_ZERO);
950        }
951        if (isZero()) {
952            return ZERO;
953        }
954        // Multiply by reciprocal
955        return new BigFraction(numerator.multiply(value.denominator),
956                               denominator.multiply(value.numerator));
957    }
958
959    /**
960     * Returns a {@code BigFraction} whose value is
961     * <code>this<sup>exponent</sup></code>, returning the result in reduced form.
962     *
963     * @param exponent exponent to which this {@code BigFraction} is to be raised.
964     * @return <code>this<sup>exponent</sup></code>.
965     * @throws ArithmeticException if the intermediate result would overflow.
966     */
967    @Override
968    public BigFraction pow(final int exponent) {
969        if (exponent == 1) {
970            return this;
971        }
972        if (exponent == 0) {
973            return ONE;
974        }
975        if (isZero()) {
976            if (exponent < 0) {
977                throw new FractionException(FractionException.ERROR_ZERO_DENOMINATOR);
978            }
979            return ZERO;
980        }
981        if (exponent > 0) {
982            return new BigFraction(numerator.pow(exponent),
983                                   denominator.pow(exponent));
984        }
985        if (exponent == -1) {
986            return this.reciprocal();
987        }
988        if (exponent == Integer.MIN_VALUE) {
989            // MIN_VALUE can't be negated
990            return new BigFraction(denominator.pow(Integer.MAX_VALUE).multiply(denominator),
991                                   numerator.pow(Integer.MAX_VALUE).multiply(numerator));
992        }
993        // Note: Raise the BigIntegers to the power and then reduce.
994        // The supported range for BigInteger is currently
995        // +/-2^(Integer.MAX_VALUE) exclusive thus larger
996        // exponents (long, BigInteger) are currently not supported.
997        return new BigFraction(denominator.pow(-exponent),
998                               numerator.pow(-exponent));
999    }
1000
1001    /**
1002     * Returns the {@code String} representing this fraction.
1003     * Uses:
1004     * <ul>
1005     *  <li>{@code "0"} if {@code numerator} is zero.
1006     *  <li>{@code "numerator"} if {@code denominator} is one.
1007     *  <li>{@code "numerator / denominator"} for all other cases.
1008     * </ul>
1009     *
1010     * @return a string representation of the fraction.
1011     */
1012    @Override
1013    public String toString() {
1014        final String str;
1015        if (isZero()) {
1016            str = "0";
1017        } else if (BigInteger.ONE.equals(denominator)) {
1018            str = numerator.toString();
1019        } else {
1020            str = numerator + " / " + denominator;
1021        }
1022        return str;
1023    }
1024
1025    /**
1026     * Compares this object with the specified object for order using the signed magnitude.
1027     *
1028     * @param other {@inheritDoc}
1029     * @return {@inheritDoc}
1030     */
1031    @Override
1032    public int compareTo(final BigFraction other) {
1033        final int lhsSigNum = signum();
1034        final int rhsSigNum = other.signum();
1035
1036        if (lhsSigNum != rhsSigNum) {
1037            return (lhsSigNum > rhsSigNum) ? 1 : -1;
1038        }
1039        // Same sign.
1040        // Avoid a multiply if both fractions are zero
1041        if (lhsSigNum == 0) {
1042            return 0;
1043        }
1044        // Compare absolute magnitude
1045        final BigInteger nOd = numerator.abs().multiply(other.denominator.abs());
1046        final BigInteger dOn = denominator.abs().multiply(other.numerator.abs());
1047        return nOd.compareTo(dOn);
1048    }
1049
1050    /**
1051     * Test for equality with another object. If the other object is a {@code Fraction} then a
1052     * comparison is made of the sign and magnitude; otherwise {@code false} is returned.
1053     *
1054     * @param other {@inheritDoc}
1055     * @return {@inheritDoc}
1056     */
1057    @Override
1058    public boolean equals(final Object other) {
1059        if (this == other) {
1060            return true;
1061        }
1062
1063        if (other instanceof BigFraction) {
1064            // Since fractions are always in lowest terms, numerators and
1065            // denominators can be compared directly for equality.
1066            final BigFraction rhs = (BigFraction) other;
1067            if (signum() == rhs.signum()) {
1068                return numerator.abs().equals(rhs.numerator.abs()) &&
1069                       denominator.abs().equals(rhs.denominator.abs());
1070            }
1071        }
1072
1073        return false;
1074    }
1075
1076    @Override
1077    public int hashCode() {
1078        // Incorporate the sign and absolute values of the numerator and denominator.
1079        // Equivalent to:
1080        // int hash = 1;
1081        // hash = 31 * hash + numerator.abs().hashCode();
1082        // hash = 31 * hash + denominator.abs().hashCode();
1083        // hash = hash * signum()
1084        // Note: BigInteger.hashCode() * BigInteger.signum() == BigInteger.abs().hashCode().
1085        final int numS = numerator.signum();
1086        final int denS = denominator.signum();
1087        return (31 * (31 + numerator.hashCode() * numS) + denominator.hashCode() * denS) * numS * denS;
1088    }
1089
1090    /**
1091     * Calculates the sign bit, the biased exponent and the significand for a
1092     * binary floating-point representation of this {@code BigFraction}
1093     * according to the IEEE 754 standard, and encodes these values into a {@code long}
1094     * variable. The representative bits are arranged adjacent to each other and
1095     * placed at the low-order end of the returned {@code long} value, with the
1096     * least significant bits used for the significand, the next more
1097     * significant bits for the exponent, and next more significant bit for the
1098     * sign.
1099     *
1100     * <p>Warning: The arguments are not validated.
1101     *
1102     * @param exponentLength the number of bits allowed for the exponent; must be
1103     *                       between 1 and 32 (inclusive), and must not be greater
1104     *                       than {@code 63 - significandLength}
1105     * @param significandLength the number of bits allowed for the significand
1106     *                          (excluding the implicit leading 1-bit in
1107     *                          normalized numbers, e.g. 52 for a double-precision
1108     *                          floating-point number); must be between 1 and
1109     *                          {@code 63 - exponentLength} (inclusive)
1110     * @return the bits of an IEEE 754 binary floating-point representation of
1111     * this fraction encoded in a {@code long}, as described above.
1112     */
1113    private long toFloatingPointBits(int exponentLength, int significandLength) {
1114        // Assume the following conditions:
1115        //assert exponentLength >= 1;
1116        //assert exponentLength <= 32;
1117        //assert significandLength >= 1;
1118        //assert significandLength <= 63 - exponentLength;
1119
1120        if (isZero()) {
1121            return 0L;
1122        }
1123
1124        final long sign = (numerator.signum() * denominator.signum()) == -1 ? 1L : 0L;
1125        final BigInteger positiveNumerator = numerator.abs();
1126        final BigInteger positiveDenominator = denominator.abs();
1127
1128        /*
1129         * The most significant 1-bit of a non-zero number is not explicitly
1130         * stored in the significand of an IEEE 754 normalized binary
1131         * floating-point number, so we need to round the value of this fraction
1132         * to (significandLength + 1) bits. In order to do this, we calculate
1133         * the most significant (significandLength + 2) bits, and then, based on
1134         * the least significant of those bits, find out whether we need to
1135         * round up or down.
1136         *
1137         * First, we'll remove all powers of 2 from the denominator because they
1138         * are not relevant for the significand of the prospective binary
1139         * floating-point value.
1140         */
1141        final int denRightShift = positiveDenominator.getLowestSetBit();
1142        final BigInteger divisor = positiveDenominator.shiftRight(denRightShift);
1143
1144        /*
1145         * Now, we're going to calculate the (significandLength + 2) most
1146         * significant bits of the fraction's value using integer division. To
1147         * guarantee that the quotient of the division has at least
1148         * (significandLength + 2) bits, the bit length of the dividend must
1149         * exceed that of the divisor by at least that amount.
1150         *
1151         * If the denominator has prime factors other than 2, i.e. if the
1152         * divisor was not reduced to 1, an excess of exactly
1153         * (significandLength + 2) bits is sufficient, because the knowledge
1154         * that the fractional part of the precise quotient's binary
1155         * representation does not terminate is enough information to resolve
1156         * cases where the most significant (significandLength + 2) bits alone
1157         * are not conclusive.
1158         *
1159         * Otherwise, the quotient must be calculated exactly and the bit length
1160         * of the numerator can only be reduced as long as no precision is lost
1161         * in the process (meaning it can have powers of 2 removed, like the
1162         * denominator).
1163         */
1164        int numRightShift = positiveNumerator.bitLength() - divisor.bitLength() - (significandLength + 2);
1165        if (numRightShift > 0 &&
1166            divisor.equals(BigInteger.ONE)) {
1167            numRightShift = Math.min(numRightShift, positiveNumerator.getLowestSetBit());
1168        }
1169        final BigInteger dividend = positiveNumerator.shiftRight(numRightShift);
1170
1171        final BigInteger quotient = dividend.divide(divisor);
1172
1173        int quotRightShift = quotient.bitLength() - (significandLength + 1);
1174        long significand = roundAndRightShift(
1175                quotient,
1176                quotRightShift,
1177                !divisor.equals(BigInteger.ONE)
1178        ).longValue();
1179
1180        /*
1181         * If the significand had to be rounded up, this could have caused the
1182         * bit length of the significand to increase by one.
1183         */
1184        if ((significand & (1L << (significandLength + 1))) != 0) {
1185            significand >>= 1;
1186            quotRightShift++;
1187        }
1188
1189        /*
1190         * Now comes the exponent. The absolute value of this fraction based on
1191         * the current local variables is:
1192         *
1193         * significand * 2^(numRightShift - denRightShift + quotRightShift)
1194         *
1195         * To get the unbiased exponent for the floating-point value, we need to
1196         * add (significandLength) to the above exponent, because all but the
1197         * most significant bit of the significand will be treated as a
1198         * fractional part. To convert the unbiased exponent to a biased
1199         * exponent, we also need to add the exponent bias.
1200         */
1201        final int exponentBias = (1 << (exponentLength - 1)) - 1;
1202        long exponent = (long) numRightShift - denRightShift + quotRightShift + significandLength + exponentBias;
1203        final long maxExponent = (1L << exponentLength) - 1L; //special exponent for infinities and NaN
1204
1205        if (exponent >= maxExponent) { //infinity
1206            exponent = maxExponent;
1207            significand = 0L;
1208        } else if (exponent > 0) { //normalized number
1209            significand &= -1L >>> (64 - significandLength); //remove implicit leading 1-bit
1210        } else { //smaller than the smallest normalized number
1211            /*
1212             * We need to round the quotient to fewer than
1213             * (significandLength + 1) bits. This must be done with the original
1214             * quotient and not with the current significand, because the loss
1215             * of precision in the previous rounding might cause a rounding of
1216             * the current significand's value to produce a different result
1217             * than a rounding of the original quotient.
1218             *
1219             * So we find out how many high-order bits from the quotient we can
1220             * transfer into the significand. The absolute value of the fraction
1221             * is:
1222             *
1223             * quotient * 2^(numRightShift - denRightShift)
1224             *
1225             * To get the significand, we need to right shift the quotient so
1226             * that the above exponent becomes (1 - exponentBias - significandLength)
1227             * (the unbiased exponent of a subnormal floating-point number is
1228             * defined as equivalent to the minimum unbiased exponent of a
1229             * normalized floating-point number, and (- significandLength)
1230             * because the significand will be treated as the fractional part).
1231             */
1232            significand = roundAndRightShift(quotient,
1233                                             (1 - exponentBias - significandLength) - (numRightShift - denRightShift),
1234                                             !divisor.equals(BigInteger.ONE)).longValue();
1235            exponent = 0L;
1236
1237            /*
1238             * Note: It is possible that an otherwise subnormal number will
1239             * round up to the smallest normal number. However, this special
1240             * case does not need to be treated separately, because the
1241             * overflowing highest-order bit of the significand will then simply
1242             * become the lowest-order bit of the exponent, increasing the
1243             * exponent from 0 to 1 and thus establishing the implicity of the
1244             * leading 1-bit.
1245             */
1246        }
1247
1248        return (sign << (significandLength + exponentLength)) |
1249            (exponent << significandLength) |
1250            significand;
1251    }
1252
1253    /**
1254     * Rounds an integer to the specified power of two (i.e. the minimum number of
1255     * low-order bits that must be zero) and performs a right-shift by this
1256     * amount. The rounding mode applied is round to nearest, with ties rounding
1257     * to even (meaning the prospective least significant bit must be zero). The
1258     * number can optionally be treated as though it contained at
1259     * least one 0-bit and one 1-bit in its fractional part, to influence the result in cases
1260     * that would otherwise be a tie.
1261     * @param value the number to round and right-shift
1262     * @param bits the power of two to which to round; must be positive
1263     * @param hasFractionalBits whether the number should be treated as though
1264     *                          it contained a non-zero fractional part
1265     * @return a {@code BigInteger} as described above
1266     * @throws IllegalArgumentException if {@code bits <= 0}
1267     */
1268    private static BigInteger roundAndRightShift(BigInteger value, int bits, boolean hasFractionalBits) {
1269        if (bits <= 0) {
1270            throw new IllegalArgumentException("bits: " + bits);
1271        }
1272
1273        BigInteger result = value.shiftRight(bits);
1274        if (value.testBit(bits - 1) &&
1275            (hasFractionalBits ||
1276             (value.getLowestSetBit() < bits - 1) ||
1277             value.testBit(bits))) {
1278            result = result.add(BigInteger.ONE); //round up
1279        }
1280
1281        return result;
1282    }
1283
1284    /**
1285     * Returns true if this fraction is zero.
1286     *
1287     * @return true if zero
1288     */
1289    private boolean isZero() {
1290        return numerator.signum() == 0;
1291    }
1292}