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.base.Preconditions.checkArgument;
     20 
     21 import java.math.BigInteger;
     22 
     23 import com.google.common.annotations.VisibleForTesting;
     24 
     25 /**
     26  * Utilities for {@code double} primitives. Some of these are exposed in JDK 6,
     27  * but we can't depend on them there.
     28  *
     29  * @author Louis Wasserman
     30  */
     31 final class DoubleUtils {
     32   // TODO(user): replace with appropriate calls when we move to JDK 6
     33 
     34   private DoubleUtils() {
     35   }
     36 
     37   static double next(double x, boolean up) {
     38     // Math.nextAfter is JDK 6.
     39     if (x == 0.0) {
     40       return up ? Double.MIN_VALUE : -Double.MIN_VALUE;
     41     }
     42     long bits = Double.doubleToRawLongBits(x);
     43     if ((x < 0.0) == up) {
     44       bits--;
     45     } else {
     46       bits++;
     47     }
     48     return Double.longBitsToDouble(bits);
     49   }
     50 
     51   // The mask for the significand, according to the {@link
     52   // Double#doubleToRawLongBits(double)} spec.
     53   static final long SIGNIFICAND_MASK = 0x000fffffffffffffL;
     54 
     55   // The mask for the exponent, according to the {@link
     56   // Double#doubleToRawLongBits(double)} spec.
     57   static final long EXPONENT_MASK = 0x7ff0000000000000L;
     58 
     59   // The mask for the sign, according to the {@link
     60   // Double#doubleToRawLongBits(double)} spec.
     61   static final long SIGN_MASK = 0x8000000000000000L;
     62 
     63   static final int SIGNIFICAND_BITS = 52;
     64 
     65   static final int EXPONENT_BIAS = 1023;
     66 
     67   static final int MIN_DOUBLE_EXPONENT = -1022;
     68 
     69   static final int MAX_DOUBLE_EXPONENT = 1023;
     70 
     71   /**
     72    * The implicit 1 bit that is omitted in significands of normal doubles.
     73    */
     74   static final long IMPLICIT_BIT = SIGNIFICAND_MASK + 1;
     75 
     76   @VisibleForTesting
     77   static int getExponent(double d) {
     78     // TODO: replace with Math.getExponent in JDK 6
     79     long bits = Double.doubleToRawLongBits(d);
     80     int exponent = (int) ((bits & EXPONENT_MASK) >> SIGNIFICAND_BITS);
     81     exponent -= EXPONENT_BIAS;
     82     return exponent;
     83   }
     84 
     85   /**
     86    * Returns {@code d * 2^scale}.
     87    */
     88   static strictfp double scalb(double d, int scale) {
     89     // TODO: replace with Math.scalb in JDK 6
     90     int exponent = getExponent(d);
     91     switch (exponent) {
     92       case MAX_DOUBLE_EXPONENT + 1: // NaN, infinity
     93         return d;
     94       case MIN_DOUBLE_EXPONENT - 1:
     95         return d * StrictMath.pow(2.0, scale);
     96       default:
     97         int newExponent = exponent + scale;
     98         if (MIN_DOUBLE_EXPONENT <= newExponent
     99             & newExponent <= MAX_DOUBLE_EXPONENT) {
    100           long bits = Double.doubleToRawLongBits(d);
    101           bits &= ~EXPONENT_MASK;
    102           bits |= ((long) (newExponent + EXPONENT_BIAS)) << SIGNIFICAND_BITS;
    103           return Double.longBitsToDouble(bits);
    104         }
    105         return d * StrictMath.pow(2.0, scale);
    106     }
    107   }
    108 
    109   static long getSignificand(double d) {
    110     checkArgument(isFinite(d), "not a normal value");
    111     int exponent = getExponent(d);
    112     long bits = Double.doubleToRawLongBits(d);
    113     bits &= SIGNIFICAND_MASK;
    114     return (exponent == MIN_DOUBLE_EXPONENT - 1)
    115         ? bits << 1
    116         : bits | IMPLICIT_BIT;
    117   }
    118 
    119   static boolean isFinite(double d) {
    120     return getExponent(d) <= MAX_DOUBLE_EXPONENT;
    121   }
    122 
    123   static boolean isNormal(double d) {
    124     return getExponent(d) >= MIN_DOUBLE_EXPONENT;
    125   }
    126 
    127   /*
    128    * Returns x scaled by a power of 2 such that it is in the range [1, 2). Assumes x is positive,
    129    * normal, and finite.
    130    */
    131   static double scaleNormalize(double x) {
    132     long significand = Double.doubleToRawLongBits(x) & SIGNIFICAND_MASK;
    133     return Double.longBitsToDouble(significand | ONE_BITS);
    134   }
    135 
    136   static double bigToDouble(BigInteger x) {
    137     // This is an extremely fast implementation of BigInteger.doubleValue().  JDK patch pending.
    138     BigInteger absX = x.abs();
    139     int exponent = absX.bitLength() - 1;
    140     // exponent == floor(log2(abs(x)))
    141     if (exponent < Long.SIZE - 1) {
    142       return x.longValue();
    143     } else if (exponent > MAX_DOUBLE_EXPONENT) {
    144       return x.signum() * Double.POSITIVE_INFINITY;
    145     }
    146 
    147     /*
    148      * We need the top SIGNIFICAND_BITS + 1 bits, including the "implicit" one bit. To make
    149      * rounding easier, we pick out the top SIGNIFICAND_BITS + 2 bits, so we have one to help us
    150      * round up or down. twiceSignifFloor will contain the top SIGNIFICAND_BITS + 2 bits, and
    151      * signifFloor the top SIGNIFICAND_BITS + 1.
    152      *
    153      * It helps to consider the real number signif = absX * 2^(SIGNIFICAND_BITS - exponent).
    154      */
    155     int shift = exponent - SIGNIFICAND_BITS - 1;
    156     long twiceSignifFloor = absX.shiftRight(shift).longValue();
    157     long signifFloor = twiceSignifFloor >> 1;
    158     signifFloor &= SIGNIFICAND_MASK; // remove the implied bit
    159 
    160     /*
    161      * We round up if either the fractional part of signif is strictly greater than 0.5 (which is
    162      * true if the 0.5 bit is set and any lower bit is set), or if the fractional part of signif is
    163      * >= 0.5 and signifFloor is odd (which is true if both the 0.5 bit and the 1 bit are set).
    164      */
    165     boolean increment = (twiceSignifFloor & 1) != 0
    166         && ((signifFloor & 1) != 0 || absX.getLowestSetBit() < shift);
    167     long signifRounded = increment ? signifFloor + 1 : signifFloor;
    168     long bits = (long) ((exponent + EXPONENT_BIAS)) << SIGNIFICAND_BITS;
    169     bits += signifRounded;
    170     /*
    171      * If signifRounded == 2^53, we'd need to set all of the significand bits to zero and add 1 to
    172      * the exponent. This is exactly the behavior we get from just adding signifRounded to bits
    173      * directly.  If the exponent is MAX_DOUBLE_EXPONENT, we round up (correctly) to
    174      * Double.POSITIVE_INFINITY.
    175      */
    176     bits |= x.signum() & SIGN_MASK;
    177     return Double.longBitsToDouble(bits);
    178   }
    179 
    180   private static final long ONE_BITS = Double.doubleToRawLongBits(1.0);
    181 }
    182