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.math3.random;
018
019import java.io.Serializable;
020
021import org.apache.commons.math3.exception.NotStrictlyPositiveException;
022import org.apache.commons.math3.exception.OutOfRangeException;
023import org.apache.commons.math3.util.FastMath;
024
025/** Base class for random number generators that generates bits streams.
026 *
027 * @since 2.0
028 */
029public abstract class BitsStreamGenerator
030    implements RandomGenerator,
031               Serializable {
032    /** Serializable version identifier */
033    private static final long serialVersionUID = 20130104L;
034    /** Next gaussian. */
035    private double nextGaussian;
036
037    /**
038     * Creates a new random number generator.
039     */
040    public BitsStreamGenerator() {
041        nextGaussian = Double.NaN;
042    }
043
044    /** {@inheritDoc} */
045    public abstract void setSeed(int seed);
046
047    /** {@inheritDoc} */
048    public abstract void setSeed(int[] seed);
049
050    /** {@inheritDoc} */
051    public abstract void setSeed(long seed);
052
053    /** Generate next pseudorandom number.
054     * <p>This method is the core generation algorithm. It is used by all the
055     * public generation methods for the various primitive types {@link
056     * #nextBoolean()}, {@link #nextBytes(byte[])}, {@link #nextDouble()},
057     * {@link #nextFloat()}, {@link #nextGaussian()}, {@link #nextInt()},
058     * {@link #next(int)} and {@link #nextLong()}.</p>
059     * @param bits number of random bits to produce
060     * @return random bits generated
061     */
062    protected abstract int next(int bits);
063
064    /** {@inheritDoc} */
065    public boolean nextBoolean() {
066        return next(1) != 0;
067    }
068
069    /** {@inheritDoc} */
070    public double nextDouble() {
071        final long high = ((long) next(26)) << 26;
072        final int  low  = next(26);
073        return (high | low) * 0x1.0p-52d;
074    }
075
076    /** {@inheritDoc} */
077    public float nextFloat() {
078        return next(23) * 0x1.0p-23f;
079    }
080
081    /** {@inheritDoc} */
082    public double nextGaussian() {
083
084        final double random;
085        if (Double.isNaN(nextGaussian)) {
086            // generate a new pair of gaussian numbers
087            final double x = nextDouble();
088            final double y = nextDouble();
089            final double alpha = 2 * FastMath.PI * x;
090            final double r      = FastMath.sqrt(-2 * FastMath.log(y));
091            random       = r * FastMath.cos(alpha);
092            nextGaussian = r * FastMath.sin(alpha);
093        } else {
094            // use the second element of the pair already generated
095            random = nextGaussian;
096            nextGaussian = Double.NaN;
097        }
098
099        return random;
100
101    }
102
103    /** {@inheritDoc} */
104    public int nextInt() {
105        return next(32);
106    }
107
108    /**
109     * {@inheritDoc}
110     * <p>This default implementation is copied from Apache Harmony
111     * java.util.Random (r929253).</p>
112     *
113     * <p>Implementation notes: <ul>
114     * <li>If n is a power of 2, this method returns
115     * {@code (int) ((n * (long) next(31)) >> 31)}.</li>
116     *
117     * <li>If n is not a power of 2, what is returned is {@code next(31) % n}
118     * with {@code next(31)} values rejected (i.e. regenerated) until a
119     * value that is larger than the remainder of {@code Integer.MAX_VALUE / n}
120     * is generated. Rejection of this initial segment is necessary to ensure
121     * a uniform distribution.</li></ul></p>
122     */
123    public int nextInt(int n) throws IllegalArgumentException {
124        if (n > 0) {
125            if ((n & -n) == n) {
126                return (int) ((n * (long) next(31)) >> 31);
127            }
128            int bits;
129            int val;
130            do {
131                bits = next(31);
132                val = bits % n;
133            } while (bits - val + (n - 1) < 0);
134            return val;
135        }
136        throw new NotStrictlyPositiveException(n);
137    }
138
139    /** {@inheritDoc} */
140    public long nextLong() {
141        final long high  = ((long) next(32)) << 32;
142        final long  low  = ((long) next(32)) & 0xffffffffL;
143        return high | low;
144    }
145
146    /**
147     * Returns a pseudorandom, uniformly distributed {@code long} value
148     * between 0 (inclusive) and the specified value (exclusive), drawn from
149     * this random number generator's sequence.
150     *
151     * @param n the bound on the random number to be returned.  Must be
152     * positive.
153     * @return  a pseudorandom, uniformly distributed {@code long}
154     * value between 0 (inclusive) and n (exclusive).
155     * @throws IllegalArgumentException  if n is not positive.
156     */
157    public long nextLong(long n) throws IllegalArgumentException {
158        if (n > 0) {
159            long bits;
160            long val;
161            do {
162                bits = ((long) next(31)) << 32;
163                bits |= ((long) next(32)) & 0xffffffffL;
164                val  = bits % n;
165            } while (bits - val + (n - 1) < 0);
166            return val;
167        }
168        throw new NotStrictlyPositiveException(n);
169    }
170
171    /**
172     * Clears the cache used by the default implementation of
173     * {@link #nextGaussian}.
174     */
175    public void clear() {
176        nextGaussian = Double.NaN;
177    }
178
179    /**
180     * Generates random bytes and places them into a user-supplied array.
181     *
182     * <p>
183     * The array is filled with bytes extracted from random integers.
184     * This implies that the number of random bytes generated may be larger than
185     * the length of the byte array.
186     * </p>
187     *
188     * @param bytes Array in which to put the generated bytes. Cannot be {@code null}.
189     */
190    public void nextBytes(byte[] bytes) {
191        nextBytesFill(bytes, 0, bytes.length);
192    }
193
194    /**
195     * Generates random bytes and places them into a user-supplied array.
196     *
197     * <p>
198     * The array is filled with bytes extracted from random integers.
199     * This implies that the number of random bytes generated may be larger than
200     * the length of the byte array.
201     * </p>
202     *
203     * @param bytes Array in which to put the generated bytes. Cannot be {@code null}.
204     * @param start Index at which to start inserting the generated bytes.
205     * @param len Number of bytes to insert.
206     * @throws OutOfRangeException if {@code start < 0} or {@code start >= bytes.length}.
207     * @throws OutOfRangeException if {@code len < 0} or {@code len > bytes.length - start}.
208     */
209    public void nextBytes(byte[] bytes,
210                          int start,
211                          int len) {
212        if (start < 0 ||
213            start >= bytes.length) {
214            throw new OutOfRangeException(start, 0, bytes.length);
215        }
216        if (len < 0 ||
217            len > bytes.length - start) {
218            throw new OutOfRangeException(len, 0, bytes.length - start);
219        }
220
221        nextBytesFill(bytes, start, len);
222    }
223
224    /**
225     * Generates random bytes and places them into a user-supplied array.
226     *
227     * <p>
228     * The array is filled with bytes extracted from random integers.
229     * This implies that the number of random bytes generated may be larger than
230     * the length of the byte array.
231     * </p>
232     *
233     * @param bytes Array in which to put the generated bytes. Cannot be {@code null}.
234     * @param start Index at which to start inserting the generated bytes.
235     * @param len Number of bytes to insert.
236     */
237    private void nextBytesFill(byte[] bytes,
238                               int start,
239                               int len) {
240        int index = start; // Index of first insertion.
241
242        // Index of first insertion plus multiple 4 part of length (i.e. length
243        // with two least significant bits unset).
244        final int indexLoopLimit = index + (len & 0x7ffffffc);
245
246        // Start filling in the byte array, 4 bytes at a time.
247        while (index < indexLoopLimit) {
248            final int random = next(32);
249            bytes[index++] = (byte) random;
250            bytes[index++] = (byte) (random >>> 8);
251            bytes[index++] = (byte) (random >>> 16);
252            bytes[index++] = (byte) (random >>> 24);
253        }
254
255        final int indexLimit = start + len; // Index of last insertion + 1.
256
257        // Fill in the remaining bytes.
258        if (index < indexLimit) {
259            int random = next(32);
260            while (true) {
261                bytes[index++] = (byte) random;
262                if (index < indexLimit) {
263                    random >>>= 8;
264                } else {
265                    break;
266                }
267            }
268        }
269    }
270}