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 package org.apache.commons.rng.core.source32; 18 19 import org.apache.commons.rng.core.util.NumberFactory; 20 21 /** 22 * This abstract class is a base for algorithms from the Permuted Congruential Generator (PCG) 23 * family that use an internal 64-bit Linear Congruential Generator (LCG) and output 32-bits 24 * per cycle. 25 * 26 * <h2>Note: PCG generators may exhibit massive stream correlation</h2> 27 * 28 * <p>Although the seed size is 128 bits, only the first 64 are effective: in effect, 29 * two seeds that only differ by the last 64 bits may produce highly correlated sequences. 30 * 31 * <p>Due to the use of an underlying linear congruential generator (LCG) alterations 32 * to the 128 bit seed have the following effect: the first 64-bits alter the 33 * generator state; the second 64 bits, with the exception of the most significant bit, 34 * which is discarded, choose between one of two alternative LCGs 35 * where the output of the chosen LCG is the same sequence except for an additive 36 * constant determined by the seed bits. The result is that seeds that differ 37 * only in the last 64-bits will have a 50% chance of producing highly correlated 38 * output sequences. 39 40 * <p>Consider using the fixed increment variant where the 64-bit seed sets the 41 * generator state. 42 * 43 * <p>For further information see: 44 * <ul> 45 * <li> 46 * <blockquote> 47 * Durst, M.J. (1989) <i>Using Linear Congruential Generators For Parallel Random Number Generation. 48 * Section 3.1: Different additive constants in a maximum potency congruential generator</i>. 49 * 1989 Winter Simulation Conference Proceedings, Washington, DC, USA, 1989, pp. 462-466. 50 * </blockquote> 51 * </li> 52 * </ul> 53 * 54 * @see <a href="http://www.pcg-random.org/"> 55 * PCG, A Family of Better Random Number Generators</a> 56 * @see <a href="https://ieeexplore.ieee.org/document/718715">Durst, M.J. (1989) 57 * Using Linear Congruential Generators For Parallel Random Number Generation</a> 58 * @see <a href="https://issues.apache.org/jira/browse/RNG-123"> 59 * PCG generators may exhibit massive stream correlation</a> 60 * @since 1.3 61 */ 62 abstract class AbstractPcg6432 extends IntProvider { 63 /** Size of the seed array. */ 64 private static final int SEED_SIZE = 2; 65 /** The default increment. */ 66 private static final long DEFAULT_INCREMENT = 1442695040888963407L; 67 68 /** The state of the LCG. */ 69 private long state; 70 71 /** The increment of the LCG. */ 72 private long increment; 73 74 /** 75 * Creates a new instance using a default increment. 76 * 77 * @param seed Initial state. 78 * @since 1.4 79 */ 80 AbstractPcg6432(Long seed) { 81 increment = DEFAULT_INCREMENT; 82 state = bump(seed + this.increment); 83 } 84 85 /** 86 * Creates a new instance. 87 * 88 * @param seed Initial seed. 89 * If the length is larger than 2, only the first 2 elements will 90 * be used; if smaller, the remaining elements will be automatically set. 91 * 92 * <p>The 1st element is used to set the LCG state. The 2nd element is used 93 * to set the LCG increment; the most significant bit 94 * is discarded by left shift and the increment is set to odd.</p> 95 */ 96 AbstractPcg6432(long[] seed) { 97 if (seed.length < SEED_SIZE) { 98 final long[] tmp = new long[SEED_SIZE]; 99 fillState(tmp, seed); 100 setSeedInternal(tmp); 101 } else { 102 setSeedInternal(seed); 103 } 104 } 105 106 /** 107 * Seeds the RNG. 108 * 109 * @param seed Seed. 110 */ 111 private void setSeedInternal(long[] seed) { 112 // Ensure the increment is odd to provide a maximal period LCG. 113 this.increment = (seed[1] << 1) | 1; 114 this.state = bump(seed[0] + this.increment); 115 } 116 117 /** 118 * Provides the next state of the LCG. 119 * 120 * @param input Current state. 121 * @return next state 122 */ 123 private long bump(long input) { 124 return input * 6364136223846793005L + increment; 125 } 126 127 /** {@inheritDoc} */ 128 @Override 129 public int next() { 130 final long x = state; 131 state = bump(state); 132 return transform(x); 133 } 134 135 /** 136 * Transform the 64-bit state of the generator to a 32-bit output. 137 * The transformation function shall vary with respect to different generators. 138 * 139 * @param x State. 140 * @return the output 141 */ 142 protected abstract int transform(long x); 143 144 /** {@inheritDoc} */ 145 @Override 146 protected byte[] getStateInternal() { 147 // The increment is divided by 2 before saving. 148 // This transform is used in the reference PCG code; it prevents restoring from 149 // a byte state a non-odd increment that results in a sub-maximal period generator. 150 return composeStateInternal(NumberFactory.makeByteArray( 151 new long[] {state, increment >>> 1}), 152 super.getStateInternal()); 153 } 154 155 /** {@inheritDoc} */ 156 @Override 157 protected void setStateInternal(byte[] s) { 158 final byte[][] c = splitStateInternal(s, SEED_SIZE * 8); 159 final long[] tempseed = NumberFactory.makeLongArray(c[0]); 160 state = tempseed[0]; 161 // Reverse the transform performed during getState to make the increment odd again. 162 increment = tempseed[1] << 1 | 1; 163 super.setStateInternal(c[1]); 164 } 165 }