Source code

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