KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jahia > utils > keygenerator > MersenneTwister


1 package org.jahia.utils.keygenerator;
2
3
4 import java.io.IOException JavaDoc;
5 import java.io.ObjectInputStream JavaDoc;
6 import java.io.ObjectOutputStream JavaDoc;
7 import java.io.Serializable JavaDoc;
8
9 /**
10  * Mersenne Twister and MersenneTwisterFast:
11  * <P>
12  * <b>MersenneTwister</b> is a drop-in subclass replacement
13  * for java.util.Random. It is properly synchronized and
14  * can be used in a multithreaded environment.
15  *
16  * <p><b>MersenneTwisterFast</b> is not a subclass of java.util.Random. It has
17  * the same public methods as Random does, however, and it is
18  * algorithmically identical to MersenneTwister. MersenneTwisterFast
19  * has hard-code inlined all of its methods directly, and made all of them
20  * final (well, the ones of consequence anyway). Further, these
21  * methods are <i>not</i> synchronized, so the same MersenneTwisterFast
22  * instance cannot be shared by multiple threads. But all this helps
23  * MersenneTwisterFast achieve over twice the speed of MersenneTwister.
24  *
25  * <p><b>About the Mersenne Twister. </b>
26  * This is a Java version of the C-program for MT19937: Integer version.
27  * next(32) generates one pseudorandom unsigned integer (32bit)
28
29  * which is uniformly distributed among 0 to 2^32-1 for each
30  * call. next(int bits) >>>'s by (32-bits) to get a value ranging
31  * between 0 and 2^bits-1 long inclusive; hope that's correct.
32  * setSeed(seed) set initial values to the working area
33  * of 624 words. For setSeed(seed), seed is any 32-bit integer
34  * <b>except for 0</b>.
35  *
36  * <p>Orignally Coded by Takuji Nishimura, considering the suggestions by
37  * Topher Cooper and Marc Rieffel in July-Aug. 1997.
38  * More information can be found
39  * <A HREF="http://www.math.keio.ac.jp/matumoto/emt.html">
40  * here. </a>
41
42  * <P>
43  * Translated to Java by Michael Lecuyer January 30, 1999
44  * Copyright (C) 1999 Michael Lecuyer
45  * <P>
46  * This library is free software; you can redistribute it and or
47
48  * modify it under the terms of the GNU Library General Public
49  * License as published by the Free Software Foundation; either
50  * version 2 of the License, or (at your option) any later
51  * version.
52  * This library is distributed in the hope that it will be useful,
53
54  * but WITHOUT ANY WARRANTY; without even the implied warranty of
55  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
56  * See the GNU Library General Public License for more details.
57  * You should have received a copy of the GNU Library General
58  * Public License along with this library; if not, write to the
59  * Free Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
60  * 02111-1307 USA
61  * <P>
62  * Makoto Matsumoto and Takuji Nishimura, the original authors
63  * ask "When you use this, send an email to: matumoto@math.keio.ac.jp
64  * with an appropriate reference to your work" You might also point
65  * out this was a translation.
66  * <P>
67  * <b>Reference. </b>
68  * M. Matsumoto and T. Nishimura,
69  * "Mersenne Twister: A 623-Dimensionally Equidistributed Uniform
70  * Pseudo-Random Number Generator",
71  * <i>ACM Transactions on Modeling and Computer Simulation,</i>
72  * Vol. 8, No. 1, January 1998, pp 3--30.
73  *
74  * <p><b>About this version. </b> This is a modification of the
75  * <a HREF="http://www.theorem.com/java/index.htm#Mersenne">original
76  * code</a> made to conform to proper java.util.Random format by
77  * <a HREF="http://www.cs.umd.edu/users/seanl/">Sean Luke,</a>
78  * August 7, 1999.
79  *
80  * <p><b>Bug Fixes. </b>This implementation implements the bug fixes made
81  * in Java 1.2's version of Random, which means it can be used with
82  * earlier versions of Java. See
83  * <a HREF="http://www.javasoft.com/products/jdk/1.2/docs/api/java/util/Random.html">
84  * the JDK 1.2 java.util.Random documentation</a> for further documentation
85  * on the random-number generation contracts made. Additionally, there's
86  * an undocumented bug in the JDK java.util.Random.nextBytes() method,
87  * which this code fixes.
88  *
89  * <p><b>Important Note. </b> Just like java.util.Random, this
90  * generator accepts a long seed but doesn't use all of it. java.util.Random
91  * uses 48 bits. The Mersenne Twister instead uses 32 bits (int size).
92  * So it's best if your seed does not exceed the int range.
93  */
94
95 public class MersenneTwister extends java.util.Random JavaDoc implements Serializable JavaDoc
96     {
97     // Period parameters
98 private static final int N = 624;
99     private static final int M = 397;
100     private static final int MATRIX_A = 0x9908b0df; // private static final * constant vector a
101 private static final int UPPER_MASK = 0x80000000; // most significant w-r bits
102 private static final int LOWER_MASK = 0x7fffffff; // least significant r bits
103
104
105     // Tempering parameters
106
107     private static final int TEMPERING_MASK_B = 0x9d2c5680;
108     private static final int TEMPERING_MASK_C = 0xefc60000;
109     
110     // #define TEMPERING_SHIFT_U(y) (y >>> 11)
111 // #define TEMPERING_SHIFT_S(y) (y << 7)
112 // #define TEMPERING_SHIFT_T(y) (y << 15)
113 // #define TEMPERING_SHIFT_L(y) (y >>> 18)
114
115     private int mt[]; // the array for the state vector
116 private int mti; // mti==N+1 means mt[N] is not initialized
117 private int mag01[];
118     
119     // a good initial seed (of int size, though stored in a long)
120 private static final long GOOD_SEED = 4357;
121
122
123     /**
124      * Constructor using the default seed.
125      */
126     public MersenneTwister()
127         {
128         super(GOOD_SEED);
129         setSeed(GOOD_SEED);
130         }
131     
132     /**
133      * Constructor using a given seed. Though you pass this seed in
134      * as a long, it's best to make sure it's actually an integer.
135      *
136      * @param seed generator starting number, often the time of day.
137      */
138     public MersenneTwister(long seed)
139         {
140         super(seed); /* just in case */
141         setSeed(seed);
142         }
143     
144     /**
145      * Initalize the pseudo random number generator.
146      * The Mersenne Twister only uses an integer for its seed;
147      * It's best that you don't pass in a long that's bigger
148      * than an int.
149      *
150      * Note that for very old versions of jdk (like 1.0.2),
151      * setSeed will not properly reset the gaussian mechanism,
152      * so nextGaussian() may return <i>one</i> more extra
153      * gaussian drawn from the old seed rather than the new one.
154      *
155      * @param seed from constructor
156      *
157      */
158
159     synchronized public void setSeed(long seed)
160         {
161
162         // this lets java.util.Random clear its nextNextGaussian field
163 // Note this is broken in older jdks like 1.0.2. -- nextNextGaussian
164 // will not be cleared so the very next gaussian you get *may* be drawn
165 // from the old seed's generation.
166
167         super.setSeed(seed);
168
169         mt = new int[N];
170         
171         // setting initial seeds to mt[N] using
172 // the generator Line 25 of Table 1 in
173 // [KNUTH 1981, The Art of Computer Programming
174 // Vol. 2 (2nd Ed.), pp102]
175
176         // the 0xffffffff is commented out because in Java
177 // ints are always 32 bits; hence i & 0xffffffff == i
178
179         mt[0]= ((int)seed); // & 0xffffffff;
180
181         for (mti = 1; mti < N; mti++)
182             mt[mti] = (69069 * mt[mti-1]); //& 0xffffffff;
183
184         // mag01[x] = x * MATRIX_A for x=0,1
185 mag01 = new int[2];
186         mag01[0] = 0x0;
187         mag01[1] = MATRIX_A;
188         }
189     
190     /**
191      * Returns an integer with <i>bits</i> bits filled with a random number.
192      */
193     synchronized protected int next(int bits)
194         {
195         int y;
196         
197         if (mti >= N) // generate N words at one time
198 {
199             int kk;
200             
201             for (kk = 0; kk < N - M; kk++)
202                 {
203                 y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
204                 mt[kk] = mt[kk+M] ^ (y >>> 1) ^ mag01[y & 0x1];
205                 }
206             for (; kk < N-1; kk++)
207                 {
208                 y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
209                 mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ mag01[y & 0x1];
210                 }
211             y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
212             mt[N-1] = mt[M-1] ^ (y >>> 1) ^ mag01[y & 0x1];
213
214             mti = 0;
215             }
216   
217         y = mt[mti++];
218         y ^= y >>> 11; // TEMPERING_SHIFT_U(y)
219 y ^= (y << 7) & TEMPERING_MASK_B; // TEMPERING_SHIFT_S(y)
220 y ^= (y << 15) & TEMPERING_MASK_C; // TEMPERING_SHIFT_T(y)
221 y ^= (y >>> 18); // TEMPERING_SHIFT_L(y)
222
223         return y >>> (32 - bits); // hope that's right!
224 }
225     
226     
227     /* If you've got a truly old version of Java, you can omit these
228        two next methods. */
229
230     private synchronized void writeObject(ObjectOutputStream JavaDoc out)
231             throws IOException JavaDoc
232         {
233         // just so we're synchronized.
234 out.defaultWriteObject();
235         }
236
237     private synchronized void readObject (ObjectInputStream JavaDoc in)
238             throws IOException JavaDoc, ClassNotFoundException JavaDoc
239         {
240         // just so we're synchronized.
241 in.defaultReadObject();
242         }
243
244     /** This method is missing from jdk 1.0.x and below. JDK 1.1
245         includes this for us, but what the heck.*/
246     public boolean nextBoolean() {return next(1) != 0;}
247
248     /** This method is missing from JDK 1.1 and below. JDK 1.2
249         includes this for us, but what the heck. */
250
251     public int nextInt(int n) {
252         if (n<=0)
253             throw new IllegalArgumentException JavaDoc("n must be positive");
254
255         if ((n & -n) == n) // i.e., n is a power of 2
256 return (int)((n * (long)next(31)) >> 31);
257
258         int bits, val;
259         do {
260             bits = next(31);
261             val = bits % n;
262         } while(bits - val + (n-1) < 0);
263         return val;
264     }
265
266     /** A bug fix for versions of JDK 1.1 and below. JDK 1.2 fixes
267         this for us, but what the heck. */
268     public double nextDouble()
269         {
270         return (((long)next(26) << 27) + next(27))
271             / (double)(1L << 53);
272         }
273
274     /** A bug fix for versions of JDK 1.1 and below. JDK 1.2 fixes
275         this for us, but what the heck. */
276
277
278     public float nextFloat()
279         {
280         return next(24) / ((float)(1 << 24));
281         }
282
283     /** A bug fix for all versions of the JDK. The JDK appears to
284         use all four bytes in an integer as independent byte values!
285         Totally wrong. I've submitted a bug report. */
286
287     public void nextBytes(byte[] bytes)
288         {
289         for (int x=0;x<bytes.length;x++)
290             bytes[x] = (byte)next(8);
291         }
292
293     /** For completeness' sake, though it's not in java.util.Random. */
294     
295     public char nextChar()
296         {
297         // chars are 16-bit UniCode values
298 return (char)(next(16));
299         }
300
301     /** For completeness' sake, though it's not in java.util.Random. */
302     
303     public short nextShort()
304
305         {
306         return (short)(next(16));
307         }
308
309     /** For completeness' sake, though it's not in java.util.Random. */
310
311     public byte nextByte()
312         {
313         return (byte)(next(8));
314         }
315
316
317
318     /**
319      * Tests the code.
320      */
321     public static void main(String JavaDoc args[])
322         {
323         int j;
324
325         MersenneTwister r;
326
327         // UNCOMMENT THIS TO TEST FOR PROPER GAUSSIAN STATE INITIALIZATION
328
329         /*
330         System.out.println("If the gaussian state is properly initialized when setSeed() is called,\nthen #1 != #2, but #1 == #3\nIt's known that java 1.0.2 doesn't do gaussian initialization right,\nso setSeed() may result in one last gaussian drawn from the *previous* seed.");
331         r = new MersenneTwister(1);
332         r.nextGaussian(); // loads the later gaussian into the state
333         System.out.println("1: " + r.nextGaussian());
334         r = new MersenneTwister(1);
335         r.nextGaussian(); // loads the later gaussian into the state
336         r.setSeed(1); // should reset the gaussian state
337         System.out.println("2: " + r.nextGaussian());
338         System.out.println("3: " + r.nextGaussian());
339         */
340
341         
342         // UNCOMMENT THIS TO TEST FOR CORRECTNESS
343 // COMPARE WITH http://www.math.keio.ac.jp/~nisimura/random/int/mt19937int.out
344
345         /*
346         r = new MersenneTwister(4357);
347         System.out.println("Output of MersenneTwister.java");
348         for (j=0;j<1000;j++)
349             {
350             // first, convert the int from signed to "unsigned"
351             long l = (long)r.nextInt();
352             if (l < 0 ) l += 4294967296L; // max int value
353             String s = String.valueOf(l);
354             while(s.length() < 10) s = " " + s; // buffer
355             System.out.print(s + " ");
356             if (j%8==7) System.out.println();
357             }
358         */
359
360
361         // UNCOMMENT THIS TO TEST FOR SPEED
362
363         /*
364         r = new MersenneTwister();
365         System.out.println("\nTime to test grabbing 10000000 ints");
366         long ms = System.currentTimeMillis();
367         int xx=0;
368         for (j = 0; j < 10000000; j++)
369             xx += r.nextInt();
370         System.out.println("Mersenne Twister: " + (System.currentTimeMillis()-ms + " Ignore this: " + xx));
371
372         Random rr = new Random(1);
373         xx = 0;
374         ms = System.currentTimeMillis();
375         for (j = 0; j < 10000000; j++)
376             xx += rr.nextInt();
377         System.out.println("java.util.Random: " + (System.currentTimeMillis()-ms + " Ignore this: " + xx));
378         */
379
380         
381         // UNCOMMENT THIS TO DO TEST DIFFERENT TYPE OUTPUTS
382 // THIS CAN BE USED TO COMPARE THE DIFFERENCE BETWEEN
383 // MersenneTwisterFast.java AND MersenneTwister.java
384
385         /*
386         System.out.println("\nGrab the first 1000 booleans");
387         r = new MersenneTwister();
388         for (j = 0; j < 1000; j++)
389             {
390             System.out.print(r.nextBoolean() + " ");
391             if (j%8==7) System.out.println();
392             }
393         if (!(j%8==7)) System.out.println();
394
395         byte[] bytes = new byte[1000];
396         System.out.println("\nGrab the first 1000 bytes using nextBytes");
397         r = new MersenneTwister();
398         r.nextBytes(bytes);
399         for (j = 0; j < 1000; j++)
400             {
401             System.out.print(bytes[j] + " ");
402             if (j%16==15) System.out.println();
403             }
404         if (!(j%16==15)) System.out.println();
405         
406         byte b;
407         System.out.println("\nGrab the first 1000 bytes -- must be same as nextBytes");
408         r = new MersenneTwister();
409         for (j = 0; j < 1000; j++)
410             {
411             System.out.print((b = r.nextByte()) + " ");
412             if (b!=bytes[j]) System.out.print("BAD ");
413             if (j%16==15) System.out.println();
414             }
415         if (!(j%16==15)) System.out.println();
416
417         System.out.println("\nGrab the first 1000 shorts");
418         r = new MersenneTwister();
419         for (j = 0; j < 1000; j++)
420             {
421             System.out.print(r.nextShort() + " ");
422             if (j%8==7) System.out.println();
423             }
424         if (!(j%8==7)) System.out.println();
425
426
427         System.out.println("\nGrab the first 1000 ints");
428         r = new MersenneTwister();
429         for (j = 0; j < 1000; j++)
430             {
431             System.out.print(r.nextInt() + " ");
432             if (j%4==3) System.out.println();
433             }
434         if (!(j%4==3)) System.out.println();
435
436         System.out.println("\nGrab the first 1000 ints of different sizes");
437         r = new MersenneTwister();
438         for (j = 0; j < 1000; j++)
439             {
440             System.out.print(r.nextInt(j+1) + " ");
441             if (j%4==3) System.out.println();
442             }
443         if (!(j%4==3)) System.out.println();
444
445         System.out.println("\nGrab the first 1000 longs");
446         r = new MersenneTwister();
447         for (j = 0; j < 1000; j++)
448             {
449             System.out.print(r.nextLong() + " ");
450             if (j%3==2) System.out.println();
451             }
452         if (!(j%3==2)) System.out.println();
453
454         System.out.println("\nGrab the first 1000 floats");
455         r = new MersenneTwister();
456         for (j = 0; j < 1000; j++)
457             {
458             System.out.print(r.nextFloat() + " ");
459             if (j%4==3) System.out.println();
460             }
461         if (!(j%4==3)) System.out.println();
462
463         System.out.println("\nGrab the first 1000 doubles");
464         r = new MersenneTwister();
465         for (j = 0; j < 1000; j++)
466             {
467             System.out.print(r.nextDouble() + " ");
468             if (j%3==2) System.out.println();
469             }
470         if (!(j%3==2)) System.out.println();
471
472         System.out.println("\nGrab the first 1000 gaussian doubles");
473         r = new MersenneTwister();
474         for (j = 0; j < 1000; j++)
475             {
476             System.out.print(r.nextGaussian() + " ");
477             if (j%3==2) System.out.println();
478             }
479         if (!(j%3==2)) System.out.println();
480         */
481         }
482     
483     }
484
Popular Tags