View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.rng.sampling.distribution;
18  
19  import org.apache.commons.rng.UniformRandomProvider;
20  
21  /**
22   * Sampling from an <a href="http://mathworld.wolfram.com/ExponentialDistribution.html">exponential distribution</a>.
23   *
24   * @since 1.0
25   */
26  public class AhrensDieterExponentialSampler
27      extends SamplerBase
28      implements ContinuousSampler {
29      /**
30       * Table containing the constants
31       * \( q_i = sum_{j=1}^i (\ln 2)^j / j! = \ln 2 + (\ln 2)^2 / 2 + ... + (\ln 2)^i / i! \)
32       * until the largest representable fraction below 1 is exceeded.
33       *
34       * Note that
35       * \( 1 = 2 - 1 = \exp(\ln 2) - 1 = sum_{n=1}^\infinity (\ln 2)^n / n! \)
36       * thus \( q_i \rightarrow 1 as i \rightarrow +\infinity \),
37       * so the higher \( i \), the closer we get to 1 (the series is not alternating).
38       *
39       * By trying, n = 16 in Java is enough to reach 1.
40       */
41      private static final double[] EXPONENTIAL_SA_QI = new double[16];
42      /** The mean of this distribution. */
43      private final double mean;
44      /** Underlying source of randomness. */
45      private final UniformRandomProvider rng;
46  
47      /**
48       * Initialize tables.
49       */
50      static {
51          /**
52           * Filling EXPONENTIAL_SA_QI table.
53           * Note that we don't want qi = 0 in the table.
54           */
55          final double ln2 = Math.log(2);
56          double qi = 0;
57  
58          for (int i = 0; i < EXPONENTIAL_SA_QI.length; i++) {
59              qi += Math.pow(ln2, i + 1) / InternalUtils.factorial(i + 1);
60              EXPONENTIAL_SA_QI[i] = qi;
61          }
62      }
63  
64      /**
65       * @param rng Generator of uniformly distributed random numbers.
66       * @param mean Mean of this distribution.
67       */
68      public AhrensDieterExponentialSampler(UniformRandomProvider rng,
69                                            double mean) {
70          super(null);
71          this.rng = rng;
72          this.mean = mean;
73      }
74  
75      /** {@inheritDoc} */
76      @Override
77      public double sample() {
78          // Step 1:
79          double a = 0;
80          double u = rng.nextDouble();
81  
82          // Step 2 and 3:
83          while (u < 0.5) {
84              a += EXPONENTIAL_SA_QI[0];
85              u *= 2;
86          }
87  
88          // Step 4 (now u >= 0.5):
89          u += u - 1;
90  
91          // Step 5:
92          if (u <= EXPONENTIAL_SA_QI[0]) {
93              return mean * (a + u);
94          }
95  
96          // Step 6:
97          int i = 0; // Should be 1, be we iterate before it in while using 0.
98          double u2 = rng.nextDouble();
99          double umin = u2;
100 
101         // Step 7 and 8:
102         do {
103             ++i;
104             u2 = rng.nextDouble();
105 
106             if (u2 < umin) {
107                 umin = u2;
108             }
109 
110             // Step 8:
111         } while (u > EXPONENTIAL_SA_QI[i]); // Ensured to exit since EXPONENTIAL_SA_QI[MAX] = 1.
112 
113         return mean * (a + umin * EXPONENTIAL_SA_QI[0]);
114     }
115 
116     /** {@inheritDoc} */
117     @Override
118     public String toString() {
119         return "Ahrens-Dieter Exponential deviate [" + rng.toString() + "]";
120     }
121 }