001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.math;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.math.DoubleUtils.IMPLICIT_BIT;
019import static com.google.common.math.DoubleUtils.SIGNIFICAND_BITS;
020import static com.google.common.math.DoubleUtils.getSignificand;
021import static com.google.common.math.DoubleUtils.isFinite;
022import static com.google.common.math.DoubleUtils.isNormal;
023import static com.google.common.math.DoubleUtils.scaleNormalize;
024import static com.google.common.math.MathPreconditions.checkInRangeForRoundingInputs;
025import static com.google.common.math.MathPreconditions.checkNonNegative;
026import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
027import static java.lang.Math.abs;
028import static java.lang.Math.copySign;
029import static java.lang.Math.getExponent;
030import static java.lang.Math.log;
031import static java.lang.Math.rint;
032
033import com.google.common.annotations.GwtCompatible;
034import com.google.common.annotations.GwtIncompatible;
035import com.google.common.annotations.VisibleForTesting;
036import com.google.errorprone.annotations.CanIgnoreReturnValue;
037import java.math.BigInteger;
038import java.math.RoundingMode;
039import java.util.Iterator;
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 */
047@GwtCompatible(emulated = true)
048public final class DoubleMath {
049  /*
050   * This method returns a value y such that rounding y DOWN (towards zero) gives the same result as
051   * rounding x according to the specified mode.
052   */
053  @GwtIncompatible // #isMathematicalInteger, com.google.common.math.DoubleUtils
054  static double roundIntermediate(double x, RoundingMode mode) {
055    if (!isFinite(x)) {
056      throw new ArithmeticException("input is infinite or NaN");
057    }
058    switch (mode) {
059      case UNNECESSARY:
060        checkRoundingUnnecessary(isMathematicalInteger(x));
061        return x;
062
063      case FLOOR:
064        if (x >= 0.0 || isMathematicalInteger(x)) {
065          return x;
066        } else {
067          return (long) x - 1;
068        }
069
070      case CEILING:
071        if (x <= 0.0 || isMathematicalInteger(x)) {
072          return x;
073        } else {
074          return (long) x + 1;
075        }
076
077      case DOWN:
078        return x;
079
080      case UP:
081        if (isMathematicalInteger(x)) {
082          return x;
083        } else {
084          return (long) x + (x > 0 ? 1 : -1);
085        }
086
087      case HALF_EVEN:
088        return rint(x);
089
090      case HALF_UP:
091        {
092          double z = rint(x);
093          if (abs(x - z) == 0.5) {
094            return x + copySign(0.5, x);
095          } else {
096            return z;
097          }
098        }
099
100      case HALF_DOWN:
101        {
102          double z = rint(x);
103          if (abs(x - z) == 0.5) {
104            return x;
105          } else {
106            return z;
107          }
108        }
109    }
110    throw new AssertionError();
111  }
112
113  /**
114   * Returns the {@code int} value that is equal to {@code x} rounded with the specified rounding
115   * mode, if possible.
116   *
117   * @throws ArithmeticException if
118   *     <ul>
119   *       <li>{@code x} is infinite or NaN
120   *       <li>{@code x}, after being rounded to a mathematical integer using the specified rounding
121   *           mode, is either less than {@code Integer.MIN_VALUE} or greater than {@code
122   *           Integer.MAX_VALUE}
123   *       <li>{@code x} is not a mathematical integer and {@code mode} is {@link
124   *           RoundingMode#UNNECESSARY}
125   *     </ul>
126   */
127  @GwtIncompatible // #roundIntermediate
128  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
129  @SuppressWarnings("ShortCircuitBoolean")
130  public static int roundToInt(double x, RoundingMode mode) {
131    double z = roundIntermediate(x, mode);
132    checkInRangeForRoundingInputs(
133        z > MIN_INT_AS_DOUBLE - 1.0 & z < MAX_INT_AS_DOUBLE + 1.0, x, mode);
134    return (int) z;
135  }
136
137  private static final double MIN_INT_AS_DOUBLE = -0x1p31;
138  private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0;
139
140  /**
141   * Returns the {@code long} value that is equal to {@code x} rounded with the specified rounding
142   * mode, if possible.
143   *
144   * @throws ArithmeticException if
145   *     <ul>
146   *       <li>{@code x} is infinite or NaN
147   *       <li>{@code x}, after being rounded to a mathematical integer using the specified rounding
148   *           mode, is either less than {@code Long.MIN_VALUE} or greater than {@code
149   *           Long.MAX_VALUE}
150   *       <li>{@code x} is not a mathematical integer and {@code mode} is {@link
151   *           RoundingMode#UNNECESSARY}
152   *     </ul>
153   */
154  @GwtIncompatible // #roundIntermediate
155  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
156  @SuppressWarnings("ShortCircuitBoolean")
157  public static long roundToLong(double x, RoundingMode mode) {
158    double z = roundIntermediate(x, mode);
159    checkInRangeForRoundingInputs(
160        MIN_LONG_AS_DOUBLE - z < 1.0 & z < MAX_LONG_AS_DOUBLE_PLUS_ONE, x, mode);
161    return (long) z;
162  }
163
164  private static final double MIN_LONG_AS_DOUBLE = -0x1p63;
165  /*
166   * We cannot store Long.MAX_VALUE as a double without losing precision. Instead, we store
167   * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1.
168   */
169  private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63;
170
171  /**
172   * Returns the {@code BigInteger} value that is equal to {@code x} rounded with the specified
173   * rounding mode, if possible.
174   *
175   * @throws ArithmeticException if
176   *     <ul>
177   *       <li>{@code x} is infinite or NaN
178   *       <li>{@code x} is not a mathematical integer and {@code mode} is {@link
179   *           RoundingMode#UNNECESSARY}
180   *     </ul>
181   */
182  // #roundIntermediate, java.lang.Math.getExponent, com.google.common.math.DoubleUtils
183  @GwtIncompatible
184  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
185  @SuppressWarnings("ShortCircuitBoolean")
186  public static BigInteger roundToBigInteger(double x, RoundingMode mode) {
187    x = roundIntermediate(x, mode);
188    if (MIN_LONG_AS_DOUBLE - x < 1.0 & x < MAX_LONG_AS_DOUBLE_PLUS_ONE) {
189      return BigInteger.valueOf((long) x);
190    }
191    int exponent = getExponent(x);
192    long significand = getSignificand(x);
193    BigInteger result = BigInteger.valueOf(significand).shiftLeft(exponent - SIGNIFICAND_BITS);
194    return (x < 0) ? result.negate() : result;
195  }
196
197  /**
198   * Returns {@code true} if {@code x} is exactly equal to {@code 2^k} for some finite integer
199   * {@code k}.
200   */
201  @GwtIncompatible // com.google.common.math.DoubleUtils
202  public static boolean isPowerOfTwo(double x) {
203    if (x > 0.0 && isFinite(x)) {
204      long significand = getSignificand(x);
205      return (significand & (significand - 1)) == 0;
206    }
207    return false;
208  }
209
210  /**
211   * Returns the base 2 logarithm of a double value.
212   *
213   * <p>Special cases:
214   *
215   * <ul>
216   *   <li>If {@code x} is NaN or less than zero, the result is NaN.
217   *   <li>If {@code x} is positive infinity, the result is positive infinity.
218   *   <li>If {@code x} is positive or negative zero, the result is negative infinity.
219   * </ul>
220   *
221   * <p>The computed result is within 1 ulp of the exact result.
222   *
223   * <p>If the result of this method will be immediately rounded to an {@code int}, {@link
224   * #log2(double, RoundingMode)} is faster.
225   */
226  public static double log2(double x) {
227    return log(x) / LN_2; // surprisingly within 1 ulp according to tests
228  }
229
230  /**
231   * Returns the base 2 logarithm of a double value, rounded with the specified rounding mode to an
232   * {@code int}.
233   *
234   * <p>Regardless of the rounding mode, this is faster than {@code (int) log2(x)}.
235   *
236   * @throws IllegalArgumentException if {@code x <= 0.0}, {@code x} is NaN, or {@code x} is
237   *     infinite
238   */
239  @GwtIncompatible // java.lang.Math.getExponent, com.google.common.math.DoubleUtils
240  // Whenever both tests are cheap and functional, it's faster to use &, | instead of &&, ||
241  @SuppressWarnings({"fallthrough", "ShortCircuitBoolean"})
242  public static int log2(double x, RoundingMode mode) {
243    checkArgument(x > 0.0 && isFinite(x), "x must be positive and finite");
244    int exponent = getExponent(x);
245    if (!isNormal(x)) {
246      return log2(x * IMPLICIT_BIT, mode) - SIGNIFICAND_BITS;
247      // Do the calculation on a normal value.
248    }
249    // x is positive, finite, and normal
250    boolean increment;
251    switch (mode) {
252      case UNNECESSARY:
253        checkRoundingUnnecessary(isPowerOfTwo(x));
254        // fall through
255      case FLOOR:
256        increment = false;
257        break;
258      case CEILING:
259        increment = !isPowerOfTwo(x);
260        break;
261      case DOWN:
262        increment = exponent < 0 & !isPowerOfTwo(x);
263        break;
264      case UP:
265        increment = exponent >= 0 & !isPowerOfTwo(x);
266        break;
267      case HALF_DOWN:
268      case HALF_EVEN:
269      case HALF_UP:
270        double xScaled = scaleNormalize(x);
271        // sqrt(2) is irrational, and the spec is relative to the "exact numerical result,"
272        // so log2(x) is never exactly exponent + 0.5.
273        increment = (xScaled * xScaled) > 2.0;
274        break;
275      default:
276        throw new AssertionError();
277    }
278    return increment ? exponent + 1 : exponent;
279  }
280
281  private static final double LN_2 = log(2);
282
283  /**
284   * Returns {@code true} if {@code x} represents a mathematical integer.
285   *
286   * <p>This is equivalent to, but not necessarily implemented as, the expression {@code
287   * !Double.isNaN(x) && !Double.isInfinite(x) && x == Math.rint(x)}.
288   */
289  @GwtIncompatible // java.lang.Math.getExponent, com.google.common.math.DoubleUtils
290  public static boolean isMathematicalInteger(double x) {
291    return isFinite(x)
292        && (x == 0.0
293            || SIGNIFICAND_BITS - Long.numberOfTrailingZeros(getSignificand(x)) <= getExponent(x));
294  }
295
296  /**
297   * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if
298   * {@code n == 0}, or {@code n!}, or {@link Double#POSITIVE_INFINITY} if {@code n! >
299   * Double.MAX_VALUE}.
300   *
301   * <p>The result is within 1 ulp of the true value.
302   *
303   * @throws IllegalArgumentException if {@code n < 0}
304   */
305  public static double factorial(int n) {
306    checkNonNegative("n", n);
307    if (n > MAX_FACTORIAL) {
308      return Double.POSITIVE_INFINITY;
309    } else {
310      // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate
311      // result than multiplying by everySixteenthFactorial[n >> 4] directly.
312      double accum = 1.0;
313      for (int i = 1 + (n & ~0xf); i <= n; i++) {
314        accum *= i;
315      }
316      return accum * everySixteenthFactorial[n >> 4];
317    }
318  }
319
320  @VisibleForTesting static final int MAX_FACTORIAL = 170;
321
322  @VisibleForTesting
323  static final double[] everySixteenthFactorial = {
324    0x1.0p0,
325    0x1.30777758p44,
326    0x1.956ad0aae33a4p117,
327    0x1.ee69a78d72cb6p202,
328    0x1.fe478ee34844ap295,
329    0x1.c619094edabffp394,
330    0x1.3638dd7bd6347p498,
331    0x1.7cac197cfe503p605,
332    0x1.1e5dfc140e1e5p716,
333    0x1.8ce85fadb707ep829,
334    0x1.95d5f3d928edep945
335  };
336
337  /**
338   * Returns {@code true} if {@code a} and {@code b} are within {@code tolerance} of each other.
339   *
340   * <p>Technically speaking, this is equivalent to {@code Math.abs(a - b) <= tolerance ||
341   * Double.valueOf(a).equals(Double.valueOf(b))}.
342   *
343   * <p>Notable special cases include:
344   *
345   * <ul>
346   *   <li>All NaNs are fuzzily equal.
347   *   <li>If {@code a == b}, then {@code a} and {@code b} are always fuzzily equal.
348   *   <li>Positive and negative zero are always fuzzily equal.
349   *   <li>If {@code tolerance} is zero, and neither {@code a} nor {@code b} is NaN, then {@code a}
350   *       and {@code b} are fuzzily equal if and only if {@code a == b}.
351   *   <li>With {@link Double#POSITIVE_INFINITY} tolerance, all non-NaN values are fuzzily equal.
352   *   <li>With finite tolerance, {@code Double.POSITIVE_INFINITY} and {@code
353   *       Double.NEGATIVE_INFINITY} are fuzzily equal only to themselves.
354   * </ul>
355   *
356   * <p>This is reflexive and symmetric, but <em>not</em> transitive, so it is <em>not</em> an
357   * equivalence relation and <em>not</em> suitable for use in {@link Object#equals}
358   * implementations.
359   *
360   * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
361   * @since 13.0
362   */
363  public static boolean fuzzyEquals(double a, double b, double tolerance) {
364    MathPreconditions.checkNonNegative("tolerance", tolerance);
365    return Math.copySign(a - b, 1.0) <= tolerance
366        // copySign(x, 1.0) is a branch-free version of abs(x), but with different NaN semantics
367        || (a == b) // needed to ensure that infinities equal themselves
368        || (Double.isNaN(a) && Double.isNaN(b));
369  }
370
371  /**
372   * Compares {@code a} and {@code b} "fuzzily," with a tolerance for nearly-equal values.
373   *
374   * <p>This method is equivalent to {@code fuzzyEquals(a, b, tolerance) ? 0 : Double.compare(a,
375   * b)}. In particular, like {@link Double#compare(double, double)}, it treats all NaN values as
376   * equal and greater than all other values (including {@link Double#POSITIVE_INFINITY}).
377   *
378   * <p>This is <em>not</em> a total ordering and is <em>not</em> suitable for use in {@link
379   * Comparable#compareTo} implementations. In particular, it is not transitive.
380   *
381   * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
382   * @since 13.0
383   */
384  public static int fuzzyCompare(double a, double b, double tolerance) {
385    if (fuzzyEquals(a, b, tolerance)) {
386      return 0;
387    } else if (a < b) {
388      return -1;
389    } else if (a > b) {
390      return 1;
391    } else {
392      return Boolean.compare(Double.isNaN(a), Double.isNaN(b));
393    }
394  }
395
396  /**
397   * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of
398   * {@code values}.
399   *
400   * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of
401   * the arithmetic mean of the population.
402   *
403   * @param values a nonempty series of values
404   * @throws IllegalArgumentException if {@code values} is empty or contains any non-finite value
405   * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite
406   *     values.
407   */
408  @Deprecated
409  // com.google.common.math.DoubleUtils
410  @GwtIncompatible
411  public static double mean(double... values) {
412    checkArgument(values.length > 0, "Cannot take mean of 0 values");
413    long count = 1;
414    double mean = checkFinite(values[0]);
415    for (int index = 1; index < values.length; ++index) {
416      checkFinite(values[index]);
417      count++;
418      // Art of Computer Programming vol. 2, Knuth, 4.2.2, (15)
419      mean += (values[index] - mean) / count;
420    }
421    return mean;
422  }
423
424  /**
425   * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of
426   * {@code values}.
427   *
428   * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of
429   * the arithmetic mean of the population.
430   *
431   * @param values a nonempty series of values
432   * @throws IllegalArgumentException if {@code values} is empty
433   * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite
434   *     values.
435   */
436  @Deprecated
437  public static double mean(int... values) {
438    checkArgument(values.length > 0, "Cannot take mean of 0 values");
439    // The upper bound on the length of an array and the bounds on the int values mean that, in
440    // this case only, we can compute the sum as a long without risking overflow or loss of
441    // precision. So we do that, as it's slightly quicker than the Knuth algorithm.
442    long sum = 0;
443    for (int index = 0; index < values.length; ++index) {
444      sum += values[index];
445    }
446    return (double) sum / values.length;
447  }
448
449  /**
450   * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of
451   * {@code values}.
452   *
453   * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of
454   * the arithmetic mean of the population.
455   *
456   * @param values a nonempty series of values, which will be converted to {@code double} values
457   *     (this may cause loss of precision for longs of magnitude over 2^53 (slightly over 9e15))
458   * @throws IllegalArgumentException if {@code values} is empty
459   * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite
460   *     values.
461   */
462  @Deprecated
463  public static double mean(long... values) {
464    checkArgument(values.length > 0, "Cannot take mean of 0 values");
465    long count = 1;
466    double mean = values[0];
467    for (int index = 1; index < values.length; ++index) {
468      count++;
469      // Art of Computer Programming vol. 2, Knuth, 4.2.2, (15)
470      mean += (values[index] - mean) / count;
471    }
472    return mean;
473  }
474
475  /**
476   * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of
477   * {@code values}.
478   *
479   * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of
480   * the arithmetic mean of the population.
481   *
482   * @param values a nonempty series of values, which will be converted to {@code double} values
483   *     (this may cause loss of precision)
484   * @throws IllegalArgumentException if {@code values} is empty or contains any non-finite value
485   * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite
486   *     values.
487   */
488  @Deprecated
489  // com.google.common.math.DoubleUtils
490  @GwtIncompatible
491  public static double mean(Iterable<? extends Number> values) {
492    return mean(values.iterator());
493  }
494
495  /**
496   * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of
497   * {@code values}.
498   *
499   * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of
500   * the arithmetic mean of the population.
501   *
502   * @param values a nonempty series of values, which will be converted to {@code double} values
503   *     (this may cause loss of precision)
504   * @throws IllegalArgumentException if {@code values} is empty or contains any non-finite value
505   * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite
506   *     values.
507   */
508  @Deprecated
509  // com.google.common.math.DoubleUtils
510  @GwtIncompatible
511  public static double mean(Iterator<? extends Number> values) {
512    checkArgument(values.hasNext(), "Cannot take mean of 0 values");
513    long count = 1;
514    double mean = checkFinite(values.next().doubleValue());
515    while (values.hasNext()) {
516      double value = checkFinite(values.next().doubleValue());
517      count++;
518      // Art of Computer Programming vol. 2, Knuth, 4.2.2, (15)
519      mean += (value - mean) / count;
520    }
521    return mean;
522  }
523
524  @GwtIncompatible // com.google.common.math.DoubleUtils
525  @CanIgnoreReturnValue
526  private static double checkFinite(double argument) {
527    checkArgument(isFinite(argument));
528    return argument;
529  }
530
531  private DoubleMath() {}
532}