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