```001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
009 *
010 * Unless required by applicable law or agreed to in writing, software
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
018
029import static java.lang.Math.abs;
030import static java.lang.Math.copySign;
031import static java.lang.Math.getExponent;
032import static java.lang.Math.log;
033import static java.lang.Math.rint;
034
037
038import java.math.BigInteger;
039import java.math.RoundingMode;
040
041/**
042 * A class for arithmetic on doubles that is not covered by {@link java.lang.Math}.
043 *
044 * @author Louis Wasserman
045 * @since 11.0
046 */
047public final class DoubleMath {
048  /*
049   * This method returns a value y such that rounding y DOWN (towards zero) gives the same result
050   * as rounding x according to the specified mode.
051   */
052  static double roundIntermediate(double x, RoundingMode mode) {
053    if (!isFinite(x)) {
054      throw new ArithmeticException("input is infinite or NaN");
055    }
056    switch (mode) {
057      case UNNECESSARY:
058        checkRoundingUnnecessary(isMathematicalInteger(x));
059        return x;
060
061      case FLOOR:
062        if (x >= 0.0 || isMathematicalInteger(x)) {
063          return x;
064        } else {
065          return x - 1.0;
066        }
067
068      case CEILING:
069        if (x <= 0.0 || isMathematicalInteger(x)) {
070          return x;
071        } else {
072          return x + 1.0;
073        }
074
075      case DOWN:
076        return x;
077
078      case UP:
079        if (isMathematicalInteger(x)) {
080          return x;
081        } else {
082          return x + Math.copySign(1.0, x);
083        }
084
085      case HALF_EVEN:
086        return rint(x);
087
088      case HALF_UP: {
089        double z = rint(x);
090        if (abs(x - z) == 0.5) {
091          return x + copySign(0.5, x);
092        } else {
093          return z;
094        }
095      }
096
097      case HALF_DOWN: {
098        double z = rint(x);
099        if (abs(x - z) == 0.5) {
100          return x;
101        } else {
102          return z;
103        }
104      }
105
106      default:
107        throw new AssertionError();
108    }
109  }
110
111  /**
112   * Returns the {@code int} value that is equal to {@code x} rounded with the specified rounding
113   * mode, if possible.
114   *
115   * @throws ArithmeticException if
116   *         <ul>
117   *         <li>{@code x} is infinite or NaN
118   *         <li>{@code x}, after being rounded to a mathematical integer using the specified
119   *         rounding mode, is either less than {@code Integer.MIN_VALUE} or greater than {@code
120   *         Integer.MAX_VALUE}
121   *         <li>{@code x} is not a mathematical integer and {@code mode} is
123   *         </ul>
124   */
125  public static int roundToInt(double x, RoundingMode mode) {
126    double z = roundIntermediate(x, mode);
127    checkInRange(z > MIN_INT_AS_DOUBLE - 1.0 & z < MAX_INT_AS_DOUBLE + 1.0);
128    return (int) z;
129  }
130
131  private static final double MIN_INT_AS_DOUBLE = -0x1p31;
132  private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0;
133
134  /**
135   * Returns the {@code long} value that is equal to {@code x} rounded with the specified rounding
136   * mode, if possible.
137   *
138   * @throws ArithmeticException if
139   *         <ul>
140   *         <li>{@code x} is infinite or NaN
141   *         <li>{@code x}, after being rounded to a mathematical integer using the specified
142   *         rounding mode, is either less than {@code Long.MIN_VALUE} or greater than {@code
143   *         Long.MAX_VALUE}
144   *         <li>{@code x} is not a mathematical integer and {@code mode} is
146   *         </ul>
147   */
148  public static long roundToLong(double x, RoundingMode mode) {
149    double z = roundIntermediate(x, mode);
150    checkInRange(MIN_LONG_AS_DOUBLE - z < 1.0 & z < MAX_LONG_AS_DOUBLE_PLUS_ONE);
151    return (long) z;
152  }
153
154  private static final double MIN_LONG_AS_DOUBLE = -0x1p63;
155  /*
156   * We cannot store Long.MAX_VALUE as a double without losing precision.  Instead, we store
157   * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1.
158   */
159  private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63;
160
161  /**
162   * Returns the {@code BigInteger} value that is equal to {@code x} rounded with the specified
163   * rounding mode, if possible.
164   *
165   * @throws ArithmeticException if
166   *         <ul>
167   *         <li>{@code x} is infinite or NaN
168   *         <li>{@code x} is not a mathematical integer and {@code mode} is
170   *         </ul>
171   */
172  public static BigInteger roundToBigInteger(double x, RoundingMode mode) {
173    x = roundIntermediate(x, mode);
174    if (MIN_LONG_AS_DOUBLE - x < 1.0 & x < MAX_LONG_AS_DOUBLE_PLUS_ONE) {
175      return BigInteger.valueOf((long) x);
176    }
177    int exponent = getExponent(x);
178    long significand = getSignificand(x);
179    BigInteger result = BigInteger.valueOf(significand).shiftLeft(exponent - SIGNIFICAND_BITS);
180    return (x < 0) ? result.negate() : result;
181  }
182
183  /**
184   * Returns {@code true} if {@code x} is exactly equal to {@code 2^k} for some finite integer
185   * {@code k}.
186   */
187  public static boolean isPowerOfTwo(double x) {
188    return x > 0.0 && isFinite(x) && LongMath.isPowerOfTwo(getSignificand(x));
189  }
190
191  /**
192   * Returns the base 2 logarithm of a double value.
193   *
194   * <p>Special cases:
195   * <ul>
196   * <li>If {@code x} is NaN or less than zero, the result is NaN.
197   * <li>If {@code x} is positive infinity, the result is positive infinity.
198   * <li>If {@code x} is positive or negative zero, the result is negative infinity.
199   * </ul>
200   *
201   * <p>The computed result is within 1 ulp of the exact result.
202   *
203   * <p>If the result of this method will be immediately rounded to an {@code int},
204   * {@link #log2(double, RoundingMode)} is faster.
205   */
206  public static double log2(double x) {
207    return log(x) / LN_2; // surprisingly within 1 ulp according to tests
208  }
209
210  private static final double LN_2 = log(2);
211
212  /**
213   * Returns the base 2 logarithm of a double value, rounded with the specified rounding mode to an
214   * {@code int}.
215   *
216   * <p>Regardless of the rounding mode, this is faster than {@code (int) log2(x)}.
217   *
218   * @throws IllegalArgumentException if {@code x <= 0.0}, {@code x} is NaN, or {@code x} is
219   *         infinite
220   */
221  @SuppressWarnings("fallthrough")
222  public static int log2(double x, RoundingMode mode) {
223    checkArgument(x > 0.0 && isFinite(x), "x must be positive and finite");
224    int exponent = getExponent(x);
225    if (!isNormal(x)) {
226      return log2(x * IMPLICIT_BIT, mode) - SIGNIFICAND_BITS;
227      // Do the calculation on a normal value.
228    }
229    // x is positive, finite, and normal
230    boolean increment;
231    switch (mode) {
232      case UNNECESSARY:
233        checkRoundingUnnecessary(isPowerOfTwo(x));
234        // fall through
235      case FLOOR:
236        increment = false;
237        break;
238      case CEILING:
239        increment = !isPowerOfTwo(x);
240        break;
241      case DOWN:
242        increment = exponent < 0 & !isPowerOfTwo(x);
243        break;
244      case UP:
245        increment = exponent >= 0 & !isPowerOfTwo(x);
246        break;
247      case HALF_DOWN:
248      case HALF_EVEN:
249      case HALF_UP:
250        double xScaled = scaleNormalize(x);
251        // sqrt(2) is irrational, and the spec is relative to the "exact numerical result,"
252        // so log2(x) is never exactly exponent + 0.5.
253        increment = (xScaled * xScaled) > 2.0;
254        break;
255      default:
256        throw new AssertionError();
257    }
258    return increment ? exponent + 1 : exponent;
259  }
260
261  /**
262   * Returns {@code true} if {@code x} represents a mathematical integer.
263   *
264   * <p>This is equivalent to, but not necessarily implemented as, the expression {@code
265   * !Double.isNaN(x) && !Double.isInfinite(x) && x == Math.rint(x)}.
266   */
267  public static boolean isMathematicalInteger(double x) {
268    return isFinite(x)
269        && (x == 0.0 ||
270            SIGNIFICAND_BITS - Long.numberOfTrailingZeros(getSignificand(x)) <= getExponent(x));
271  }
272
273  /**
274   * Returns {@code n!}, that is, the product of the first {@code n} positive
275   * integers, {@code 1} if {@code n == 0}, or e n!}, or
276   * {@link Double#POSITIVE_INFINITY} if {@code n! > Double.MAX_VALUE}.
277   *
278   * <p>The result is within 1 ulp of the true value.
279   *
280   * @throws IllegalArgumentException if {@code n < 0}
281   */
282  public static double factorial(int n) {
283    checkNonNegative("n", n);
284    if (n > MAX_FACTORIAL) {
285      return Double.POSITIVE_INFINITY;
286    } else {
287      // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate
288      // result than multiplying by everySixteenthFactorial[n >> 4] directly.
289      double accum = 1.0;
290      for (int i = 1 + (n & ~0xf); i <= n; i++) {
291        accum *= i;
292      }
293      return accum * everySixteenthFactorial[n >> 4];
294    }
295  }
296
297  @VisibleForTesting
298  static final int MAX_FACTORIAL = 170;
299
300  @VisibleForTesting
301  static final double[] everySixteenthFactorial = {
302      0x1.0p0,
303      0x1.30777758p44,
305      0x1.ee69a78d72cb6p202,
306      0x1.fe478ee34844ap295,
307      0x1.c619094edabffp394,
308      0x1.3638dd7bd6347p498,
309      0x1.7cac197cfe503p605,
310      0x1.1e5dfc140e1e5p716,
312      0x1.95d5f3d928edep945};
313
314  /**
315   * Returns {@code true} if {@code a} and {@code b} are within {@code tolerance} of each other.
316   *
317   * <p>Technically speaking, this is equivalent to
318   * {@code Math.abs(a - b) <= tolerance || Double.valueOf(a).equals(Double.valueOf(b))}.
319   *
320   * <p>Notable special cases include:
321   * <ul>
322   * <li>All NaNs are fuzzily equal.
323   * <li>If {@code a == b}, then {@code a} and {@code b} are always fuzzily equal.
324   * <li>Positive and negative zero are always fuzzily equal.
325   * <li>If {@code tolerance} is zero, and neither {@code a} nor {@code b} is NaN, then
326   * {@code a} and {@code b} are fuzzily equal if and only if {@code a == b}.
327   * <li>With {@link Double#POSITIVE_INFINITY} tolerance, all non-NaN values are fuzzily equal.
328   * <li>With finite tolerance, {@code Double.POSITIVE_INFINITY} and {@code
329   * Double.NEGATIVE_INFINITY} are fuzzily equal only to themselves.
330   * </li>
331   *
332   * <p>This is reflexive and symmetric, but <em>not</em> transitive, so it is <em>not</em> an
333   * equivalence relation and <em>not</em> suitable for use in {@link Object#equals}
334   * implementations.
335   *
336   * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
337   * @since 13.0
338   */
339  public static boolean fuzzyEquals(double a, double b, double tolerance) {
340    MathPreconditions.checkNonNegative("tolerance", tolerance);
341    return
342          Math.copySign(a - b, 1.0) <= tolerance
343           // copySign(x, 1.0) is a branch-free version of abs(x), but with different NaN semantics
344          || (a == b) // needed to ensure that infinities equal themselves
345          || ((a != a) && (b != b)); // x != x is equivalent to Double.isNaN(x), but faster
346  }
347
348  /**
349   * Compares {@code a} and {@code b} "fuzzily," with a tolerance for nearly-equal values.
350   *
351   * <p>This method is equivalent to
352   * {@code fuzzyEquals(a, b, tolerance) ? 0 : Double.compare(a, b)}. In particular, like
353   * {@link Double#compare(double, double)}, it treats all NaN values as equal and greater than all
354   * other values (including {@link Double#POSITIVE_INFINITY}).
355   *
356   * <p>This is <em>not</em> a total ordering and is <em>not</em> suitable for use in
357   * {@link Comparable#compareTo} implementations.  In particular, it is not transitive.
358   *
359   * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
360   * @since 13.0
361   */
362  public static int fuzzyCompare(double a, double b, double tolerance) {
363    if (fuzzyEquals(a, b, tolerance)) {
364      return 0;
365    } else if (a < b) {
366      return -1;
367    } else if (a > b) {
368      return 1;
369    } else {
370      return Booleans.compare(Double.isNaN(a), Double.isNaN(b));
371    }
372  }
373
374  private DoubleMath() {}
375}

```