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