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 018package org.apache.commons.rng.core.source64; 019 020import java.util.List; 021import java.util.ArrayList; 022import org.apache.commons.rng.core.util.NumberFactory; 023 024/** 025 * Random number generator designed by Mark D. Overton. 026 * 027 * <p>It is one of the many generators described by the author in the following article series:</p> 028 * <ul> 029 * <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477">Part one</a></li> 030 * <li><a href="http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484">Part two</a></li> 031 * </ul> 032 * 033 * @since 1.0 034 */ 035public class TwoCmres extends LongProvider { 036 /** Error message. */ 037 private static final String INTERNAL_ERROR_MSG = "Internal error: Please file a bug report"; 038 /** A small positive integer. */ 039 private static final byte SEED_GUARD = 9; 040 /** Factory of instances of this class. Singleton. */ 041 private static final Cmres.Factory FACTORY = new Cmres.Factory(); 042 /** First subcycle generator. */ 043 private final Cmres x; 044 /** Second subcycle generator. */ 045 private final Cmres y; 046 /** State of first subcycle generator. */ 047 private long xx; 048 /** State of second subcycle generator. */ 049 private long yy; 050 051 /** 052 * Creates a new instance. 053 * 054 * @param seed Initial seed. 055 * @param x First subcycle generator. 056 * @param y Second subcycle generator. 057 * @throws IllegalArgumentException if {@code x == y}. 058 */ 059 private TwoCmres(int seed, 060 Cmres x, 061 Cmres y) { 062 if (x == y) { 063 throw new IllegalArgumentException("Subcycle generators must be different"); 064 } 065 this.x = x; 066 this.y = y; 067 setSeedInternal(seed); 068 } 069 070 /** 071 * Creates a new instance. 072 * 073 * @param seed Seed. 074 */ 075 public TwoCmres(Integer seed) { 076 this(seed, 0, 1); 077 } 078 079 /** 080 * Creates a new instance. 081 * 082 * @param seed Seed. 083 * @param i Table entry for first subcycle generator. 084 * @param j Table entry for second subcycle generator. 085 * @throws IllegalArgumentException if {@code i == j}. 086 * @throws IndexOutOfBoundsException if {@code i < 0} or 087 * {@code i >= numberOfSubcycleGenerators()}. 088 * @throws IndexOutOfBoundsException if {@code j < 0} or 089 * {@code j >= numberOfSubcycleGenerators()}. 090 */ 091 public TwoCmres(Integer seed, 092 int i, 093 int j) { 094 this(seed, FACTORY.get(i), FACTORY.get(j)); 095 } 096 097 /** {@inheritDoc} */ 098 @Override 099 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 NumberFactory.makeByteArray(new long[] { xx, yy }); 123 } 124 125 /** {@inheritDoc} */ 126 @Override 127 protected void setStateInternal(byte[] s) { 128 checkStateSize(s, 16); 129 130 final long[] state = NumberFactory.makeLongArray(s); 131 xx = state[0]; 132 yy = state[1]; 133 } 134 135 /** 136 * @param seed Seed. 137 */ 138 private void setSeedInternal(int seed) { 139 // The seeding procedure consists in going away from some 140 // point known to be in the cycle. 141 // The total number of calls to the "transform" method will 142 // not exceed about 130,000 (which is negligible as seeding 143 // will not occur more than once in normal usage). 144 145 // Make two positive 16-bits integers. 146 final long s = NumberFactory.makeLong(0, seed); // s >= 0 147 final int xMax = (int) ((s & 0xffff) + SEED_GUARD); 148 final int yMax = (int) ((s >> 16) + SEED_GUARD); 149 150 if (xMax < 0 || 151 yMax < 0) { 152 throw new IllegalStateException(INTERNAL_ERROR_MSG); 153 } 154 155 xx = x.getStart(); 156 for (int i = xMax; i > 0; i--) { 157 xx = x.transform(xx); 158 } 159 160 yy = y.getStart(); 161 for (int i = yMax; i > 0; i--) { 162 yy = y.transform(yy); 163 } 164 } 165 166 /** 167 * Subcycle generator. 168 * Class is immutable. 169 */ 170 static class Cmres { 171 /** Separator. */ 172 private static final String SEP = ", "; 173 /** Hexadecimal format. */ 174 private static final String HEX_FORMAT = "0x%016xL"; 175 /** Cycle start. */ 176 private final int start; 177 /** Multiplier. */ 178 private final long multiply; 179 /** Rotation. */ 180 private final int rotate; 181 182 /** 183 * @param multiply Multiplier. 184 * @param rotate Positive number. Must be in {@code [0, 64]}. 185 * @param start Cycle start. 186 */ 187 Cmres(long multiply, 188 int rotate, 189 int start) { 190 this.multiply = multiply; 191 this.rotate = rotate; 192 this.start = start; 193 } 194 195 /** {@inheritDoc} */ 196 @Override 197 public String toString() { 198 final String m = String.format((java.util.Locale) null, HEX_FORMAT, multiply); 199 return "Cmres: [" + m + SEP + rotate + SEP + start + "]"; 200 } 201 202 /** 203 * @return the multiplier. 204 */ 205 public long getMultiply() { 206 return multiply; 207 } 208 209 /** 210 * @return the cycle start. 211 */ 212 public int getStart() { 213 return start; 214 } 215 216 /** 217 * @param state Current state. 218 * @return the new state. 219 */ 220 long transform(long state) { 221 long s = state; 222 s *= multiply; 223 s = rotl(s); 224 s -= state; 225 return s; 226 } 227 228 /** 229 * @param state State. 230 * @return the rotated state. 231 */ 232 private long rotl(long state) { 233 return (state << rotate) | (state >>> (64 - rotate)); 234 } 235 236 /** Factory. */ 237 static class Factory { 238 /** List of good "Cmres" subcycle generators. */ 239 private static final List<Cmres> TABLE = new ArrayList<Cmres>(); 240 241 /** 242 * Populates the table. 243 * It lists parameters known to be good (provided in 244 * the article referred to above). 245 * To maintain compatibility, new entries must be added 246 * only at the end of the table. 247 */ 248 static { 249 add(0xedce446814d3b3d9L, 33, 0x13b572e7); 250 add(0xc5b3cf786c806df7L, 33, 0x13c8e18a); 251 add(0xdd91bbb8ab9e0e65L, 31, 0x06dd03a6); 252 add(0x7b69342c0790221dL, 31, 0x1646bb8b); 253 add(0x0c72c0d18614c32bL, 33, 0x06014a3d); 254 add(0xd8d98c13bebe26c9L, 33, 0x014e8475); 255 add(0xcb039dc328bbc40fL, 31, 0x008684bd); 256 add(0x858c5ef3c021ed2fL, 32, 0x0dc8d622); 257 add(0x4c8be96bfc23b127L, 33, 0x0b6b20cc); 258 add(0x11eab77f808cf641L, 32, 0x06534421); 259 add(0xbc9bd78810fd28fdL, 31, 0x1d9ba40d); 260 add(0x0f1505c780688cb5L, 33, 0x0b7b7b67); 261 add(0xadc174babc2053afL, 31, 0x267f4197); 262 add(0x900b6b82b31686d9L, 31, 0x023c6985); 263 // Add new entries here. 264 } 265 266 /** 267 * @return the number of subcycle generators. 268 */ 269 int numberOfSubcycleGenerators() { 270 return TABLE.size(); 271 } 272 273 /** 274 * @param index Index into the list of available generators. 275 * @return the subcycle generator entry at index {@code index}. 276 */ 277 Cmres get(int index) { 278 if (index < 0 || 279 index >= TABLE.size()) { 280 throw new IndexOutOfBoundsException("Out of interval [0, " + 281 (TABLE.size() - 1) + "]"); 282 } 283 284 return TABLE.get(index); 285 } 286 287 /** 288 * Adds an entry to the {@link Factory#TABLE}. 289 * 290 * @param multiply Multiplier. 291 * @param rotate Rotate. 292 * @param start Cycle start. 293 */ 294 private static void add(long multiply, 295 int rotate, 296 int start) { 297 // Sanity check: if there are duplicates, the class initialization 298 // will fail (and the JVM will report "NoClassDefFoundError"). 299 for (Cmres sg : TABLE) { 300 if (multiply == sg.getMultiply()) { 301 throw new IllegalStateException(INTERNAL_ERROR_MSG); 302 } 303 } 304 305 TABLE.add(new Cmres(multiply, rotate, start)); 306 } 307 } 308 } 309}