001/* 002 * Copyright (C) 2011 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.math; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.math.DoubleUtils.IMPLICIT_BIT; 019import static com.google.common.math.DoubleUtils.SIGNIFICAND_BITS; 020import static com.google.common.math.DoubleUtils.getSignificand; 021import static com.google.common.math.DoubleUtils.isFinite; 022import static com.google.common.math.DoubleUtils.isNormal; 023import static com.google.common.math.DoubleUtils.scaleNormalize; 024import static com.google.common.math.MathPreconditions.checkInRangeForRoundingInputs; 025import static com.google.common.math.MathPreconditions.checkNonNegative; 026import static com.google.common.math.MathPreconditions.checkRoundingUnnecessary; 027import static java.lang.Math.abs; 028import static java.lang.Math.copySign; 029import static java.lang.Math.getExponent; 030import static java.lang.Math.log; 031import static java.lang.Math.rint; 032 033import com.google.common.annotations.GwtCompatible; 034import com.google.common.annotations.GwtIncompatible; 035import com.google.common.annotations.VisibleForTesting; 036import com.google.common.primitives.Booleans; 037import com.google.errorprone.annotations.CanIgnoreReturnValue; 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 */ 048@GwtCompatible(emulated = true) 049public final class DoubleMath { 050 /* 051 * This method returns a value y such that rounding y DOWN (towards zero) gives the same result as 052 * rounding x according to the specified mode. 053 */ 054 @GwtIncompatible // #isMathematicalInteger, com.google.common.math.DoubleUtils 055 static double roundIntermediate(double x, RoundingMode mode) { 056 if (!isFinite(x)) { 057 throw new ArithmeticException("input is infinite or NaN"); 058 } 059 switch (mode) { 060 case UNNECESSARY: 061 checkRoundingUnnecessary(isMathematicalInteger(x)); 062 return x; 063 064 case FLOOR: 065 if (x >= 0.0 || isMathematicalInteger(x)) { 066 return x; 067 } else { 068 return (long) x - 1; 069 } 070 071 case CEILING: 072 if (x <= 0.0 || isMathematicalInteger(x)) { 073 return x; 074 } else { 075 return (long) x + 1; 076 } 077 078 case DOWN: 079 return x; 080 081 case UP: 082 if (isMathematicalInteger(x)) { 083 return x; 084 } else { 085 return (long) x + (x > 0 ? 1 : -1); 086 } 087 088 case HALF_EVEN: 089 return rint(x); 090 091 case HALF_UP: 092 { 093 double z = rint(x); 094 if (abs(x - z) == 0.5) { 095 return x + copySign(0.5, x); 096 } else { 097 return z; 098 } 099 } 100 101 case HALF_DOWN: 102 { 103 double z = rint(x); 104 if (abs(x - z) == 0.5) { 105 return x; 106 } else { 107 return z; 108 } 109 } 110 111 default: 112 throw new AssertionError(); 113 } 114 } 115 116 /** 117 * Returns the {@code int} value that is equal to {@code x} rounded with the specified rounding 118 * mode, if possible. 119 * 120 * @throws ArithmeticException if 121 * <ul> 122 * <li>{@code x} is infinite or NaN 123 * <li>{@code x}, after being rounded to a mathematical integer using the specified rounding 124 * mode, is either less than {@code Integer.MIN_VALUE} or greater than {@code 125 * Integer.MAX_VALUE} 126 * <li>{@code x} is not a mathematical integer and {@code mode} is {@link 127 * RoundingMode#UNNECESSARY} 128 * </ul> 129 */ 130 @GwtIncompatible // #roundIntermediate 131 public static int roundToInt(double x, RoundingMode mode) { 132 double z = roundIntermediate(x, mode); 133 checkInRangeForRoundingInputs( 134 z > MIN_INT_AS_DOUBLE - 1.0 & z < MAX_INT_AS_DOUBLE + 1.0, x, mode); 135 return (int) z; 136 } 137 138 private static final double MIN_INT_AS_DOUBLE = -0x1p31; 139 private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0; 140 141 /** 142 * Returns the {@code long} value that is equal to {@code x} rounded with the specified rounding 143 * mode, if possible. 144 * 145 * @throws ArithmeticException if 146 * <ul> 147 * <li>{@code x} is infinite or NaN 148 * <li>{@code x}, after being rounded to a mathematical integer using the specified rounding 149 * mode, is either less than {@code Long.MIN_VALUE} or greater than {@code 150 * Long.MAX_VALUE} 151 * <li>{@code x} is not a mathematical integer and {@code mode} is {@link 152 * RoundingMode#UNNECESSARY} 153 * </ul> 154 */ 155 @GwtIncompatible // #roundIntermediate 156 public static long roundToLong(double x, RoundingMode mode) { 157 double z = roundIntermediate(x, mode); 158 checkInRangeForRoundingInputs( 159 MIN_LONG_AS_DOUBLE - z < 1.0 & z < MAX_LONG_AS_DOUBLE_PLUS_ONE, x, mode); 160 return (long) z; 161 } 162 163 private static final double MIN_LONG_AS_DOUBLE = -0x1p63; 164 /* 165 * We cannot store Long.MAX_VALUE as a double without losing precision. Instead, we store 166 * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1. 167 */ 168 private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63; 169 170 /** 171 * Returns the {@code BigInteger} value that is equal to {@code x} rounded with the specified 172 * rounding mode, if possible. 173 * 174 * @throws ArithmeticException if 175 * <ul> 176 * <li>{@code x} is infinite or NaN 177 * <li>{@code x} is not a mathematical integer and {@code mode} is {@link 178 * RoundingMode#UNNECESSARY} 179 * </ul> 180 */ 181 // #roundIntermediate, java.lang.Math.getExponent, com.google.common.math.DoubleUtils 182 @GwtIncompatible 183 public static BigInteger roundToBigInteger(double x, RoundingMode mode) { 184 x = roundIntermediate(x, mode); 185 if (MIN_LONG_AS_DOUBLE - x < 1.0 & x < MAX_LONG_AS_DOUBLE_PLUS_ONE) { 186 return BigInteger.valueOf((long) x); 187 } 188 int exponent = getExponent(x); 189 long significand = getSignificand(x); 190 BigInteger result = BigInteger.valueOf(significand).shiftLeft(exponent - SIGNIFICAND_BITS); 191 return (x < 0) ? result.negate() : result; 192 } 193 194 /** 195 * Returns {@code true} if {@code x} is exactly equal to {@code 2^k} for some finite integer 196 * {@code k}. 197 */ 198 @GwtIncompatible // com.google.common.math.DoubleUtils 199 public static boolean isPowerOfTwo(double x) { 200 if (x > 0.0 && isFinite(x)) { 201 long significand = getSignificand(x); 202 return (significand & (significand - 1)) == 0; 203 } 204 return false; 205 } 206 207 /** 208 * Returns the base 2 logarithm of a double value. 209 * 210 * <p>Special cases: 211 * 212 * <ul> 213 * <li>If {@code x} is NaN or less than zero, the result is NaN. 214 * <li>If {@code x} is positive infinity, the result is positive infinity. 215 * <li>If {@code x} is positive or negative zero, the result is negative infinity. 216 * </ul> 217 * 218 * <p>The computed result is within 1 ulp of the exact result. 219 * 220 * <p>If the result of this method will be immediately rounded to an {@code int}, {@link 221 * #log2(double, RoundingMode)} is faster. 222 */ 223 public static double log2(double x) { 224 return log(x) / LN_2; // surprisingly within 1 ulp according to tests 225 } 226 227 /** 228 * Returns the base 2 logarithm of a double value, rounded with the specified rounding mode to an 229 * {@code int}. 230 * 231 * <p>Regardless of the rounding mode, this is faster than {@code (int) log2(x)}. 232 * 233 * @throws IllegalArgumentException if {@code x <= 0.0}, {@code x} is NaN, or {@code x} is 234 * infinite 235 */ 236 @GwtIncompatible // java.lang.Math.getExponent, com.google.common.math.DoubleUtils 237 @SuppressWarnings("fallthrough") 238 public static int log2(double x, RoundingMode mode) { 239 checkArgument(x > 0.0 && isFinite(x), "x must be positive and finite"); 240 int exponent = getExponent(x); 241 if (!isNormal(x)) { 242 return log2(x * IMPLICIT_BIT, mode) - SIGNIFICAND_BITS; 243 // Do the calculation on a normal value. 244 } 245 // x is positive, finite, and normal 246 boolean increment; 247 switch (mode) { 248 case UNNECESSARY: 249 checkRoundingUnnecessary(isPowerOfTwo(x)); 250 // fall through 251 case FLOOR: 252 increment = false; 253 break; 254 case CEILING: 255 increment = !isPowerOfTwo(x); 256 break; 257 case DOWN: 258 increment = exponent < 0 & !isPowerOfTwo(x); 259 break; 260 case UP: 261 increment = exponent >= 0 & !isPowerOfTwo(x); 262 break; 263 case HALF_DOWN: 264 case HALF_EVEN: 265 case HALF_UP: 266 double xScaled = scaleNormalize(x); 267 // sqrt(2) is irrational, and the spec is relative to the "exact numerical result," 268 // so log2(x) is never exactly exponent + 0.5. 269 increment = (xScaled * xScaled) > 2.0; 270 break; 271 default: 272 throw new AssertionError(); 273 } 274 return increment ? exponent + 1 : exponent; 275 } 276 277 private static final double LN_2 = log(2); 278 279 /** 280 * Returns {@code true} if {@code x} represents a mathematical integer. 281 * 282 * <p>This is equivalent to, but not necessarily implemented as, the expression {@code 283 * !Double.isNaN(x) && !Double.isInfinite(x) && x == Math.rint(x)}. 284 */ 285 @GwtIncompatible // java.lang.Math.getExponent, com.google.common.math.DoubleUtils 286 public static boolean isMathematicalInteger(double x) { 287 return isFinite(x) 288 && (x == 0.0 289 || SIGNIFICAND_BITS - Long.numberOfTrailingZeros(getSignificand(x)) <= getExponent(x)); 290 } 291 292 /** 293 * Returns {@code n!}, that is, the product of the first {@code n} positive integers, {@code 1} if 294 * {@code n == 0}, or {@code n!}, or {@link Double#POSITIVE_INFINITY} if {@code n! > 295 * Double.MAX_VALUE}. 296 * 297 * <p>The result is within 1 ulp of the true value. 298 * 299 * @throws IllegalArgumentException if {@code n < 0} 300 */ 301 public static double factorial(int n) { 302 checkNonNegative("n", n); 303 if (n > MAX_FACTORIAL) { 304 return Double.POSITIVE_INFINITY; 305 } else { 306 // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate 307 // result than multiplying by everySixteenthFactorial[n >> 4] directly. 308 double accum = 1.0; 309 for (int i = 1 + (n & ~0xf); i <= n; i++) { 310 accum *= i; 311 } 312 return accum * everySixteenthFactorial[n >> 4]; 313 } 314 } 315 316 @VisibleForTesting static final int MAX_FACTORIAL = 170; 317 318 @VisibleForTesting 319 static final double[] everySixteenthFactorial = { 320 0x1.0p0, 321 0x1.30777758p44, 322 0x1.956ad0aae33a4p117, 323 0x1.ee69a78d72cb6p202, 324 0x1.fe478ee34844ap295, 325 0x1.c619094edabffp394, 326 0x1.3638dd7bd6347p498, 327 0x1.7cac197cfe503p605, 328 0x1.1e5dfc140e1e5p716, 329 0x1.8ce85fadb707ep829, 330 0x1.95d5f3d928edep945 331 }; 332 333 /** 334 * Returns {@code true} if {@code a} and {@code b} are within {@code tolerance} of each other. 335 * 336 * <p>Technically speaking, this is equivalent to {@code Math.abs(a - b) <= tolerance || 337 * Double.valueOf(a).equals(Double.valueOf(b))}. 338 * 339 * <p>Notable special cases include: 340 * 341 * <ul> 342 * <li>All NaNs are fuzzily equal. 343 * <li>If {@code a == b}, then {@code a} and {@code b} are always fuzzily equal. 344 * <li>Positive and negative zero are always fuzzily equal. 345 * <li>If {@code tolerance} is zero, and neither {@code a} nor {@code b} is NaN, then {@code a} 346 * and {@code b} are fuzzily equal if and only if {@code a == b}. 347 * <li>With {@link Double#POSITIVE_INFINITY} tolerance, all non-NaN values are fuzzily equal. 348 * <li>With finite tolerance, {@code Double.POSITIVE_INFINITY} and {@code 349 * Double.NEGATIVE_INFINITY} are fuzzily equal only to themselves. 350 * </ul> 351 * 352 * <p>This is reflexive and symmetric, but <em>not</em> transitive, so it is <em>not</em> an 353 * equivalence relation and <em>not</em> suitable for use in {@link Object#equals} 354 * implementations. 355 * 356 * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN 357 * @since 13.0 358 */ 359 public static boolean fuzzyEquals(double a, double b, double tolerance) { 360 MathPreconditions.checkNonNegative("tolerance", tolerance); 361 return Math.copySign(a - b, 1.0) <= tolerance 362 // copySign(x, 1.0) is a branch-free version of abs(x), but with different NaN semantics 363 || (a == b) // needed to ensure that infinities equal themselves 364 || (Double.isNaN(a) && Double.isNaN(b)); 365 } 366 367 /** 368 * Compares {@code a} and {@code b} "fuzzily," with a tolerance for nearly-equal values. 369 * 370 * <p>This method is equivalent to {@code fuzzyEquals(a, b, tolerance) ? 0 : Double.compare(a, 371 * b)}. In particular, like {@link Double#compare(double, double)}, it treats all NaN values as 372 * equal and greater than all other values (including {@link Double#POSITIVE_INFINITY}). 373 * 374 * <p>This is <em>not</em> a total ordering and is <em>not</em> suitable for use in {@link 375 * Comparable#compareTo} implementations. In particular, it is not transitive. 376 * 377 * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN 378 * @since 13.0 379 */ 380 public static int fuzzyCompare(double a, double b, double tolerance) { 381 if (fuzzyEquals(a, b, tolerance)) { 382 return 0; 383 } else if (a < b) { 384 return -1; 385 } else if (a > b) { 386 return 1; 387 } else { 388 return Booleans.compare(Double.isNaN(a), Double.isNaN(b)); 389 } 390 } 391 392 /** 393 * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of 394 * {@code values}. 395 * 396 * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of 397 * the arithmetic mean of the population. 398 * 399 * @param values a nonempty series of values 400 * @throws IllegalArgumentException if {@code values} is empty or contains any non-finite value 401 * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite 402 * values. 403 */ 404 @Deprecated 405 // com.google.common.math.DoubleUtils 406 @GwtIncompatible 407 public static double mean(double... values) { 408 checkArgument(values.length > 0, "Cannot take mean of 0 values"); 409 long count = 1; 410 double mean = checkFinite(values[0]); 411 for (int index = 1; index < values.length; ++index) { 412 checkFinite(values[index]); 413 count++; 414 // Art of Computer Programming vol. 2, Knuth, 4.2.2, (15) 415 mean += (values[index] - mean) / count; 416 } 417 return mean; 418 } 419 420 /** 421 * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of 422 * {@code values}. 423 * 424 * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of 425 * the arithmetic mean of the population. 426 * 427 * @param values a nonempty series of values 428 * @throws IllegalArgumentException if {@code values} is empty 429 * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite 430 * values. 431 */ 432 @Deprecated 433 public static double mean(int... values) { 434 checkArgument(values.length > 0, "Cannot take mean of 0 values"); 435 // The upper bound on the the length of an array and the bounds on the int values mean that, in 436 // this case only, we can compute the sum as a long without risking overflow or loss of 437 // precision. So we do that, as it's slightly quicker than the Knuth algorithm. 438 long sum = 0; 439 for (int index = 0; index < values.length; ++index) { 440 sum += values[index]; 441 } 442 return (double) sum / values.length; 443 } 444 445 /** 446 * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of 447 * {@code values}. 448 * 449 * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of 450 * the arithmetic mean of the population. 451 * 452 * @param values a nonempty series of values, which will be converted to {@code double} values 453 * (this may cause loss of precision for longs of magnitude over 2^53 (slightly over 9e15)) 454 * @throws IllegalArgumentException if {@code values} is empty 455 * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite 456 * values. 457 */ 458 @Deprecated 459 public static double mean(long... values) { 460 checkArgument(values.length > 0, "Cannot take mean of 0 values"); 461 long count = 1; 462 double mean = values[0]; 463 for (int index = 1; index < values.length; ++index) { 464 count++; 465 // Art of Computer Programming vol. 2, Knuth, 4.2.2, (15) 466 mean += (values[index] - mean) / count; 467 } 468 return mean; 469 } 470 471 /** 472 * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of 473 * {@code values}. 474 * 475 * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of 476 * the arithmetic mean of the population. 477 * 478 * @param values a nonempty series of values, which will be converted to {@code double} values 479 * (this may cause loss of precision) 480 * @throws IllegalArgumentException if {@code values} is empty or contains any non-finite value 481 * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite 482 * values. 483 */ 484 @Deprecated 485 // com.google.common.math.DoubleUtils 486 @GwtIncompatible 487 public static double mean(Iterable<? extends Number> values) { 488 return mean(values.iterator()); 489 } 490 491 /** 492 * Returns the <a href="http://en.wikipedia.org/wiki/Arithmetic_mean">arithmetic mean</a> of 493 * {@code values}. 494 * 495 * <p>If these values are a sample drawn from a population, this is also an unbiased estimator of 496 * the arithmetic mean of the population. 497 * 498 * @param values a nonempty series of values, which will be converted to {@code double} values 499 * (this may cause loss of precision) 500 * @throws IllegalArgumentException if {@code values} is empty or contains any non-finite value 501 * @deprecated Use {@link Stats#meanOf} instead, noting the less strict handling of non-finite 502 * values. 503 */ 504 @Deprecated 505 // com.google.common.math.DoubleUtils 506 @GwtIncompatible 507 public static double mean(Iterator<? extends Number> values) { 508 checkArgument(values.hasNext(), "Cannot take mean of 0 values"); 509 long count = 1; 510 double mean = checkFinite(values.next().doubleValue()); 511 while (values.hasNext()) { 512 double value = checkFinite(values.next().doubleValue()); 513 count++; 514 // Art of Computer Programming vol. 2, Knuth, 4.2.2, (15) 515 mean += (value - mean) / count; 516 } 517 return mean; 518 } 519 520 @GwtIncompatible // com.google.common.math.DoubleUtils 521 @CanIgnoreReturnValue 522 private static double checkFinite(double argument) { 523 checkArgument(isFinite(argument)); 524 return argument; 525 } 526 527 private DoubleMath() {} 528}