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