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