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
017 package com.google.common.math;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.math.DoubleUtils.IMPLICIT_BIT;
021 import static com.google.common.math.DoubleUtils.SIGNIFICAND_BITS;
022 import static com.google.common.math.DoubleUtils.getSignificand;
023 import static com.google.common.math.DoubleUtils.isFinite;
024 import static com.google.common.math.DoubleUtils.isNormal;
025 import static com.google.common.math.DoubleUtils.scaleNormalize;
026 import static com.google.common.math.MathPreconditions.checkInRange;
027 import static com.google.common.math.MathPreconditions.checkNonNegative;
028 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
029
030 import com.google.common.annotations.Beta;
031 import com.google.common.annotations.VisibleForTesting;
032
033 import java.math.BigInteger;
034 import java.math.RoundingMode;
035
036 /**
037 * A class for arithmetic on doubles that is not covered by {@link java.lang.Math}.
038 *
039 * @author Louis Wasserman
040 * @since 11.0
041 */
042 @Beta
043 public final class DoubleMath {
044 /*
045 * This method returns a value y such that rounding y DOWN (towards zero) gives the same result
046 * as rounding x according to the specified mode.
047 */
048 static double roundIntermediate(double x, RoundingMode mode) {
049 if (!isFinite(x)) {
050 throw new ArithmeticException("input is infinite or NaN");
051 }
052 switch (mode) {
053 case UNNECESSARY:
054 checkRoundingUnnecessary(isMathematicalInteger(x));
055 return x;
056
057 case FLOOR:
058 return (x >= 0.0) ? x : Math.floor(x);
059
060 case CEILING:
061 return (x >= 0.0) ? Math.ceil(x) : x;
062
063 case DOWN:
064 return x;
065
066 case UP:
067 return (x >= 0.0) ? Math.ceil(x) : Math.floor(x);
068
069 case HALF_EVEN:
070 return Math.rint(x);
071
072 case HALF_UP:
073 if (isMathematicalInteger(x)) {
074 return x;
075 } else {
076 return (x >= 0.0) ? x + 0.5 : x - 0.5;
077 }
078
079 case HALF_DOWN:
080 if (isMathematicalInteger(x)) {
081 return x;
082 } else if (x >= 0.0) {
083 double z = x + 0.5;
084 return (z == x) ? x : DoubleUtils.nextDown(z); // x + 0.5 - epsilon
085 } else {
086 double z = x - 0.5;
087 return (z == x) ? x : Math.nextUp(z); // x - 0.5 + epsilon
088 }
089
090 default:
091 throw new AssertionError();
092 }
093 }
094
095 /**
096 * Returns the {@code int} value that is equal to {@code x} rounded with the specified rounding
097 * mode, if possible.
098 *
099 * @throws ArithmeticException if
100 * <ul>
101 * <li>{@code x} is infinite or NaN
102 * <li>{@code x}, after being rounded to a mathematical integer using the specified
103 * rounding mode, is either less than {@code Integer.MIN_VALUE} or greater than {@code
104 * Integer.MAX_VALUE}
105 * <li>{@code x} is not a mathematical integer and {@code mode} is
106 * {@link RoundingMode#UNNECESSARY}
107 * </ul>
108 */
109 public static int roundToInt(double x, RoundingMode mode) {
110 double z = roundIntermediate(x, mode);
111 checkInRange(z > MIN_INT_AS_DOUBLE - 1.0 & z < MAX_INT_AS_DOUBLE + 1.0);
112 return (int) z;
113 }
114
115 private static final double MIN_INT_AS_DOUBLE = -0x1p31;
116 private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0;
117
118 /**
119 * Returns the {@code long} value that is equal to {@code x} rounded with the specified rounding
120 * mode, if possible.
121 *
122 * @throws ArithmeticException if
123 * <ul>
124 * <li>{@code x} is infinite or NaN
125 * <li>{@code x}, after being rounded to a mathematical integer using the specified
126 * rounding mode, is either less than {@code Long.MIN_VALUE} or greater than {@code
127 * Long.MAX_VALUE}
128 * <li>{@code x} is not a mathematical integer and {@code mode} is
129 * {@link RoundingMode#UNNECESSARY}
130 * </ul>
131 */
132 public static long roundToLong(double x, RoundingMode mode) {
133 double z = roundIntermediate(x, mode);
134 checkInRange(MIN_LONG_AS_DOUBLE - z < 1.0 & z < MAX_LONG_AS_DOUBLE_PLUS_ONE);
135 return (long) z;
136 }
137
138 private static final double MIN_LONG_AS_DOUBLE = -0x1p63;
139 /*
140 * We cannot store Long.MAX_VALUE as a double without losing precision. Instead, we store
141 * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1.
142 */
143 private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63;
144
145 /**
146 * Returns the {@code BigInteger} value that is equal to {@code x} rounded with the specified
147 * rounding mode, if possible.
148 *
149 * @throws ArithmeticException if
150 * <ul>
151 * <li>{@code x} is infinite or NaN
152 * <li>{@code x} is not a mathematical integer and {@code mode} is
153 * {@link RoundingMode#UNNECESSARY}
154 * </ul>
155 */
156 public static BigInteger roundToBigInteger(double x, RoundingMode mode) {
157 x = roundIntermediate(x, mode);
158 if (MIN_LONG_AS_DOUBLE - x < 1.0 & x < MAX_LONG_AS_DOUBLE_PLUS_ONE) {
159 return BigInteger.valueOf((long) x);
160 }
161 int exponent = Math.getExponent(x);
162 if (exponent < 0) {
163 return BigInteger.ZERO;
164 }
165 long significand = getSignificand(x);
166 BigInteger result = BigInteger.valueOf(significand).shiftLeft(exponent - SIGNIFICAND_BITS);
167 return (x < 0) ? result.negate() : result;
168 }
169
170 /**
171 * Returns {@code true} if {@code x} is exactly equal to {@code 2^k} for some finite integer
172 * {@code k}.
173 */
174 public static boolean isPowerOfTwo(double x) {
175 return x > 0.0 && isFinite(x) && LongMath.isPowerOfTwo(getSignificand(x));
176 }
177
178 /**
179 * Returns the base 2 logarithm of a double value.
180 *
181 * <p>Special cases:
182 * <ul>
183 * <li>If {@code x} is NaN or less than zero, the result is NaN.
184 * <li>If {@code x} is positive infinity, the result is positive infinity.
185 * <li>If {@code x} is positive or negative zero, the result is negative infinity.
186 * </ul>
187 *
188 * <p>The computed result must be within 1 ulp of the exact result.
189 *
190 * <p>If the result of this method will be immediately rounded to an {@code int},
191 * {@link #log2(double, RoundingMode)} is faster.
192 */
193 public static double log2(double x) {
194 return Math.log(x) / LN_2; // surprisingly within 1 ulp according to tests
195 }
196
197 private static final double LN_2 = Math.log(2);
198
199 /**
200 * Returns the base 2 logarithm of a double value, rounded with the specified rounding mode to an
201 * {@code int}.
202 *
203 * <p>Regardless of the rounding mode, this is faster than {@code (int) log2(x)}.
204 *
205 * @throws IllegalArgumentException if {@code x <= 0.0}, {@code x} is NaN, or {@code x} is
206 * infinite
207 */
208 @SuppressWarnings("fallthrough")
209 public static int log2(double x, RoundingMode mode) {
210 checkArgument(x > 0.0 && isFinite(x), "x must be positive and finite");
211 int exponent = Math.getExponent(x);
212 if (!isNormal(x)) {
213 return log2(x * IMPLICIT_BIT, mode) - SIGNIFICAND_BITS;
214 // Do the calculation on a normal value.
215 }
216 // x is positive, finite, and normal
217 boolean increment;
218 switch (mode) {
219 case UNNECESSARY:
220 checkRoundingUnnecessary(isPowerOfTwo(x));
221 // fall through
222 case FLOOR:
223 increment = false;
224 break;
225 case CEILING:
226 increment = !isPowerOfTwo(x);
227 break;
228 case DOWN:
229 increment = exponent < 0 & !isPowerOfTwo(x);
230 break;
231 case UP:
232 increment = exponent >= 0 & !isPowerOfTwo(x);
233 break;
234 case HALF_DOWN:
235 case HALF_EVEN:
236 case HALF_UP:
237 double xScaled = scaleNormalize(x);
238 // sqrt(2) is irrational, and the spec is relative to the "exact numerical result,"
239 // so log2(x) is never exactly exponent + 0.5.
240 increment = (xScaled * xScaled) > 2.0;
241 break;
242 default:
243 throw new AssertionError();
244 }
245 return increment ? exponent + 1 : exponent;
246 }
247
248 /**
249 * Returns {@code true} if {@code x} represents a mathematical integer.
250 *
251 * <p>This is equivalent to, but not necessarily implemented as, the expression {@code
252 * !Double.isNaN(x) && !Double.isInfinite(x) && x == Math.rint(x)}.
253 */
254 public static boolean isMathematicalInteger(double x) {
255 return isFinite(x)
256 && (x == 0.0 || SIGNIFICAND_BITS
257 - Long.numberOfTrailingZeros(getSignificand(x)) <= Math.getExponent(x));
258 }
259
260 /**
261 * Returns {@code n!}, that is, the product of the first {@code n} positive
262 * integers, {@code 1} if {@code n == 0}, or e n!}, or
263 * {@link Double#POSITIVE_INFINITY} if {@code n! > Double.MAX_VALUE}.
264 *
265 * <p>The result is within 1 ulp of the true value.
266 *
267 * @throws IllegalArgumentException if {@code n < 0}
268 */
269 public static double factorial(int n) {
270 checkNonNegative("n", n);
271 if (n > MAX_FACTORIAL) {
272 return Double.POSITIVE_INFINITY;
273 } else {
274 // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate
275 // result than multiplying by EVERY_SIXTEENTH_FACTORIAL[n >> 4] directly.
276 double accum = 1.0;
277 for (int i = 1 + (n & ~0xf); i <= n; i++) {
278 accum *= i;
279 }
280 return accum * EVERY_SIXTEENTH_FACTORIAL[n >> 4];
281 }
282 }
283
284 @VisibleForTesting
285 static final int MAX_FACTORIAL = 170;
286
287 @VisibleForTesting
288 static final double[] EVERY_SIXTEENTH_FACTORIAL = {
289 0x1.0p0,
290 0x1.30777758p44,
291 0x1.956ad0aae33a4p117,
292 0x1.ee69a78d72cb6p202,
293 0x1.fe478ee34844ap295,
294 0x1.c619094edabffp394,
295 0x1.3638dd7bd6347p498,
296 0x1.7cac197cfe503p605,
297 0x1.1e5dfc140e1e5p716,
298 0x1.8ce85fadb707ep829,
299 0x1.95d5f3d928edep945};
300
301 private DoubleMath() {}
302 }