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 java.math.BigInteger.ONE;
     20 import static java.math.BigInteger.ZERO;
     21 import static java.math.RoundingMode.CEILING;
     22 import static java.math.RoundingMode.DOWN;
     23 import static java.math.RoundingMode.FLOOR;
     24 import static java.math.RoundingMode.HALF_DOWN;
     25 import static java.math.RoundingMode.HALF_EVEN;
     26 import static java.math.RoundingMode.HALF_UP;
     27 import static java.math.RoundingMode.UP;
     28 import static java.util.Arrays.asList;
     29 
     30 import com.google.common.annotations.GwtCompatible;
     31 import com.google.common.base.Function;
     32 import com.google.common.base.Predicate;
     33 import com.google.common.collect.ImmutableList;
     34 import com.google.common.collect.ImmutableSet;
     35 import com.google.common.collect.Iterables;
     36 import com.google.common.primitives.Doubles;
     37 
     38 import java.math.BigInteger;
     39 import java.math.RoundingMode;
     40 
     41 /**
     42  * Exhaustive input sets for every integral type.
     43  *
     44  * @author lowasser (at) google.com (Louis Wasserman)
     45  */
     46 @GwtCompatible
     47 public class MathTesting {
     48   static final ImmutableSet<RoundingMode> ALL_ROUNDING_MODES = ImmutableSet.copyOf(RoundingMode
     49       .values());
     50 
     51   static final ImmutableList<RoundingMode> ALL_SAFE_ROUNDING_MODES = ImmutableList.of(DOWN, UP,
     52       FLOOR, CEILING, HALF_EVEN, HALF_UP, HALF_DOWN);
     53 
     54   // Exponents to test for the pow() function.
     55   static final ImmutableList<Integer> EXPONENTS = ImmutableList.of(0, 1, 2, 3, 4, 5, 6, 7, 10, 15,
     56       20, 25, 30, 40, 70);
     57 
     58   /* Helper function to make a Long value from an Integer. */
     59   private static final Function<Integer, Long> TO_LONG = new Function<Integer, Long>() {
     60     @Override
     61     public Long apply(Integer n) {
     62       return Long.valueOf(n);
     63     }
     64   };
     65 
     66   /* Helper function to make a BigInteger value from a Long. */
     67   private static final Function<Long, BigInteger> TO_BIGINTEGER =
     68       new Function<Long, BigInteger>() {
     69         @Override
     70         public BigInteger apply(Long n) {
     71           return BigInteger.valueOf(n);
     72         }
     73       };
     74 
     75   private static final Function<Integer, Integer> NEGATE_INT = new Function<Integer, Integer>() {
     76     @Override
     77     public Integer apply(Integer x) {
     78       return -x;
     79     }
     80   };
     81 
     82   private static final Function<Long, Long> NEGATE_LONG = new Function<Long, Long>() {
     83     @Override
     84     public Long apply(Long x) {
     85       return -x;
     86     }
     87   };
     88 
     89   private static final Function<BigInteger, BigInteger> NEGATE_BIGINT =
     90       new Function<BigInteger, BigInteger>() {
     91         @Override
     92         public BigInteger apply(BigInteger x) {
     93           return x.negate();
     94         }
     95       };
     96 
     97   /*
     98    * This list contains values that attempt to provoke overflow in integer operations. It contains
     99    * positive values on or near 2^N for N near multiples of 8 (near byte boundaries).
    100    */
    101   static final ImmutableSet<Integer> POSITIVE_INTEGER_CANDIDATES;
    102 
    103   static final Iterable<Integer> NEGATIVE_INTEGER_CANDIDATES;
    104 
    105   static final Iterable<Integer> NONZERO_INTEGER_CANDIDATES;
    106 
    107   static final Iterable<Integer> ALL_INTEGER_CANDIDATES;
    108 
    109   static {
    110     ImmutableSet.Builder<Integer> intValues = ImmutableSet.builder();
    111     // Add boundary values manually to avoid over/under flow (this covers 2^N for 0 and 31).
    112     intValues.add(Integer.MAX_VALUE - 1, Integer.MAX_VALUE);
    113     // Add values up to 64. This covers cases like "square of a prime" and such.
    114     for (int i = 1; i <= 64; i++) {
    115       intValues.add(i);
    116     }
    117     // Now add values near 2^N for lots of values of N.
    118     for (int exponent : asList(2, 3, 4, 5, 6, 7, 8, 9, 15, 16, 17, 23, 24, 25)) {
    119       int x = 1 << exponent;
    120       intValues.add(x, x + 1, x - 1);
    121     }
    122     intValues.add(9999).add(10000).add(10001).add(1000000); // near powers of 10
    123     intValues.add(5792).add(5793); // sqrt(2^25) rounded up and down
    124     POSITIVE_INTEGER_CANDIDATES = intValues.build();
    125     NEGATIVE_INTEGER_CANDIDATES =
    126         Iterables.concat(Iterables.transform(POSITIVE_INTEGER_CANDIDATES, NEGATE_INT),
    127             ImmutableList.of(Integer.MIN_VALUE));
    128     NONZERO_INTEGER_CANDIDATES =
    129         Iterables.concat(POSITIVE_INTEGER_CANDIDATES, NEGATIVE_INTEGER_CANDIDATES);
    130     ALL_INTEGER_CANDIDATES = Iterables.concat(NONZERO_INTEGER_CANDIDATES, ImmutableList.of(0));
    131   }
    132 
    133   /*
    134    * This list contains values that attempt to provoke overflow in long operations. It contains
    135    * positive values on or near 2^N for N near multiples of 8 (near byte boundaries). This list is
    136    * a superset of POSITIVE_INTEGER_CANDIDATES.
    137    */
    138   static final ImmutableSet<Long> POSITIVE_LONG_CANDIDATES;
    139 
    140   static final Iterable<Long> NEGATIVE_LONG_CANDIDATES;
    141 
    142   static final Iterable<Long> NONZERO_LONG_CANDIDATES;
    143 
    144   static final Iterable<Long> ALL_LONG_CANDIDATES;
    145 
    146   static {
    147     ImmutableSet.Builder<Long> longValues = ImmutableSet.builder();
    148     // First of all add all the integer candidate values.
    149     longValues.addAll(Iterables.transform(POSITIVE_INTEGER_CANDIDATES, TO_LONG));
    150     // Add boundary values manually to avoid over/under flow (this covers 2^N for 31 and 63).
    151     longValues.add(Integer.MAX_VALUE + 1L, Long.MAX_VALUE - 1L, Long.MAX_VALUE);
    152     // Now add values near 2^N for lots of values of N.
    153     for (int exponent : asList(32, 33, 39, 40, 41, 47, 48, 49, 55, 56, 57)) {
    154       long x = 1L << exponent;
    155       longValues.add(x, x + 1, x - 1);
    156     }
    157     longValues.add(194368031998L).add(194368031999L); // sqrt(2^75) rounded up and down
    158     POSITIVE_LONG_CANDIDATES = longValues.build();
    159     NEGATIVE_LONG_CANDIDATES =
    160         Iterables.concat(Iterables.transform(POSITIVE_LONG_CANDIDATES, NEGATE_LONG),
    161             ImmutableList.of(Long.MIN_VALUE));
    162     NONZERO_LONG_CANDIDATES = Iterables.concat(POSITIVE_LONG_CANDIDATES, NEGATIVE_LONG_CANDIDATES);
    163     ALL_LONG_CANDIDATES = Iterables.concat(NONZERO_LONG_CANDIDATES, ImmutableList.of(0L));
    164   }
    165 
    166   /*
    167    * This list contains values that attempt to provoke overflow in big integer operations. It
    168    * contains positive values on or near 2^N for N near multiples of 8 (near byte boundaries). This
    169    * list is a superset of POSITIVE_LONG_CANDIDATES.
    170    */
    171   static final ImmutableSet<BigInteger> POSITIVE_BIGINTEGER_CANDIDATES;
    172 
    173   static final Iterable<BigInteger> NEGATIVE_BIGINTEGER_CANDIDATES;
    174 
    175   static final Iterable<BigInteger> NONZERO_BIGINTEGER_CANDIDATES;
    176 
    177   static final Iterable<BigInteger> ALL_BIGINTEGER_CANDIDATES;
    178 
    179   static {
    180     ImmutableSet.Builder<BigInteger> bigValues = ImmutableSet.builder();
    181     // First of all add all the long candidate values.
    182     bigValues.addAll(Iterables.transform(POSITIVE_LONG_CANDIDATES, TO_BIGINTEGER));
    183     // Add boundary values manually to avoid over/under flow.
    184     bigValues.add(BigInteger.valueOf(Long.MAX_VALUE).add(ONE));
    185     // Now add values near 2^N for lots of values of N.
    186     for (int exponent : asList(64, 65, 71, 72, 73, 79, 80, 81, 255, 256, 257, 511, 512, 513,
    187         Double.MAX_EXPONENT - 1, Double.MAX_EXPONENT, Double.MAX_EXPONENT + 1)) {
    188       BigInteger x = ONE.shiftLeft(exponent);
    189       bigValues.add(x, x.add(ONE), x.subtract(ONE));
    190     }
    191     bigValues.add(new BigInteger("218838949120258359057546633")); // sqrt(2^175) rounded up and
    192                                                                   // down
    193     bigValues.add(new BigInteger("218838949120258359057546634"));
    194     POSITIVE_BIGINTEGER_CANDIDATES = bigValues.build();
    195     NEGATIVE_BIGINTEGER_CANDIDATES =
    196         Iterables.transform(POSITIVE_BIGINTEGER_CANDIDATES, NEGATE_BIGINT);
    197     NONZERO_BIGINTEGER_CANDIDATES =
    198         Iterables.concat(POSITIVE_BIGINTEGER_CANDIDATES, NEGATIVE_BIGINTEGER_CANDIDATES);
    199     ALL_BIGINTEGER_CANDIDATES =
    200         Iterables.concat(NONZERO_BIGINTEGER_CANDIDATES, ImmutableList.of(ZERO));
    201   }
    202 
    203   static final ImmutableSet<Double> INTEGRAL_DOUBLE_CANDIDATES;
    204   static final ImmutableSet<Double> FRACTIONAL_DOUBLE_CANDIDATES;
    205   static final Iterable<Double> FINITE_DOUBLE_CANDIDATES;
    206   static final Iterable<Double> POSITIVE_FINITE_DOUBLE_CANDIDATES;
    207   static final Iterable<Double> ALL_DOUBLE_CANDIDATES;
    208   static {
    209     ImmutableSet.Builder<Double> integralBuilder = ImmutableSet.builder();
    210     ImmutableSet.Builder<Double> fractionalBuilder = ImmutableSet.builder();
    211     integralBuilder.addAll(Doubles.asList(0.0, -0.0, Double.MAX_VALUE, -Double.MAX_VALUE));
    212     // Add small multiples of MIN_VALUE and MIN_NORMAL
    213     for (int scale = 1; scale <= 4; scale++) {
    214       for (double d : Doubles.asList(Double.MIN_VALUE, Double.MIN_NORMAL)) {
    215         fractionalBuilder.add(d * scale).add(-d * scale);
    216       }
    217     }
    218     for (double d : Doubles.asList(0, 1, 2, 7, 51, 102, Math.scalb(1.0, 53), Integer.MIN_VALUE,
    219         Integer.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE)) {
    220       for (double delta : Doubles.asList(0.0, 1.0, 2.0)) {
    221         integralBuilder.addAll(Doubles.asList(d + delta, d - delta, -d - delta, -d + delta));
    222       }
    223       for (double delta : Doubles.asList(0.01, 0.1, 0.25, 0.499, 0.5, 0.501, 0.7, 0.8)) {
    224         double x = d + delta;
    225         if (x != Math.round(x)) {
    226           fractionalBuilder.add(x);
    227         }
    228       }
    229     }
    230     INTEGRAL_DOUBLE_CANDIDATES = integralBuilder.build();
    231     fractionalBuilder.add(1.414).add(1.415).add(Math.sqrt(2));
    232     fractionalBuilder.add(5.656).add(5.657).add(4 * Math.sqrt(2));
    233     for (double d : INTEGRAL_DOUBLE_CANDIDATES) {
    234       double x = 1 / d;
    235       if (x != Math.rint(x)) {
    236         fractionalBuilder.add(x);
    237       }
    238     }
    239     FRACTIONAL_DOUBLE_CANDIDATES = fractionalBuilder.build();
    240     FINITE_DOUBLE_CANDIDATES =
    241         Iterables.concat(FRACTIONAL_DOUBLE_CANDIDATES, INTEGRAL_DOUBLE_CANDIDATES);
    242     POSITIVE_FINITE_DOUBLE_CANDIDATES =
    243         Iterables.filter(FINITE_DOUBLE_CANDIDATES, new Predicate<Double>() {
    244           @Override
    245           public boolean apply(Double input) {
    246             return input.doubleValue() > 0.0;
    247           }
    248         });
    249     ALL_DOUBLE_CANDIDATES =
    250         Iterables.concat(FINITE_DOUBLE_CANDIDATES,
    251             asList(Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY, Double.NaN));
    252   }
    253 }
    254