Home | History | Annotate | Download | only in math 
      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 
     17 package com.google.common.math;
     18 
     19 import static com.google.common.math.MathPreconditions.checkNonNegative;
     20 import static java.lang.Math.log;
     21 
     22 import com.google.common.annotations.GwtCompatible;
     23 import com.google.common.annotations.VisibleForTesting;
     24 import com.google.common.primitives.Booleans;
     25 
     26 /**
     27  * A class for arithmetic on doubles that is not covered by {@link java.lang.Math}.
     28  *
     29  * @author Louis Wasserman
     30  * @since 11.0
     31  */
     32 @GwtCompatible(emulated = true)
     33 public final class DoubleMath {
     34   /*
     35    * This method returns a value y such that rounding y DOWN (towards zero) gives the same result
     36    * as rounding x according to the specified mode.
     37    */
     38 
     39   private static final double MIN_INT_AS_DOUBLE = -0x1p31;
     40   private static final double MAX_INT_AS_DOUBLE = 0x1p31 - 1.0;
     41 
     42   private static final double MIN_LONG_AS_DOUBLE = -0x1p63;
     43   /*
     44    * We cannot store Long.MAX_VALUE as a double without losing precision.  Instead, we store
     45    * Long.MAX_VALUE + 1 == -Long.MIN_VALUE, and then offset all comparisons by 1.
     46    */
     47   private static final double MAX_LONG_AS_DOUBLE_PLUS_ONE = 0x1p63;
     48 
     49   /**
     50    * Returns the base 2 logarithm of a double value.
     51    *
     52    * <p>Special cases:
     53    * <ul>
     54    * <li>If {@code x} is NaN or less than zero, the result is NaN.
     55    * <li>If {@code x} is positive infinity, the result is positive infinity.
     56    * <li>If {@code x} is positive or negative zero, the result is negative infinity.
     57    * </ul>
     58    *
     59    * <p>The computed result is within 1 ulp of the exact result.
     60    *
     61    * <p>If the result of this method will be immediately rounded to an {@code int},
     62    * {@link #log2(double, RoundingMode)} is faster.
     63    */
     64   public static double log2(double x) {
     65     return log(x) / LN_2; // surprisingly within 1 ulp according to tests
     66   }
     67 
     68   private static final double LN_2 = log(2);
     69 
     70   /**
     71    * Returns {@code n!}, that is, the product of the first {@code n} positive
     72    * integers, {@code 1} if {@code n == 0}, or {@code n!}, or
     73    * {@link Double#POSITIVE_INFINITY} if {@code n! > Double.MAX_VALUE}.
     74    *
     75    * <p>The result is within 1 ulp of the true value.
     76    *
     77    * @throws IllegalArgumentException if {@code n < 0}
     78    */
     79   public static double factorial(int n) {
     80     checkNonNegative("n", n);
     81     if (n > MAX_FACTORIAL) {
     82       return Double.POSITIVE_INFINITY;
     83     } else {
     84       // Multiplying the last (n & 0xf) values into their own accumulator gives a more accurate
     85       // result than multiplying by everySixteenthFactorial[n >> 4] directly.
     86       double accum = 1.0;
     87       for (int i = 1 + (n & ~0xf); i <= n; i++) {
     88         accum *= i;
     89       }
     90       return accum * everySixteenthFactorial[n >> 4];
     91     }
     92   }
     93 
     94   @VisibleForTesting
     95   static final int MAX_FACTORIAL = 170;
     96 
     97   @VisibleForTesting
     98   static final double[] everySixteenthFactorial = {
     99       0x1.0p0,
    100       0x1.30777758p44,
    101       0x1.956ad0aae33a4p117,
    102       0x1.ee69a78d72cb6p202,
    103       0x1.fe478ee34844ap295,
    104       0x1.c619094edabffp394,
    105       0x1.3638dd7bd6347p498,
    106       0x1.7cac197cfe503p605,
    107       0x1.1e5dfc140e1e5p716,
    108       0x1.8ce85fadb707ep829,
    109       0x1.95d5f3d928edep945};
    110 
    111   /**
    112    * Returns {@code true} if {@code a} and {@code b} are within {@code tolerance} of each other.
    113    *
    114    * <p>Technically speaking, this is equivalent to
    115    * {@code Math.abs(a - b) <= tolerance || Double.valueOf(a).equals(Double.valueOf(b))}.
    116    *
    117    * <p>Notable special cases include:
    118    * <ul>
    119    * <li>All NaNs are fuzzily equal.
    120    * <li>If {@code a == b}, then {@code a} and {@code b} are always fuzzily equal.
    121    * <li>Positive and negative zero are always fuzzily equal.
    122    * <li>If {@code tolerance} is zero, and neither {@code a} nor {@code b} is NaN, then
    123    * {@code a} and {@code b} are fuzzily equal if and only if {@code a == b}.
    124    * <li>With {@link Double#POSITIVE_INFINITY} tolerance, all non-NaN values are fuzzily equal.
    125    * <li>With finite tolerance, {@code Double.POSITIVE_INFINITY} and {@code
    126    * Double.NEGATIVE_INFINITY} are fuzzily equal only to themselves.
    127    * </li>
    128    *
    129    * <p>This is reflexive and symmetric, but <em>not</em> transitive, so it is <em>not</em> an
    130    * equivalence relation and <em>not</em> suitable for use in {@link Object#equals}
    131    * implementations.
    132    *
    133    * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
    134    * @since 13.0
    135    */
    136   public static boolean fuzzyEquals(double a, double b, double tolerance) {
    137     MathPreconditions.checkNonNegative("tolerance", tolerance);
    138     return
    139           Math.copySign(a - b, 1.0) <= tolerance
    140            // copySign(x, 1.0) is a branch-free version of abs(x), but with different NaN semantics
    141           || (a == b) // needed to ensure that infinities equal themselves
    142           || (Double.isNaN(a) && Double.isNaN(b));
    143   }
    144 
    145   /**
    146    * Compares {@code a} and {@code b} "fuzzily," with a tolerance for nearly-equal values.
    147    *
    148    * <p>This method is equivalent to
    149    * {@code fuzzyEquals(a, b, tolerance) ? 0 : Double.compare(a, b)}. In particular, like
    150    * {@link Double#compare(double, double)}, it treats all NaN values as equal and greater than all
    151    * other values (including {@link Double#POSITIVE_INFINITY}).
    152    *
    153    * <p>This is <em>not</em> a total ordering and is <em>not</em> suitable for use in
    154    * {@link Comparable#compareTo} implementations.  In particular, it is not transitive.
    155    *
    156    * @throws IllegalArgumentException if {@code tolerance} is {@code < 0} or NaN
    157    * @since 13.0
    158    */
    159   public static int fuzzyCompare(double a, double b, double tolerance) {
    160     if (fuzzyEquals(a, b, tolerance)) {
    161       return 0;
    162     } else if (a < b) {
    163       return -1;
    164     } else if (a > b) {
    165       return 1;
    166     } else {
    167       return Booleans.compare(Double.isNaN(a), Double.isNaN(b));
    168     }
    169   }
    170 
    171   private DoubleMath() {}
    172 }
    173 
    174