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.equals(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 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}