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.Arrays; 021 022import org.apache.commons.rng.JumpableUniformRandomProvider; 023import org.apache.commons.rng.UniformRandomProvider; 024import org.apache.commons.rng.core.util.NumberFactory; 025 026/** 027 * A fast RNG implementing the {@code XorShift1024*} algorithm. 028 * 029 * <p>Note: This has been superseded by {@link XorShift1024StarPhi}. The sequences emitted 030 * by both generators are correlated.</p> 031 * 032 * @see <a href="http://xorshift.di.unimi.it/xorshift1024star.c">Original source code</a> 033 * @see <a href="https://en.wikipedia.org/wiki/Xorshift">Xorshift (Wikipedia)</a> 034 * @since 1.0 035 */ 036public class XorShift1024Star extends LongProvider implements JumpableUniformRandomProvider { 037 /** Size of the state vector. */ 038 private static final int SEED_SIZE = 16; 039 /** The coefficients for the jump function. */ 040 private static final long[] JUMP_COEFFICIENTS = { 041 0x84242f96eca9c41dL, 0xa3c65b8776f96855L, 0x5b34a39f070b5837L, 0x4489affce4f31a1eL, 042 0x2ffeeb0a48316f40L, 0xdc2d9891fe68c022L, 0x3659132bb12fea70L, 0xaac17d8efa43cab8L, 043 0xc4cb815590989b13L, 0x5ee975283d71c93bL, 0x691548c86c1bd540L, 0x7910c41d10a1e6a5L, 044 0x0b5fc64563b3e2a8L, 0x047f7684e9fc949dL, 0xb99181f2d8f685caL, 0x284600e3f30e38c3L 045 }; 046 /** State. */ 047 private final long[] state = new long[SEED_SIZE]; 048 /** The multiplier for the XorShift1024 algorithm. */ 049 private final long multiplier; 050 /** Index in "state" array. */ 051 private int index; 052 053 /** 054 * Creates a new instance. 055 * 056 * @param seed Initial seed. 057 * If the length is larger than 16, only the first 16 elements will 058 * be used; if smaller, the remaining elements will be automatically 059 * set. A seed containing all zeros will create a non-functional generator. 060 */ 061 public XorShift1024Star(long[] seed) { 062 this(seed, 1181783497276652981L); 063 } 064 065 /** 066 * Creates a new instance. 067 * 068 * @param seed Initial seed. 069 * If the length is larger than 16, only the first 16 elements will 070 * be used; if smaller, the remaining elements will be automatically 071 * set. A seed containing all zeros will create a non-functional generator. 072 * @param multiplier The multiplier for the XorShift1024 algorithm. 073 * @since 1.3 074 */ 075 protected XorShift1024Star(long[] seed, long multiplier) { 076 setSeedInternal(seed); 077 this.multiplier = multiplier; 078 } 079 080 /** 081 * Creates a copy instance. 082 * 083 * @param source Source to copy. 084 * @since 1.3 085 */ 086 protected XorShift1024Star(XorShift1024Star source) { 087 super(source); 088 System.arraycopy(source.state, 0, state, 0, SEED_SIZE); 089 multiplier = source.multiplier; 090 index = source.index; 091 } 092 093 /** {@inheritDoc} */ 094 @Override 095 protected byte[] getStateInternal() { 096 final long[] s = Arrays.copyOf(state, SEED_SIZE + 1); 097 s[SEED_SIZE] = index; 098 099 return composeStateInternal(NumberFactory.makeByteArray(s), 100 super.getStateInternal()); 101 } 102 103 /** {@inheritDoc} */ 104 @Override 105 protected void setStateInternal(byte[] s) { 106 final byte[][] c = splitStateInternal(s, (SEED_SIZE + 1) * 8); 107 108 final long[] tmp = NumberFactory.makeLongArray(c[0]); 109 System.arraycopy(tmp, 0, state, 0, SEED_SIZE); 110 index = (int) tmp[SEED_SIZE]; 111 112 super.setStateInternal(c[1]); 113 } 114 115 /** 116 * Seeds the RNG. 117 * 118 * @param seed Seed. 119 */ 120 private void setSeedInternal(long[] seed) { 121 // Reset the whole state of this RNG (i.e. "state" and "index"). 122 // Filling procedure is not part of the reference code. 123 fillState(state, seed); 124 index = 0; 125 } 126 127 /** {@inheritDoc} */ 128 @Override 129 public long next() { 130 final long s0 = state[index]; 131 index = (index + 1) & 15; 132 long s1 = state[index]; 133 s1 ^= s1 << 31; // a 134 state[index] = s1 ^ s0 ^ (s1 >>> 11) ^ (s0 >>> 30); // b,c 135 return state[index] * multiplier; 136 } 137 138 /** 139 * {@inheritDoc} 140 * 141 * <p>The jump size is the equivalent of 2<sup>512</sup> 142 * calls to {@link UniformRandomProvider#nextLong() nextLong()}. It can provide 143 * up to 2<sup>512</sup> non-overlapping subsequences.</p> 144 * 145 * @since 1.3 146 */ 147 @Override 148 public UniformRandomProvider jump() { 149 final UniformRandomProvider copy = copy(); 150 performJump(); 151 return copy; 152 } 153 154 /** 155 * Create a copy. 156 * 157 * @return the copy 158 * @since 1.3 159 */ 160 protected XorShift1024Star copy() { 161 // This exists to ensure the jump function returns 162 // the correct class type. It should not be public. 163 return new XorShift1024Star(this); 164 } 165 166 /** 167 * Perform the jump to advance the generator state. Resets the cached state of the generator. 168 */ 169 private void performJump() { 170 final long[] newState = new long[SEED_SIZE]; 171 for (final long jc : JUMP_COEFFICIENTS) { 172 for (int b = 0; b < 64; b++) { 173 if ((jc & (1L << b)) != 0) { 174 for (int i = 0; i < SEED_SIZE; i++) { 175 newState[i] ^= state[(i + index) & 15]; 176 } 177 } 178 next(); 179 } 180 } 181 for (int j = 0; j < 16; j++) { 182 state[(j + index) & 15] = newState[j]; 183 } 184 resetCachedState(); 185 } 186}