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.MathBenchmarking.ARRAY_MASK;
20 import static com.google.common.math.MathBenchmarking.ARRAY_SIZE;
21 import static com.google.common.math.MathBenchmarking.RANDOM_SOURCE;
22 import static java.math.RoundingMode.CEILING;
23 
24 import com.google.caliper.BeforeExperiment;
25 import com.google.caliper.Benchmark;
26 import com.google.caliper.Param;
27 import com.google.common.math.BigIntegerMath;
28 import com.google.common.math.IntMath;
29 import com.google.common.math.LongMath;
30 
31 import java.math.BigInteger;
32 
33 /**
34  * Benchmarks for the non-rounding methods of {@code BigIntegerMath}.
35  *
36  * @author Louis Wasserman
37  */
38 public class BigIntegerMathBenchmark {
39   private static final int[] factorials = new int[ARRAY_SIZE];
40   private static final int[] slowFactorials = new int[ARRAY_SIZE];
41   private static final int[] binomials = new int[ARRAY_SIZE];
42 
43   @Param({"50", "1000", "10000"})
44   int factorialBound;
45 
46   @BeforeExperiment
setUp()47   void setUp() {
48     for (int i = 0; i < ARRAY_SIZE; i++) {
49       factorials[i] = RANDOM_SOURCE.nextInt(factorialBound);
50       slowFactorials[i] = RANDOM_SOURCE.nextInt(factorialBound);
51       binomials[i] = RANDOM_SOURCE.nextInt(factorials[i] + 1);
52     }
53   }
54 
55   /**
56    * Previous version of BigIntegerMath.factorial, kept for timing purposes.
57    */
oldSlowFactorial(int n)58   private static BigInteger oldSlowFactorial(int n) {
59     if (n <= 20) {
60       return BigInteger.valueOf(LongMath.factorial(n));
61     } else {
62       int k = 20;
63       return BigInteger.valueOf(LongMath.factorial(k)).multiply(oldSlowFactorial(k, n));
64     }
65   }
66 
67   /**
68    * Returns the product of {@code n1} exclusive through {@code n2} inclusive.
69    */
oldSlowFactorial(int n1, int n2)70   private static BigInteger oldSlowFactorial(int n1, int n2) {
71     assert n1 <= n2;
72     if (IntMath.log2(n2, CEILING) * (n2 - n1) < Long.SIZE - 1) {
73       // the result will definitely fit into a long
74       long result = 1;
75       for (int i = n1 + 1; i <= n2; i++) {
76         result *= i;
77       }
78       return BigInteger.valueOf(result);
79     }
80 
81     /*
82      * We want each multiplication to have both sides with approximately the same number of digits.
83      * Currently, we just divide the range in half.
84      */
85     int mid = (n1 + n2) >>> 1;
86     return oldSlowFactorial(n1, mid).multiply(oldSlowFactorial(mid, n2));
87   }
88 
slowFactorial(int reps)89   @Benchmark int slowFactorial(int reps) {
90     int tmp = 0;
91     for (int i = 0; i < reps; i++) {
92       int j = i & ARRAY_MASK;
93       tmp += oldSlowFactorial(slowFactorials[j]).intValue();
94     }
95     return tmp;
96   }
97 
factorial(int reps)98   @Benchmark int factorial(int reps) {
99     int tmp = 0;
100     for (int i = 0; i < reps; i++) {
101       int j = i & ARRAY_MASK;
102       tmp += BigIntegerMath.factorial(factorials[j]).intValue();
103     }
104     return tmp;
105   }
106 
binomial(int reps)107   @Benchmark int binomial(int reps) {
108     int tmp = 0;
109     for (int i = 0; i < reps; i++) {
110       int j = i & 0xffff;
111       tmp += BigIntegerMath.binomial(factorials[j], binomials[j]).intValue();
112     }
113     return tmp;
114   }
115 }
116