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.getExponent;
023 import static com.google.common.math.DoubleUtils.getSignificand;
024 import static com.google.common.math.DoubleUtils.isFinite;
025 import static com.google.common.math.DoubleUtils.isNormal;
026 import static com.google.common.math.DoubleUtils.next;
027 import static com.google.common.math.DoubleUtils.scaleNormalize;
028 import static com.google.common.math.MathPreconditions.checkInRange;
029 import static com.google.common.math.MathPreconditions.checkNonNegative;
030 import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary;
031
032 import java.math.BigInteger;
033 import java.math.RoundingMode;
034
035 import com.google.common.annotations.VisibleForTesting;
036 import com.google.common.annotations.Beta;
037
038 /**
039 * A class for arithmetic on doubles that is not covered by {@link java.lang.Math}.
040 *
041 * @author Louis Wasserman
042 * @since 11.0
043 */
044 @Beta
045 public final class DoubleMath {
046 /*
047 * This method returns a value y such that rounding y DOWN (towards zero) gives the same result
048 * as rounding x according to the specified mode.
049 */
050 static double roundIntermediate(double x, RoundingMode mode) {
051 if (!isFinite(x)) {
052 throw new ArithmeticException("input is infinite or NaN");
053 }
054 switch (mode) {
055 case UNNECESSARY:
056 checkRoundingUnnecessary(isMathematicalInteger(x));
057 return x;
058
059 case FLOOR:
060 return (x >= 0.0) ? x : Math.floor(x);
061
062 case CEILING:
063 return (x >= 0.0) ? Math.ceil(x) : x;
064
065 case DOWN:
066 return x;
067
068 case UP:
069 return (x >= 0.0) ? Math.ceil(x) : Math.floor(x);
070
071 case HALF_EVEN:
072 return Math.rint(x);
073
074 case HALF_UP:
075 if (isMathematicalInteger(x)) {
076 return x;
077 } else {
078 return (x >= 0.0) ? x + 0.5 : x - 0.5;
079 }
080
081 case HALF_DOWN:
082 if (isMathematicalInteger(x)) {
083 return x;
084 } else if (x >= 0.0) {
085 double z = x + 0.5;
086 return (z == x) ? x : next(z, false); // x + 0.5 - epsilon
087 } else {
088 double z = x - 0.5;
089 return (z == x) ? x : next(z, true); // x - 0.5 + epsilon
090 }
091
092 default:
093 throw new AssertionError();
094 }
095 }
096
097 /**
098 * Returns the {@code int} value that is equal to {@code x} rounded with the specified rounding
099 * 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 }