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  
18  package org.apache.commons.rng.core.source64;
19  
20  import java.util.List;
21  import java.util.ArrayList;
22  import org.apache.commons.rng.core.util.NumberFactory;
23  
24  /**
25   * Random number generator designed by Mark D. Overton.
26   *
27   * <p>It is one of the many generators described by the author in the following article series:</p>
28   *  <ul>
29   *   <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477">Part one</a></li>
30   *   <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484">Part two</a></li>
31   *  </ul>
32   *
33   * @since 1.0
34   */
35  public class TwoCmres extends LongProvider {
36      /** Error message. */
37      private static final String INTERNAL_ERROR_MSG = "Internal error: Please file a bug report";
38      /** A small positive integer. */
39      private static final byte SEED_GUARD = 9;
40      /** Factory of instances of this class. Singleton. */
41      private static final Cmres.Factory FACTORY = new Cmres.Factory();
42      /** First subcycle generator. */
43      private final Cmres x;
44      /** Second subcycle generator. */
45      private final Cmres y;
46      /** State of first subcycle generator. */
47      private long xx;
48      /** State of second subcycle generator. */
49      private long yy;
50  
51      /**
52       * Creates a new instance.
53       *
54       * @param seed Initial seed.
55       * @param x First subcycle generator.
56       * @param y Second subcycle generator.
57       * @throws IllegalArgumentException if {@code x == y}.
58       */
59      private TwoCmres(int seed,
60                       Cmres x,
61                       Cmres y) {
62          if (x.equals(y)) {
63              throw new IllegalArgumentException("Subcycle generators must be different");
64          }
65          this.x = x;
66          this.y = y;
67          setSeedInternal(seed);
68      }
69  
70      /**
71       * Creates a new instance.
72       *
73       * @param seed Seed.
74       */
75      public TwoCmres(Integer seed) {
76          this(seed, 0, 1);
77      }
78  
79      /**
80       * Creates a new instance.
81       *
82       * @param seed Seed.
83       * @param i Table entry for first subcycle generator.
84       * @param j Table entry for second subcycle generator.
85       * @throws IllegalArgumentException if {@code i == j}.
86       * @throws IndexOutOfBoundsException if {@code i < 0} or
87       * {@code i >= numberOfSubcycleGenerators()}.
88       * @throws IndexOutOfBoundsException if {@code j < 0} or
89       * {@code j >= numberOfSubcycleGenerators()}.
90       */
91      public TwoCmres(Integer seed,
92                      int i,
93                      int j) {
94          this(seed, FACTORY.get(i), FACTORY.get(j));
95      }
96  
97      /** {@inheritDoc} */
98      @Override
99      public long next() {
100         xx = x.transform(xx);
101         yy = y.transform(yy);
102 
103         return xx + yy;
104     }
105 
106     /** {@inheritDoc} */
107     @Override
108     public String toString() {
109         return super.toString() + " (" + x + " + " + y + ")";
110     }
111 
112     /**
113      * @return the number of subcycle generators.
114      */
115     public static int numberOfSubcycleGenerators() {
116         return FACTORY.numberOfSubcycleGenerators();
117     }
118 
119     /** {@inheritDoc} */
120     @Override
121     protected byte[] getStateInternal() {
122         return composeStateInternal(NumberFactory.makeByteArray(new long[] {xx, yy}),
123                                     super.getStateInternal());
124     }
125 
126     /** {@inheritDoc} */
127     @Override
128     protected void setStateInternal(byte[] s) {
129         final byte[][] c = splitStateInternal(s, 16);
130 
131         final long[] state = NumberFactory.makeLongArray(c[0]);
132         xx = state[0];
133         yy = state[1];
134 
135         super.setStateInternal(c[1]);
136     }
137 
138     /**
139      * @param seed Seed.
140      */
141     private void setSeedInternal(int seed) {
142         // The seeding procedure consists in going away from some
143         // point known to be in the cycle.
144         // The total number of calls to the "transform" method will
145         // not exceed about 130,000 (which is negligible as seeding
146         // will not occur more than once in normal usage).
147 
148         // Make two positive 16-bits integers from the 32-bit seed.
149         // Add the small positive seed guard. The result will never be negative.
150         final int xMax = (seed & 0xffff) + (SEED_GUARD & 0xff);
151         final int yMax = (seed >>> 16)   + (SEED_GUARD & 0xff);
152 
153         xx = x.getStart();
154         for (int i = xMax; i > 0; i--) {
155             xx = x.transform(xx);
156         }
157 
158         yy = y.getStart();
159         for (int i = yMax; i > 0; i--) {
160             yy = y.transform(yy);
161         }
162     }
163 
164     /**
165      * Subcycle generator.
166      * Class is immutable.
167      */
168     static class Cmres {
169         /** Separator. */
170         private static final String SEP = ", ";
171         /** Hexadecimal format. */
172         private static final String HEX_FORMAT = "0x%016xL";
173         /** Cycle start. */
174         private final int start;
175         /** Multiplier. */
176         private final long multiply;
177         /** Rotation. */
178         private final int rotate;
179 
180         /**
181          * @param multiply Multiplier.
182          * @param rotate Positive number. Must be in {@code [0, 64]}.
183          * @param start Cycle start.
184          */
185         Cmres(long multiply,
186               int rotate,
187               int start) {
188             this.multiply = multiply;
189             this.rotate = rotate;
190             this.start = start;
191         }
192 
193         /** {@inheritDoc} */
194         @Override
195         public String toString() {
196             final String m = String.format((java.util.Locale) null, HEX_FORMAT, multiply);
197             return "Cmres: [" + m + SEP + rotate + SEP + start + "]";
198         }
199 
200         /**
201          * @return the multiplier.
202          */
203         public long getMultiply() {
204             return multiply;
205         }
206 
207         /**
208          * @return the cycle start.
209          */
210         public int getStart() {
211             return start;
212         }
213 
214         /**
215          * @param state Current state.
216          * @return the new state.
217          */
218         long transform(long state) {
219             long s = state;
220             s *= multiply;
221             s = Long.rotateLeft(s, rotate);
222             s -= state;
223             return s;
224         }
225 
226         /** Factory. */
227         static class Factory {
228             /** List of good "Cmres" subcycle generators. */
229             private static final List<Cmres> TABLE = new ArrayList<>();
230 
231             //
232             // Populates the table.
233             // It lists parameters known to be good (provided in
234             // the article referred to above).
235             // To maintain compatibility, new entries must be added
236             // only at the end of the table.
237             //
238             static {
239                 add(0xedce446814d3b3d9L, 33, 0x13b572e7);
240                 add(0xc5b3cf786c806df7L, 33, 0x13c8e18a);
241                 add(0xdd91bbb8ab9e0e65L, 31, 0x06dd03a6);
242                 add(0x7b69342c0790221dL, 31, 0x1646bb8b);
243                 add(0x0c72c0d18614c32bL, 33, 0x06014a3d);
244                 add(0xd8d98c13bebe26c9L, 33, 0x014e8475);
245                 add(0xcb039dc328bbc40fL, 31, 0x008684bd);
246                 add(0x858c5ef3c021ed2fL, 32, 0x0dc8d622);
247                 add(0x4c8be96bfc23b127L, 33, 0x0b6b20cc);
248                 add(0x11eab77f808cf641L, 32, 0x06534421);
249                 add(0xbc9bd78810fd28fdL, 31, 0x1d9ba40d);
250                 add(0x0f1505c780688cb5L, 33, 0x0b7b7b67);
251                 add(0xadc174babc2053afL, 31, 0x267f4197);
252                 add(0x900b6b82b31686d9L, 31, 0x023c6985);
253                 // Add new entries here.
254             }
255 
256             /**
257              * @return the number of subcycle generators.
258              */
259             int numberOfSubcycleGenerators() {
260                 return TABLE.size();
261             }
262 
263             /**
264              * @param index Index into the list of available generators.
265              * @return the subcycle generator entry at index {@code index}.
266              */
267             Cmres get(int index) {
268                 if (index < 0 ||
269                     index >= TABLE.size()) {
270                     throw new IndexOutOfBoundsException("Out of interval [0, " +
271                                                         (TABLE.size() - 1) + "]");
272                 }
273 
274                 return TABLE.get(index);
275             }
276 
277             /**
278              * Adds an entry to the {@link Factory#TABLE}.
279              *
280              * @param multiply Multiplier.
281              * @param rotate Rotate.
282              * @param start Cycle start.
283              */
284             private static void add(long multiply,
285                                     int rotate,
286                                     int start) {
287                 // Validity check: if there are duplicates, the class initialization
288                 // will fail (and the JVM will report "NoClassDefFoundError").
289                 checkUnique(TABLE, multiply);
290 
291                 TABLE.add(new Cmres(multiply, rotate, start));
292             }
293 
294             /**
295              * Check the multiply parameter is unique (not contained in any entry in the provided
296              * table).
297              *
298              * @param table the table
299              * @param multiply the multiply parameter
300              */
301             static void checkUnique(List<Cmres> table, long multiply) {
302                 for (final Cmres sg : table) {
303                     if (multiply == sg.getMultiply()) {
304                         throw new IllegalStateException(INTERNAL_ERROR_MSG);
305                     }
306                 }
307             }
308         }
309     }
310 }