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 }