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.math3.random;
18  
19  import java.io.Serializable;
20  
21  import org.apache.commons.math3.exception.NotStrictlyPositiveException;
22  import org.apache.commons.math3.exception.OutOfRangeException;
23  import org.apache.commons.math3.util.FastMath;
24  
25  /** Base class for random number generators that generates bits streams.
26   *
27   * @since 2.0
28   */
29  public abstract class BitsStreamGenerator
30      implements RandomGenerator,
31                 Serializable {
32      /** Serializable version identifier */
33      private static final long serialVersionUID = 20130104L;
34      /** Next gaussian. */
35      private double nextGaussian;
36  
37      /**
38       * Creates a new random number generator.
39       */
40      public BitsStreamGenerator() {
41          nextGaussian = Double.NaN;
42      }
43  
44      /** {@inheritDoc} */
45      public abstract void setSeed(int seed);
46  
47      /** {@inheritDoc} */
48      public abstract void setSeed(int[] seed);
49  
50      /** {@inheritDoc} */
51      public abstract void setSeed(long seed);
52  
53      /** Generate next pseudorandom number.
54       * <p>This method is the core generation algorithm. It is used by all the
55       * public generation methods for the various primitive types {@link
56       * #nextBoolean()}, {@link #nextBytes(byte[])}, {@link #nextDouble()},
57       * {@link #nextFloat()}, {@link #nextGaussian()}, {@link #nextInt()},
58       * {@link #next(int)} and {@link #nextLong()}.</p>
59       * @param bits number of random bits to produce
60       * @return random bits generated
61       */
62      protected abstract int next(int bits);
63  
64      /** {@inheritDoc} */
65      public boolean nextBoolean() {
66          return next(1) != 0;
67      }
68  
69      /** {@inheritDoc} */
70      public double nextDouble() {
71          final long high = ((long) next(26)) << 26;
72          final int  low  = next(26);
73          return (high | low) * 0x1.0p-52d;
74      }
75  
76      /** {@inheritDoc} */
77      public float nextFloat() {
78          return next(23) * 0x1.0p-23f;
79      }
80  
81      /** {@inheritDoc} */
82      public double nextGaussian() {
83  
84          final double random;
85          if (Double.isNaN(nextGaussian)) {
86              // generate a new pair of gaussian numbers
87              final double x = nextDouble();
88              final double y = nextDouble();
89              final double alpha = 2 * FastMath.PI * x;
90              final double r      = FastMath.sqrt(-2 * FastMath.log(y));
91              random       = r * FastMath.cos(alpha);
92              nextGaussian = r * FastMath.sin(alpha);
93          } else {
94              // use the second element of the pair already generated
95              random = nextGaussian;
96              nextGaussian = Double.NaN;
97          }
98  
99          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 }