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