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