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 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, 7, 10, 15,
56       20, 25, 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 40. This covers cases like "square of a prime" and such.
114     for (int i = 1; i <= 40; 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, 9, 15, 16, 17, 24, 25, 30)) {
119       int x = 1 << exponent;
intValues.add(x, x + 1, x - 1)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 = ImmutableList.copyOf(Iterables.concat(
126         Iterables.transform(POSITIVE_INTEGER_CANDIDATES, NEGATE_INT),
127         ImmutableList.of(Integer.MIN_VALUE)));
128     NONZERO_INTEGER_CANDIDATES = ImmutableList.copyOf(
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.
Iterables.transform(POSITIVE_INTEGER_CANDIDATES, TO_LONG)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;
longValues.add(x, x + 1, x - 1)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 final int MAX_EXPONENT = 1023; // Double.MAX_EXPONENT not present in JDK5
180 
181   static final double MIN_NORMAL = 2.2250738585072014E-308;
182 
183   static {
184     ImmutableSet.Builder<BigInteger> bigValues = ImmutableSet.builder();
185     // First of all add all the long candidate values.
Iterables.transform(POSITIVE_LONG_CANDIDATES, TO_BIGINTEGER)186     bigValues.addAll(Iterables.transform(POSITIVE_LONG_CANDIDATES, TO_BIGINTEGER));
187     // Add boundary values manually to avoid over/under flow.
188     bigValues.add(BigInteger.valueOf(Long.MAX_VALUE).add(ONE));
189     // Now add values near 2^N for lots of values of N.
190     for (int exponent : asList(64, 65, 71, 72, 73, 79, 80, 81, 255, 256, 257, 511, 512, 513,
191         MAX_EXPONENT - 1, MAX_EXPONENT, MAX_EXPONENT + 1)) {
192       BigInteger x = ONE.shiftLeft(exponent);
bigValues.add(x, x.add(ONE), x.subtract(ONE))193       bigValues.add(x, x.add(ONE), x.subtract(ONE));
194     }
bigValues.add(new BigInteger("218838949120258359057546633"))195     bigValues.add(new BigInteger("218838949120258359057546633")); // sqrt(2^175) rounded up and
196                                                                   // down
bigValues.add(new BigInteger("218838949120258359057546634"))197     bigValues.add(new BigInteger("218838949120258359057546634"));
198     POSITIVE_BIGINTEGER_CANDIDATES = bigValues.build();
199     NEGATIVE_BIGINTEGER_CANDIDATES =
200         Iterables.transform(POSITIVE_BIGINTEGER_CANDIDATES, NEGATE_BIGINT);
201     NONZERO_BIGINTEGER_CANDIDATES =
202         Iterables.concat(POSITIVE_BIGINTEGER_CANDIDATES, NEGATIVE_BIGINTEGER_CANDIDATES);
203     ALL_BIGINTEGER_CANDIDATES =
204         Iterables.concat(NONZERO_BIGINTEGER_CANDIDATES, ImmutableList.of(ZERO));
205   }
206 
207   static final ImmutableSet<Double> INTEGRAL_DOUBLE_CANDIDATES;
208   static final ImmutableSet<Double> FRACTIONAL_DOUBLE_CANDIDATES;
209   static final Iterable<Double> INFINITIES = Doubles.asList(
210       Double.POSITIVE_INFINITY,
211       Double.NEGATIVE_INFINITY);
212   static final Iterable<Double> FINITE_DOUBLE_CANDIDATES;
213   static final Iterable<Double> POSITIVE_FINITE_DOUBLE_CANDIDATES;
214   static final Iterable<Double> ALL_DOUBLE_CANDIDATES;
215   static final Iterable<Double> DOUBLE_CANDIDATES_EXCEPT_NAN;
216   static {
217     ImmutableSet.Builder<Double> integralBuilder = ImmutableSet.builder();
218     ImmutableSet.Builder<Double> fractionalBuilder = ImmutableSet.builder();
219     integralBuilder.addAll(Doubles.asList(0.0, -0.0, Double.MAX_VALUE, -Double.MAX_VALUE));
220     // Add small multiples of MIN_VALUE and MIN_NORMAL
221     for (int scale = 1; scale <= 4; scale++) {
222       for (double d : Doubles.asList(Double.MIN_VALUE, MIN_NORMAL)) {
223         fractionalBuilder.add(d * scale).add(-d * scale);
224       }
225     }
226     for (double d : Doubles.asList(0, 1, 2, 7, 51, 102, Integer.MIN_VALUE,
227         Integer.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE)) {
228       for (double delta : Doubles.asList(0.0, 1.0, 2.0)) {
229         integralBuilder.addAll(Doubles.asList(d + delta, d - delta, -d - delta, -d + delta));
230       }
231       for (double delta : Doubles.asList(0.01, 0.1, 0.25, 0.499, 0.5, 0.501, 0.7, 0.8)) {
232         double x = d + delta;
233         if (x != Math.round(x)) {
234           fractionalBuilder.add(x);
235         }
236       }
237     }
238     INTEGRAL_DOUBLE_CANDIDATES = integralBuilder.build();
239     fractionalBuilder.add(1.414).add(1.415).add(Math.sqrt(2));
240     fractionalBuilder.add(5.656).add(5.657).add(4 * Math.sqrt(2));
241     for (double d : INTEGRAL_DOUBLE_CANDIDATES) {
242       double x = 1 / d;
243       if (x != Math.rint(x)) {
244         fractionalBuilder.add(x);
245       }
246     }
247     FRACTIONAL_DOUBLE_CANDIDATES = fractionalBuilder.build();
248     FINITE_DOUBLE_CANDIDATES =
249         Iterables.concat(FRACTIONAL_DOUBLE_CANDIDATES, INTEGRAL_DOUBLE_CANDIDATES);
250     POSITIVE_FINITE_DOUBLE_CANDIDATES =
251         Iterables.filter(FINITE_DOUBLE_CANDIDATES, new Predicate<Double>() {
252           @Override
253           public boolean apply(Double input) {
254             return input.doubleValue() > 0.0;
255           }
256         });
257     DOUBLE_CANDIDATES_EXCEPT_NAN = Iterables.concat(FINITE_DOUBLE_CANDIDATES, INFINITIES);
258     ALL_DOUBLE_CANDIDATES =
259         Iterables.concat(DOUBLE_CANDIDATES_EXCEPT_NAN, asList(Double.NaN));
260   }
261 }
262