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. */ oldSlowFactorial(int n1, int n2)62 private static BigInteger oldSlowFactorial(int n1, int n2) { 63 assert n1 <= n2; 64 if (IntMath.log2(n2, CEILING) * (n2 - n1) < Long.SIZE - 1) { 65 // the result will definitely fit into a long 66 long result = 1; 67 for (int i = n1 + 1; i <= n2; i++) { 68 result *= i; 69 } 70 return BigInteger.valueOf(result); 71 } 72 73 /* 74 * We want each multiplication to have both sides with approximately the same number of digits. 75 * Currently, we just divide the range in half. 76 */ 77 int mid = (n1 + n2) >>> 1; 78 return oldSlowFactorial(n1, mid).multiply(oldSlowFactorial(mid, n2)); 79 } 80 81 @Benchmark slowFactorial(int reps)82 int slowFactorial(int reps) { 83 int tmp = 0; 84 for (int i = 0; i < reps; i++) { 85 int j = i & ARRAY_MASK; 86 tmp += oldSlowFactorial(slowFactorials[j]).intValue(); 87 } 88 return tmp; 89 } 90 91 @Benchmark factorial(int reps)92 int factorial(int reps) { 93 int tmp = 0; 94 for (int i = 0; i < reps; i++) { 95 int j = i & ARRAY_MASK; 96 tmp += BigIntegerMath.factorial(factorials[j]).intValue(); 97 } 98 return tmp; 99 } 100 101 @Benchmark binomial(int reps)102 int binomial(int reps) { 103 int tmp = 0; 104 for (int i = 0; i < reps; i++) { 105 int j = i & 0xffff; 106 tmp += BigIntegerMath.binomial(factorials[j], binomials[j]).intValue(); 107 } 108 return tmp; 109 } 110 } 111