Home | History | Annotate | Download | only in math 
      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    */
     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    */
     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    */
     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    */
     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    */
    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    */
    118   static int randomExponent() {
    119     return RANDOM_SOURCE.nextInt(MAX_EXPONENT + 1);
    120   }
    121 
    122   static double randomPositiveDouble() {
    123     return Math.exp(randomDouble(6));
    124   }
    125 }
    126