001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.rng.sampling.distribution;
018
019import org.apache.commons.rng.UniformRandomProvider;
020
021/**
022 * Sampling from an <a href="http://mathworld.wolfram.com/ExponentialDistribution.html">exponential distribution</a>.
023 *
024 * @since 1.0
025 */
026public class AhrensDieterExponentialSampler
027    extends SamplerBase
028    implements ContinuousSampler {
029    /**
030     * Table containing the constants
031     * \( q_i = sum_{j=1}^i (\ln 2)^j / j! = \ln 2 + (\ln 2)^2 / 2 + ... + (\ln 2)^i / i! \)
032     * until the largest representable fraction below 1 is exceeded.
033     *
034     * Note that
035     * \( 1 = 2 - 1 = \exp(\ln 2) - 1 = sum_{n=1}^\infinity (\ln 2)^n / n! \)
036     * thus \( q_i \rightarrow 1 as i \rightarrow +\infinity \),
037     * so the higher \( i \), the closer we get to 1 (the series is not alternating).
038     *
039     * By trying, n = 16 in Java is enough to reach 1.
040     */
041    private static final double[] EXPONENTIAL_SA_QI = new double[16];
042    /** The mean of this distribution. */
043    private final double mean;
044    /** Underlying source of randomness. */
045    private final UniformRandomProvider rng;
046
047    /**
048     * Initialize tables.
049     */
050    static {
051        /**
052         * Filling EXPONENTIAL_SA_QI table.
053         * Note that we don't want qi = 0 in the table.
054         */
055        final double ln2 = Math.log(2);
056        double qi = 0;
057
058        for (int i = 0; i < EXPONENTIAL_SA_QI.length; i++) {
059            qi += Math.pow(ln2, i + 1) / InternalUtils.factorial(i + 1);
060            EXPONENTIAL_SA_QI[i] = qi;
061        }
062    }
063
064    /**
065     * @param rng Generator of uniformly distributed random numbers.
066     * @param mean Mean of this distribution.
067     */
068    public AhrensDieterExponentialSampler(UniformRandomProvider rng,
069                                          double mean) {
070        super(null);
071        this.rng = rng;
072        this.mean = mean;
073    }
074
075    /** {@inheritDoc} */
076    @Override
077    public double sample() {
078        // Step 1:
079        double a = 0;
080        double u = rng.nextDouble();
081
082        // Step 2 and 3:
083        while (u < 0.5) {
084            a += EXPONENTIAL_SA_QI[0];
085            u *= 2;
086        }
087
088        // Step 4 (now u >= 0.5):
089        u += u - 1;
090
091        // Step 5:
092        if (u <= EXPONENTIAL_SA_QI[0]) {
093            return mean * (a + u);
094        }
095
096        // Step 6:
097        int i = 0; // Should be 1, be we iterate before it in while using 0.
098        double u2 = rng.nextDouble();
099        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}