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     */
017    package org.apache.commons.math.random;
018    
019    import org.apache.commons.math.MathRuntimeException;
020    
021    /**
022     * Abstract class implementing the {@link  RandomGenerator} interface.
023     * Default implementations for all methods other than {@link #nextDouble()} and
024     * {@link #setSeed(long)} are provided. 
025     * <p>
026     * All data generation methods are based on <code>nextDouble().</code>
027     * Concrete implementations <strong>must</strong> override
028     * this method and <strong>should</strong> provide better / more
029     * performant implementations of the other methods if the underlying PRNG
030     * supplies them.</p>
031     *
032     * @since 1.1
033     * @version $Revision: 796543 $ $Date: 2009-07-21 17:32:38 -0400 (Tue, 21 Jul 2009) $
034     */
035    public abstract class AbstractRandomGenerator implements RandomGenerator {
036        
037        /** 
038         * Cached random normal value.  The default implementation for 
039         * {@link #nextGaussian} generates pairs of values and this field caches the
040         * second value so that the full algorithm is not executed for every
041         * activation.  The value <code>Double.NaN</code> signals that there is
042         * no cached value.  Use {@link #clear} to clear the cached value.
043         */
044        private double cachedNormalDeviate = Double.NaN;
045        
046        /**
047         * Construct a RandomGenerator.
048         */
049        public AbstractRandomGenerator() {
050            super();
051            
052        }
053        
054        /**
055         * Clears the cache used by the default implementation of 
056         * {@link #nextGaussian}. Implemementations that do not override the
057         * default implementation of <code>nextGaussian</code> should call this
058         * method in the implementation of {@link #setSeed(long)}
059         */
060        public void clear() {
061            cachedNormalDeviate = Double.NaN;
062        }
063    
064        /** {@inheritDoc} */
065        public void setSeed(int seed) {
066            setSeed((long) seed);
067        }
068    
069        /** {@inheritDoc} */
070        public void setSeed(int[] seed) {
071            // the following number is the largest prime that fits in 32 bits (it is 2^32 - 5)
072            final long prime = 4294967291l;
073    
074            long combined = 0l;
075            for (int s : seed) {
076                combined = combined * prime + s;
077            }
078            setSeed(combined);
079        }
080    
081        /**
082         * Sets the seed of the underyling random number generator using a 
083         * <code>long</code> seed.  Sequences of values generated starting with the
084         * same seeds should be identical.
085         * <p>
086         * Implementations that do not override the default implementation of 
087         * <code>nextGaussian</code> should include a call to {@link #clear} in the
088         * implementation of this method.</p>
089         *
090         * @param seed the seed value
091         */
092        public abstract void setSeed(long seed);  
093    
094        /**
095         * Generates random bytes and places them into a user-supplied 
096         * byte array.  The number of random bytes produced is equal to 
097         * the length of the byte array.
098         * <p>
099         * The default implementation fills the array with bytes extracted from
100         * random integers generated using {@link #nextInt}.</p>
101         * 
102         * @param bytes the non-null byte array in which to put the 
103         * random bytes
104         */
105        public void nextBytes(byte[] bytes) {
106            int bytesOut = 0;
107            while (bytesOut < bytes.length) {
108              int randInt = nextInt();
109              for (int i = 0; i < 3; i++) {
110                  if ( i > 0) {
111                      randInt = randInt >> 8;
112                  }
113                  bytes[bytesOut++] = (byte) randInt;
114                  if (bytesOut == bytes.length) {
115                      return;
116                  }
117              }
118            }
119        }
120    
121         /**
122         * Returns the next pseudorandom, uniformly distributed <code>int</code>
123         * value from this random number generator's sequence.  
124         * All 2<font size="-1"><sup>32</sup></font> possible <tt>int</tt> values
125         * should be produced with  (approximately) equal probability. 
126         * <p>
127         * The default implementation provided here returns 
128         * <pre>
129         * <code>(int) (nextDouble() * Integer.MAX_VALUE)</code>
130         * </pre></p>
131         *
132         * @return the next pseudorandom, uniformly distributed <code>int</code>
133         *  value from this random number generator's sequence
134         */
135        public int nextInt() {
136            return (int) (nextDouble() * Integer.MAX_VALUE);
137        }
138    
139        /**
140         * Returns a pseudorandom, uniformly distributed <tt>int</tt> value
141         * between 0 (inclusive) and the specified value (exclusive), drawn from
142         * this random number generator's sequence. 
143         * <p>  
144         * The default implementation returns 
145         * <pre>
146         * <code>(int) (nextDouble() * n</code>
147         * </pre></p>
148         *
149         * @param n the bound on the random number to be returned.  Must be
150         * positive.
151         * @return  a pseudorandom, uniformly distributed <tt>int</tt>
152         * value between 0 (inclusive) and n (exclusive).
153         * @throws IllegalArgumentException if n is not positive.
154         */
155        public int nextInt(int n) {
156            if (n <= 0 ) {
157                throw MathRuntimeException.createIllegalArgumentException(
158                      "upper bound must be positive ({0})", n);
159            }
160            int result = (int) (nextDouble() * n);
161            return result < n ? result : n - 1;
162        }
163    
164         /**
165         * Returns the next pseudorandom, uniformly distributed <code>long</code>
166         * value from this random number generator's sequence.  All 
167         * 2<font size="-1"><sup>64</sup></font> possible <tt>long</tt> values 
168         * should be produced with (approximately) equal probability. 
169         * <p>  
170         * The default implementation returns 
171         * <pre>
172         * <code>(long) (nextDouble() * Long.MAX_VALUE)</code>
173         * </pre></p>
174         *
175         * @return  the next pseudorandom, uniformly distributed <code>long</code>
176         *value from this random number generator's sequence
177         */
178        public long nextLong() {
179            return (long) (nextDouble() * Long.MAX_VALUE);
180        }
181    
182        /**
183         * Returns the next pseudorandom, uniformly distributed
184         * <code>boolean</code> value from this random number generator's
185         * sequence.  
186         * <p>  
187         * The default implementation returns 
188         * <pre>
189         * <code>nextDouble() <= 0.5</code>
190         * </pre></p>
191         * 
192         * @return  the next pseudorandom, uniformly distributed
193         * <code>boolean</code> value from this random number generator's
194         * sequence
195         */
196        public boolean nextBoolean() {
197            return nextDouble() <= 0.5;
198        }
199    
200         /**
201         * Returns the next pseudorandom, uniformly distributed <code>float</code>
202         * value between <code>0.0</code> and <code>1.0</code> from this random
203         * number generator's sequence.  
204         * <p>  
205         * The default implementation returns 
206         * <pre>
207         * <code>(float) nextDouble() </code>
208         * </pre></p>
209         *
210         * @return  the next pseudorandom, uniformly distributed <code>float</code>
211         * value between <code>0.0</code> and <code>1.0</code> from this
212         * random number generator's sequence
213         */
214        public float nextFloat() {
215            return (float) nextDouble();
216        }
217    
218        /**
219         * Returns the next pseudorandom, uniformly distributed 
220         * <code>double</code> value between <code>0.0</code> and
221         * <code>1.0</code> from this random number generator's sequence.  
222         * <p>
223         * This method provides the underlying source of random data used by the
224         * other methods.</p>   
225         *
226         * @return  the next pseudorandom, uniformly distributed 
227         *  <code>double</code> value between <code>0.0</code> and
228         *  <code>1.0</code> from this random number generator's sequence
229         */  
230        public abstract double nextDouble();  
231    
232        /**
233         * Returns the next pseudorandom, Gaussian ("normally") distributed
234         * <code>double</code> value with mean <code>0.0</code> and standard
235         * deviation <code>1.0</code> from this random number generator's sequence.
236         * <p>
237         * The default implementation uses the <em>Polar Method</em>
238         * due to G.E.P. Box, M.E. Muller and G. Marsaglia, as described in 
239         * D. Knuth, <u>The Art of Computer Programming</u>, 3.4.1C.</p>
240         * <p>
241         * The algorithm generates a pair of independent random values.  One of
242         * these is cached for reuse, so the full algorithm is not executed on each
243         * activation.  Implementations that do not override this method should
244         * make sure to call {@link #clear} to clear the cached value in the 
245         * implementation of {@link #setSeed(long)}.</p>
246         * 
247         * @return  the next pseudorandom, Gaussian ("normally") distributed
248         * <code>double</code> value with mean <code>0.0</code> and
249         * standard deviation <code>1.0</code> from this random number
250         *  generator's sequence
251         */
252        public double nextGaussian() {
253            if (!Double.isNaN(cachedNormalDeviate)) {
254                double dev = cachedNormalDeviate;
255                cachedNormalDeviate = Double.NaN;
256                return dev;
257            }
258            double v1 = 0;
259            double v2 = 0;
260            double s = 1;
261            while (s >=1 ) { 
262                v1 = 2 * nextDouble() - 1; 
263                v2 = 2 * nextDouble() - 1; 
264                s = v1 * v1 + v2 * v2;
265            }
266            if (s != 0) {
267                s = Math.sqrt(-2 * Math.log(s) / s);   
268            }
269            cachedNormalDeviate = v2 * s;
270            return v1 * s;      
271        }
272    }