001    /*
002     * Copyright (C) 2011 The Guava Authors
003     *
004     * Licensed under the Apache License, Version 2.0 (the "License");
005     * you may not use this file except in compliance with the License.
006     * You may obtain a copy of the License at
007     *
008     * http://www.apache.org/licenses/LICENSE-2.0
009     *
010     * Unless required by applicable law or agreed to in writing, software
011     * distributed under the License is distributed on an "AS IS" BASIS,
012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013     * See the License for the specific language governing permissions and
014     * limitations under the License.
015     */
016    
017    package com.google.common.math;
018    
019    import static com.google.common.base.Preconditions.checkArgument;
020    import static com.google.common.math.DoubleUtils.IMPLICIT_BIT;
021    import static com.google.common.math.DoubleUtils.SIGNIFICAND_BITS;
022    import static com.google.common.math.DoubleUtils.getExponent;
023    import static com.google.common.math.DoubleUtils.getSignificand;
024    import static com.google.common.math.DoubleUtils.isFinite;
025    import static com.google.common.math.DoubleUtils.isNormal;
026    import static com.google.common.math.DoubleUtils.next;
027    import static com.google.common.math.DoubleUtils.scaleNormalize;
028    import static com.google.common.math.MathPreconditions.checkInRange;
029    import static com.google.common.math.MathPreconditions.checkNonNegative;
030    import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
031    
032    import java.math.BigInteger;
033    import java.math.RoundingMode;
034    
035    import com.google.common.annotations.VisibleForTesting;
036    import com.google.common.annotations.Beta;
037    
038    /**
039     * A class for arithmetic on doubles that is not covered by {@link java.lang.Math}.
040     *
041     * @author Louis Wasserman
042     * @since 11.0
043     */
044    @Beta
045    public final class DoubleMath {
046      /*
047       * This method returns a value y such that rounding y DOWN (towards zero) gives the same result
048       * as rounding x according to the specified mode.
049       */
050      static double roundIntermediate(double x, RoundingMode mode) {
051        if (!isFinite(x)) {
052          throw new ArithmeticException("input is infinite or NaN");
053        }
054        switch (mode) {
055          case UNNECESSARY:
056            checkRoundingUnnecessary(isMathematicalInteger(x));
057            return x;
058    
059          case FLOOR:
060            return (x >= 0.0) ? x : Math.floor(x);
061    
062          case CEILING:
063            return (x >= 0.0) ? Math.ceil(x) : x;
064    
065          case DOWN:
066            return x;
067    
068          case UP:
069            return (x >= 0.0) ? Math.ceil(x) : Math.floor(x);
070    
071          case HALF_EVEN:
072            return Math.rint(x);
073    
074          case HALF_UP:
075            if (isMathematicalInteger(x)) {
076              return x;
077            } else {
078              return (x >= 0.0) ? x + 0.5 : x - 0.5;
079            }
080    
081          case HALF_DOWN:
082            if (isMathematicalInteger(x)) {
083              return x;
084            } else if (x >= 0.0) {
085              double z = x + 0.5;
086              return (z == x) ? x : next(z, false); // x + 0.5 - epsilon
087            } else {
088              double z = x - 0.5;
089              return (z == x) ? x : next(z, true); // x - 0.5 + epsilon
090            }
091    
092          default:
093            throw new AssertionError();
094        }
095      }
096      
097      /**
098       * Returns the {@code int} value that is equal to {@code x} rounded with the specified rounding
099       * mode, if possible.
100       *
101       * @throws ArithmeticException if
102       *         <ul>
103       *         <li>{@code x} is infinite or NaN
104       *         <li>{@code x}, after being rounded to a mathematical integer using the specified
105       *         rounding mode, is either less than {@code Integer.MIN_VALUE} or greater than {@code
106       *         Integer.MAX_VALUE}
107       *         <li>{@code x} is not a mathematical integer and {@code mode} is
108       *         {@link RoundingMode#UNNECESSARY}
109       *         </ul>
110       */
111      public static int roundToInt(double x, RoundingMode mode) {
112        double z = roundIntermediate(x, mode);
113        checkInRange(z > MIN_INT_AS_DOUBLE - 1.0 & z < MAX_INT_AS_DOUBLE + 1.0);
114        return (int) z;
115      }
116    
117      private static final double MIN_INT_AS_DOUBLE = -0x1p31;
118      private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0;
119    
120      /**
121       * Returns the {@code long} value that is equal to {@code x} rounded with the specified rounding
122       * mode, if possible.
123       *
124       * @throws ArithmeticException if
125       *         <ul>
126       *         <li>{@code x} is infinite or NaN
127       *         <li>{@code x}, after being rounded to a mathematical integer using the specified
128       *         rounding mode, is either less than {@code Long.MIN_VALUE} or greater than {@code
129       *         Long.MAX_VALUE}
130       *         <li>{@code x} is not a mathematical integer and {@code mode} is
131       *         {@link RoundingMode#UNNECESSARY}
132       *         </ul>
133       */
134      public static long roundToLong(double x, RoundingMode mode) {
135        double z = roundIntermediate(x, mode);
136        checkInRange(MIN_LONG_AS_DOUBLE - z < 1.0 & z < MAX_LONG_AS_DOUBLE_PLUS_ONE);
137        return (long) z;
138      }
139    
140      private static final double MIN_LONG_AS_DOUBLE = -0x1p63;
141      /*
142       * We cannot store Long.MAX_VALUE as a double without losing precision.  Instead, we store
143       * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1.
144       */
145      private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63;
146    
147      /**
148       * Returns the {@code BigInteger} value that is equal to {@code x} rounded with the specified
149       * rounding mode, if possible.
150       *
151       * @throws ArithmeticException if
152       *         <ul>
153       *         <li>{@code x} is infinite or NaN
154       *         <li>{@code x} is not a mathematical integer and {@code mode} is
155       *         {@link RoundingMode#UNNECESSARY}
156       *         </ul>
157       */
158      public static BigInteger roundToBigInteger(double x, RoundingMode mode) {
159        x = roundIntermediate(x, mode);
160        if (MIN_LONG_AS_DOUBLE - x < 1.0 & x < MAX_LONG_AS_DOUBLE_PLUS_ONE) {
161          return BigInteger.valueOf((long) x);
162        }
163        int exponent = getExponent(x);
164        if (exponent < 0) {
165          return BigInteger.ZERO;
166        }
167        long significand = getSignificand(x);
168        BigInteger result = BigInteger.valueOf(significand).shiftLeft(exponent - SIGNIFICAND_BITS);
169        return (x < 0) ? result.negate() : result;
170      }
171    
172      /**
173       * Returns {@code true} if {@code x} is exactly equal to {@code 2^k} for some finite integer
174       * {@code k}.
175       */
176      public static boolean isPowerOfTwo(double x) {
177        return x > 0.0 && isFinite(x) && LongMath.isPowerOfTwo(getSignificand(x));
178      }
179    
180      /**
181       * Returns the base 2 logarithm of a double value.
182       *
183       * <p>Special cases:
184       * <ul>
185       * <li>If {@code x} is NaN or less than zero, the result is NaN.
186       * <li>If {@code x} is positive infinity, the result is positive infinity.
187       * <li>If {@code x} is positive or negative zero, the result is negative infinity.
188       * </ul>
189       *
190       * <p>The computed result must be within 1 ulp of the exact result.
191       *
192       * <p>If the result of this method will be immediately rounded to an {@code int},
193       * {@link #log2(double, RoundingMode)} is faster.
194       */
195      public static double log2(double x) {
196        return Math.log(x) / LN_2; // surprisingly within 1 ulp according to tests
197      }
198    
199      private static final double LN_2 = Math.log(2);
200    
201      /**
202       * Returns the base 2 logarithm of a double value, rounded with the specified rounding mode to an
203       * {@code int}.
204       *
205       * <p>Regardless of the rounding mode, this is faster than {@code (int) log2(x)}.
206       *
207       * @throws IllegalArgumentException if {@code x <= 0.0}, {@code x} is NaN, or {@code x} is
208       *         infinite
209       */
210      @SuppressWarnings("fallthrough")
211      public static int log2(double x, RoundingMode mode) {
212        checkArgument(x > 0.0 && isFinite(x), "x must be positive and finite");
213        int exponent = getExponent(x);
214        if (!isNormal(x)) {
215          return log2(x * IMPLICIT_BIT, mode) - SIGNIFICAND_BITS;
216          // Do the calculation on a normal value.
217        }
218        // x is positive, finite, and normal
219        boolean increment;
220        switch (mode) {
221          case UNNECESSARY:
222            checkRoundingUnnecessary(isPowerOfTwo(x));
223            // fall through
224          case FLOOR:
225            increment = false;
226            break;
227          case CEILING:
228            increment = !isPowerOfTwo(x);
229            break;
230          case DOWN:
231            increment = exponent < 0 & !isPowerOfTwo(x);
232            break;
233          case UP:
234            increment = exponent >= 0 & !isPowerOfTwo(x);
235            break;
236          case HALF_DOWN:
237          case HALF_EVEN:
238          case HALF_UP:
239            double xScaled = scaleNormalize(x);
240            // sqrt(2) is irrational, and the spec is relative to the "exact numerical result,"
241            // so log2(x) is never exactly exponent + 0.5.
242            increment = (xScaled * xScaled) > 2.0;
243            break;
244          default:
245            throw new AssertionError();
246        }
247        return increment ? exponent + 1 : exponent;
248      }
249    
250      /**
251       * Returns {@code true} if {@code x} represents a mathematical integer.
252       * 
253       * <p>This is equivalent to, but not necessarily implemented as, the expression {@code
254       * !Double.isNaN(x) && !Double.isInfinite(x) && x == Math.rint(x)}.
255       */
256      public static boolean isMathematicalInteger(double x) {
257        return isFinite(x)
258            && (x == 0.0 || SIGNIFICAND_BITS
259                - Long.numberOfTrailingZeros(getSignificand(x)) <= getExponent(x));
260      }
261    
262      /**
263       * Returns {@code n!}, that is, the product of the first {@code n} positive
264       * integers, {@code 1} if {@code n == 0}, or e n!}, or
265       * {@link Double#POSITIVE_INFINITY} if {@code n! > Double.MAX_VALUE}.
266       *
267       * <p>The result is within 1 ulp of the true value.
268       *
269       * @throws IllegalArgumentException if {@code n < 0}
270       */
271      public static double factorial(int n) {
272        checkNonNegative("n", n);
273        if (n > MAX_FACTORIAL) {
274          return Double.POSITIVE_INFINITY;
275        } else {
276          // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate
277          // result than multiplying by EVERY_SIXTEENTH_FACTORIAL[n >> 4] directly.
278          double accum = 1.0;
279          for (int i = 1 + (n & ~0xf); i <= n; i++) {
280            accum *= i;
281          }
282          return accum * EVERY_SIXTEENTH_FACTORIAL[n >> 4];
283        }
284      }
285    
286      @VisibleForTesting
287      static final int MAX_FACTORIAL = 170;
288    
289      @VisibleForTesting
290      static final double[] EVERY_SIXTEENTH_FACTORIAL = {
291          0x1.0p0,
292          0x1.30777758p44,
293          0x1.956ad0aae33a4p117,
294          0x1.ee69a78d72cb6p202,
295          0x1.fe478ee34844ap295,
296          0x1.c619094edabffp394,
297          0x1.3638dd7bd6347p498,
298          0x1.7cac197cfe503p605,
299          0x1.1e5dfc140e1e5p716,
300          0x1.8ce85fadb707ep829,
301          0x1.95d5f3d928edep945};
302    }