1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.math;
18
19import static com.google.common.base.Preconditions.checkArgument;
20import static com.google.common.math.DoubleUtils.IMPLICIT_BIT;
21import static com.google.common.math.DoubleUtils.SIGNIFICAND_BITS;
22import static com.google.common.math.DoubleUtils.getExponent;
23import static com.google.common.math.DoubleUtils.getSignificand;
24import static com.google.common.math.DoubleUtils.isFinite;
25import static com.google.common.math.DoubleUtils.isNormal;
26import static com.google.common.math.DoubleUtils.next;
27import static com.google.common.math.DoubleUtils.scaleNormalize;
28import static com.google.common.math.MathPreconditions.checkInRange;
29import static com.google.common.math.MathPreconditions.checkNonNegative;
30import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
31
32import java.math.BigInteger;
33import java.math.RoundingMode;
34
35import com.google.common.annotations.VisibleForTesting;
36import com.google.common.annotations.Beta;
37
38/**
39 * A class for arithmetic on doubles that is not covered by {@link java.lang.Math}.
40 *
41 * @author Louis Wasserman
42 * @since 11.0
43 */
44@Beta
45public final class DoubleMath {
46  /*
47   * This method returns a value y such that rounding y DOWN (towards zero) gives the same result
48   * as rounding x according to the specified mode.
49   */
50  static double roundIntermediate(double x, RoundingMode mode) {
51    if (!isFinite(x)) {
52      throw new ArithmeticException("input is infinite or NaN");
53    }
54    switch (mode) {
55      case UNNECESSARY:
56        checkRoundingUnnecessary(isMathematicalInteger(x));
57        return x;
58
59      case FLOOR:
60        return (x >= 0.0) ? x : Math.floor(x);
61
62      case CEILING:
63        return (x >= 0.0) ? Math.ceil(x) : x;
64
65      case DOWN:
66        return x;
67
68      case UP:
69        return (x >= 0.0) ? Math.ceil(x) : Math.floor(x);
70
71      case HALF_EVEN:
72        return Math.rint(x);
73
74      case HALF_UP:
75        if (isMathematicalInteger(x)) {
76          return x;
77        } else {
78          return (x >= 0.0) ? x + 0.5 : x - 0.5;
79        }
80
81      case HALF_DOWN:
82        if (isMathematicalInteger(x)) {
83          return x;
84        } else if (x >= 0.0) {
85          double z = x + 0.5;
86          return (z == x) ? x : next(z, false); // x + 0.5 - epsilon
87        } else {
88          double z = x - 0.5;
89          return (z == x) ? x : next(z, true); // x - 0.5 + epsilon
90        }
91
92      default:
93        throw new AssertionError();
94    }
95  }
96
97  /**
98   * Returns the {@code int} value that is equal to {@code x} rounded with the specified rounding
99   * mode, if possible.
100   *
101   * @throws ArithmeticException if
102   *         <ul>
103   *         <li>{@code x} is infinite or NaN
104   *         <li>{@code x}, after being rounded to a mathematical integer using the specified
105   *         rounding mode, is either less than {@code Integer.MIN_VALUE} or greater than {@code
106   *         Integer.MAX_VALUE}
107   *         <li>{@code x} is not a mathematical integer and {@code mode} is
108   *         {@link RoundingMode#UNNECESSARY}
109   *         </ul>
110   */
111  public static int roundToInt(double x, RoundingMode mode) {
112    double z = roundIntermediate(x, mode);
113    checkInRange(z > MIN_INT_AS_DOUBLE - 1.0 & z < MAX_INT_AS_DOUBLE + 1.0);
114    return (int) z;
115  }
116
117  private static final double MIN_INT_AS_DOUBLE = -0x1p31;
118  private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0;
119
120  /**
121   * Returns the {@code long} value that is equal to {@code x} rounded with the specified rounding
122   * mode, if possible.
123   *
124   * @throws ArithmeticException if
125   *         <ul>
126   *         <li>{@code x} is infinite or NaN
127   *         <li>{@code x}, after being rounded to a mathematical integer using the specified
128   *         rounding mode, is either less than {@code Long.MIN_VALUE} or greater than {@code
129   *         Long.MAX_VALUE}
130   *         <li>{@code x} is not a mathematical integer and {@code mode} is
131   *         {@link RoundingMode#UNNECESSARY}
132   *         </ul>
133   */
134  public static long roundToLong(double x, RoundingMode mode) {
135    double z = roundIntermediate(x, mode);
136    checkInRange(MIN_LONG_AS_DOUBLE - z < 1.0 & z < MAX_LONG_AS_DOUBLE_PLUS_ONE);
137    return (long) z;
138  }
139
140  private static final double MIN_LONG_AS_DOUBLE = -0x1p63;
141  /*
142   * We cannot store Long.MAX_VALUE as a double without losing precision.  Instead, we store
143   * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1.
144   */
145  private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63;
146
147  /**
148   * Returns the {@code BigInteger} value that is equal to {@code x} rounded with the specified
149   * rounding mode, if possible.
150   *
151   * @throws ArithmeticException if
152   *         <ul>
153   *         <li>{@code x} is infinite or NaN
154   *         <li>{@code x} is not a mathematical integer and {@code mode} is
155   *         {@link RoundingMode#UNNECESSARY}
156   *         </ul>
157   */
158  public static BigInteger roundToBigInteger(double x, RoundingMode mode) {
159    x = roundIntermediate(x, mode);
160    if (MIN_LONG_AS_DOUBLE - x < 1.0 & x < MAX_LONG_AS_DOUBLE_PLUS_ONE) {
161      return BigInteger.valueOf((long) x);
162    }
163    int exponent = getExponent(x);
164    if (exponent < 0) {
165      return BigInteger.ZERO;
166    }
167    long significand = getSignificand(x);
168    BigInteger result = BigInteger.valueOf(significand).shiftLeft(exponent - SIGNIFICAND_BITS);
169    return (x < 0) ? result.negate() : result;
170  }
171
172  /**
173   * Returns {@code true} if {@code x} is exactly equal to {@code 2^k} for some finite integer
174   * {@code k}.
175   */
176  public static boolean isPowerOfTwo(double x) {
177    return x > 0.0 && isFinite(x) && LongMath.isPowerOfTwo(getSignificand(x));
178  }
179
180  /**
181   * Returns the base 2 logarithm of a double value.
182   *
183   * <p>Special cases:
184   * <ul>
185   * <li>If {@code x} is NaN or less than zero, the result is NaN.
186   * <li>If {@code x} is positive infinity, the result is positive infinity.
187   * <li>If {@code x} is positive or negative zero, the result is negative infinity.
188   * </ul>
189   *
190   * <p>The computed result must be within 1 ulp of the exact result.
191   *
192   * <p>If the result of this method will be immediately rounded to an {@code int},
193   * {@link #log2(double, RoundingMode)} is faster.
194   */
195  public static double log2(double x) {
196    return Math.log(x) / LN_2; // surprisingly within 1 ulp according to tests
197  }
198
199  private static final double LN_2 = Math.log(2);
200
201  /**
202   * Returns the base 2 logarithm of a double value, rounded with the specified rounding mode to an
203   * {@code int}.
204   *
205   * <p>Regardless of the rounding mode, this is faster than {@code (int) log2(x)}.
206   *
207   * @throws IllegalArgumentException if {@code x <= 0.0}, {@code x} is NaN, or {@code x} is
208   *         infinite
209   */
210  @SuppressWarnings("fallthrough")
211  public static int log2(double x, RoundingMode mode) {
212    checkArgument(x > 0.0 && isFinite(x), "x must be positive and finite");
213    int exponent = getExponent(x);
214    if (!isNormal(x)) {
215      return log2(x * IMPLICIT_BIT, mode) - SIGNIFICAND_BITS;
216      // Do the calculation on a normal value.
217    }
218    // x is positive, finite, and normal
219    boolean increment;
220    switch (mode) {
221      case UNNECESSARY:
222        checkRoundingUnnecessary(isPowerOfTwo(x));
223        // fall through
224      case FLOOR:
225        increment = false;
226        break;
227      case CEILING:
228        increment = !isPowerOfTwo(x);
229        break;
230      case DOWN:
231        increment = exponent < 0 & !isPowerOfTwo(x);
232        break;
233      case UP:
234        increment = exponent >= 0 & !isPowerOfTwo(x);
235        break;
236      case HALF_DOWN:
237      case HALF_EVEN:
238      case HALF_UP:
239        double xScaled = scaleNormalize(x);
240        // sqrt(2) is irrational, and the spec is relative to the "exact numerical result,"
241        // so log2(x) is never exactly exponent + 0.5.
242        increment = (xScaled * xScaled) > 2.0;
243        break;
244      default:
245        throw new AssertionError();
246    }
247    return increment ? exponent + 1 : exponent;
248  }
249
250  /**
251   * Returns {@code true} if {@code x} represents a mathematical integer.
252   *
253   * <p>This is equivalent to, but not necessarily implemented as, the expression {@code
254   * !Double.isNaN(x) && !Double.isInfinite(x) && x == Math.rint(x)}.
255   */
256  public static boolean isMathematicalInteger(double x) {
257    return isFinite(x)
258        && (x == 0.0 || SIGNIFICAND_BITS
259            - Long.numberOfTrailingZeros(getSignificand(x)) <= getExponent(x));
260  }
261
262  /**
263   * Returns {@code n!}, that is, the product of the first {@code n} positive
264   * integers, {@code 1} if {@code n == 0}, or e n!}, or
265   * {@link Double#POSITIVE_INFINITY} if {@code n! > Double.MAX_VALUE}.
266   *
267   * <p>The result is within 1 ulp of the true value.
268   *
269   * @throws IllegalArgumentException if {@code n < 0}
270   */
271  public static double factorial(int n) {
272    checkNonNegative("n", n);
273    if (n > MAX_FACTORIAL) {
274      return Double.POSITIVE_INFINITY;
275    } else {
276      // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate
277      // result than multiplying by EVERY_SIXTEENTH_FACTORIAL[n >> 4] directly.
278      double accum = 1.0;
279      for (int i = 1 + (n & ~0xf); i <= n; i++) {
280        accum *= i;
281      }
282      return accum * EVERY_SIXTEENTH_FACTORIAL[n >> 4];
283    }
284  }
285
286  @VisibleForTesting
287  static final int MAX_FACTORIAL = 170;
288
289  @VisibleForTesting
290  static final double[] EVERY_SIXTEENTH_FACTORIAL = {
291      0x1.0p0,
292      0x1.30777758p44,
293      0x1.956ad0aae33a4p117,
294      0x1.ee69a78d72cb6p202,
295      0x1.fe478ee34844ap295,
296      0x1.c619094edabffp394,
297      0x1.3638dd7bd6347p498,
298      0x1.7cac197cfe503p605,
299      0x1.1e5dfc140e1e5p716,
300      0x1.8ce85fadb707ep829,
301      0x1.95d5f3d928edep945};
302}
303