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 java.math.BigInteger; 20 import java.util.Random; 21 22 /** 23 * Utilities for benchmarks. 24 * 25 * <p>In many cases, we wish to vary the order of magnitude of the input as much as we want to vary 26 * the input itself, so most methods which generate values use an exponential distribution varying 27 * the order of magnitude of the generated values uniformly at random. 28 * 29 * @author Louis Wasserman 30 */ 31 final class MathBenchmarking { 32 static final int ARRAY_SIZE = 0x10000; 33 static final int ARRAY_MASK = 0x0ffff; 34 static final Random RANDOM_SOURCE = new Random(314159265358979L); 35 static final int MAX_EXPONENT = 100; 36 37 /* 38 * Duplicated from LongMath. 39 * binomial(biggestBinomials[k], k) fits in a long, but not 40 * binomial(biggestBinomials[k] + 1, k). 41 */ 42 static final int[] biggestBinomials = { 43 Integer.MAX_VALUE, 44 Integer.MAX_VALUE, 45 Integer.MAX_VALUE, 46 3810779, 47 121977, 48 16175, 49 4337, 50 1733, 51 887, 52 534, 53 361, 54 265, 55 206, 56 169, 57 143, 58 125, 59 111, 60 101, 61 94, 62 88, 63 83, 64 79, 65 76, 66 74, 67 72, 68 70, 69 69, 70 68, 71 67, 72 67, 73 66, 74 66, 75 66, 76 66 77 }; 78 79 /** 80 * Generates values in a distribution equivalent to randomNonNegativeBigInteger but omitting zero. 81 */ randomPositiveBigInteger(int numBits)82 static BigInteger randomPositiveBigInteger(int numBits) { 83 BigInteger result; 84 do { 85 result = randomNonNegativeBigInteger(numBits); 86 } while (result.signum() == 0); 87 return result; 88 } 89 90 /** 91 * Generates a number in [0, 2^numBits) with an exponential distribution. The floor of the log2 of 92 * the result is chosen uniformly at random in [0, numBits), and then the result is chosen in that 93 * range uniformly at random. Zero is treated as having log2 == 0. 94 */ randomNonNegativeBigInteger(int numBits)95 static BigInteger randomNonNegativeBigInteger(int numBits) { 96 int digits = RANDOM_SOURCE.nextInt(numBits); 97 if (digits == 0) { 98 return new BigInteger(1, RANDOM_SOURCE); 99 } else { 100 return new BigInteger(digits, RANDOM_SOURCE).setBit(digits); 101 } 102 } 103 104 /** 105 * Equivalent to calling randomPositiveBigInteger(numBits) and then flipping the sign with 50% 106 * probability. 107 */ randomNonZeroBigInteger(int numBits)108 static BigInteger randomNonZeroBigInteger(int numBits) { 109 BigInteger result = randomPositiveBigInteger(numBits); 110 return RANDOM_SOURCE.nextBoolean() ? result : result.negate(); 111 } 112 113 /** 114 * Chooses a number in (-2^numBits, 2^numBits) at random, with density concentrated in numbers of 115 * lower magnitude. 116 */ randomBigInteger(int numBits)117 static BigInteger randomBigInteger(int numBits) { 118 while (true) { 119 if (RANDOM_SOURCE.nextBoolean()) { 120 return randomNonNegativeBigInteger(numBits); 121 } 122 BigInteger neg = randomNonNegativeBigInteger(numBits).negate(); 123 if (neg.signum() != 0) { 124 return neg; 125 } 126 } 127 } 128 129 /** 130 * Generates a number in [0, 2^numBits) with an exponential distribution. The floor of the log2 of 131 * the absolute value of the result is chosen uniformly at random in [0, numBits), and then the 132 * result is chosen from those possibilities uniformly at random. 133 * 134 * <p>Zero is treated as having log2 == 0. 135 */ randomDouble(int maxExponent)136 static double randomDouble(int maxExponent) { 137 double result = RANDOM_SOURCE.nextDouble(); 138 result = Math.scalb(result, RANDOM_SOURCE.nextInt(maxExponent + 1)); 139 return RANDOM_SOURCE.nextBoolean() ? result : -result; 140 } 141 142 /** Returns a random integer between zero and {@code MAX_EXPONENT}. */ randomExponent()143 static int randomExponent() { 144 return RANDOM_SOURCE.nextInt(MAX_EXPONENT + 1); 145 } 146 randomPositiveDouble()147 static double randomPositiveDouble() { 148 return Math.exp(randomDouble(6)); 149 } 150 } 151