http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/ProviderBuilder.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/ProviderBuilder.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/ProviderBuilder.java new file mode 100644 index 0000000..47e6b6e --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/ProviderBuilder.java @@ -0,0 +1,381 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal; + +import java.util.Arrays; +import java.util.List; +import java.util.ArrayList; +import java.util.Map; +import java.util.HashMap; +import java.lang.reflect.Constructor; +import java.lang.reflect.InvocationTargetException; + +import org.apache.commons.rng.UniformRandomProvider; +import org.apache.commons.rng.RestorableUniformRandomProvider; +import org.apache.commons.rng.internal.util.SeedFactory; +import org.apache.commons.rng.internal.util.NoOpConverter; +import org.apache.commons.rng.internal.util.Int2Long; +import org.apache.commons.rng.internal.util.Long2Int; +import org.apache.commons.rng.internal.util.Long2IntArray; +import org.apache.commons.rng.internal.util.Long2LongArray; +import org.apache.commons.rng.internal.util.IntArray2LongArray; +import org.apache.commons.rng.internal.util.LongArray2IntArray; +import org.apache.commons.rng.internal.util.LongArray2Long; +import org.apache.commons.rng.internal.util.IntArray2Int; +import org.apache.commons.rng.internal.util.ByteArray2IntArray; +import org.apache.commons.rng.internal.util.ByteArray2LongArray; +import org.apache.commons.rng.internal.util.SeedConverter; +import org.apache.commons.rng.internal.util.SeedConverterComposer; +import org.apache.commons.rng.internal.source32.JDKRandom; +import org.apache.commons.rng.internal.source32.Well512a; +import org.apache.commons.rng.internal.source32.Well1024a; +import org.apache.commons.rng.internal.source32.Well19937a; +import org.apache.commons.rng.internal.source32.Well19937c; +import org.apache.commons.rng.internal.source32.Well44497a; +import org.apache.commons.rng.internal.source32.Well44497b; +import org.apache.commons.rng.internal.source32.ISAACRandom; +import org.apache.commons.rng.internal.source32.MersenneTwister; +import org.apache.commons.rng.internal.source32.MultiplyWithCarry256; +import org.apache.commons.rng.internal.source32.KISSRandom; +import org.apache.commons.rng.internal.source64.SplitMix64; +import org.apache.commons.rng.internal.source64.XorShift1024Star; +import org.apache.commons.rng.internal.source64.TwoCmres; +import org.apache.commons.rng.internal.source64.MersenneTwister64; + +/** + * RNG builder. + * <p> + * It uses reflection to find the factory method of the RNG implementation, + * and performs seed type conversions. + * </p> + */ +public class ProviderBuilder { + /** Error message. */ + private static final String INTERNAL_ERROR_MSG = "Internal error: Please file a bug report"; + /** Length of the seed array (for random seed). */ + private static final int RANDOM_SEED_ARRAY_SIZE = 128; + /** Seed converter. */ + private static final Long2Int LONG_TO_INT = new Long2Int(); + /** Seed converter. */ + private static final Int2Long INT_TO_LONG = new Int2Long(); + /** Seed converter. */ + private static final Long2IntArray LONG_TO_INT_ARRAY = new Long2IntArray(RANDOM_SEED_ARRAY_SIZE); + /** Seed converter. */ + private static final Long2LongArray LONG_TO_LONG_ARRAY = new Long2LongArray(RANDOM_SEED_ARRAY_SIZE); + /** Seed converter. */ + private static final LongArray2Long LONG_ARRAY_TO_LONG = new LongArray2Long(); + /** Seed converter. */ + private static final IntArray2Int INT_ARRAY_TO_INT = new IntArray2Int(); + /** Seed converter. */ + private static final LongArray2IntArray LONG_ARRAY_TO_INT_ARRAY = new LongArray2IntArray(); + /** Seed converter. */ + private static final IntArray2LongArray INT_ARRAY_TO_LONG_ARRAY = new IntArray2LongArray(); + /** Seed converter. */ + private static final ByteArray2IntArray BYTE_ARRAY_TO_INT_ARRAY = new ByteArray2IntArray(); + /** Seed converter. */ + private static final ByteArray2LongArray BYTE_ARRAY_TO_LONG_ARRAY = new ByteArray2LongArray(); + /** Map to convert "Integer" seeds. */ + private static final Map<Class<?>, SeedConverter<Integer,?>> CONV_INT = + new HashMap<Class<?>, SeedConverter<Integer,?>>(); + /** Map to convert "int[]" seeds. */ + private static final Map<Class<?>, SeedConverter<int[],?>> CONV_INT_ARRAY = + new HashMap<Class<?>, SeedConverter<int[],?>>(); + /** Map to convert "Long" seeds. */ + private static final Map<Class<?>, SeedConverter<Long,?>> CONV_LONG = + new HashMap<Class<?>, SeedConverter<Long,?>>(); + /** Map to convert "long[]" seeds. */ + private static final Map<Class<?>, SeedConverter<long[],?>> CONV_LONG_ARRAY = + new HashMap<Class<?>, SeedConverter<long[],?>>(); + /** Map to convert "byte[]" seeds. */ + private static final Map<Class<?>, SeedConverter<byte[],?>> CONV_BYTE_ARRAY = + new HashMap<Class<?>, SeedConverter<byte[],?>>(); + + static { + // Input seed type is "Long". + // Key is the implementation's "native" seed type. + CONV_LONG.put(Integer.class, LONG_TO_INT); + CONV_LONG.put(Long.class, new NoOpConverter<Long>()); + CONV_LONG.put(int[].class, LONG_TO_INT_ARRAY); + CONV_LONG.put(long[].class, LONG_TO_LONG_ARRAY); + + // Input seed type is "Integer". + // Key is the implementation's "native" seed type. + CONV_INT.put(Integer.class, new NoOpConverter<Integer>()); + CONV_INT.put(Long.class, INT_TO_LONG); + CONV_INT.put(int[].class, new SeedConverterComposer<Integer,Long,int[]>(INT_TO_LONG, LONG_TO_INT_ARRAY)); + CONV_INT.put(long[].class, new SeedConverterComposer<Integer,Long,long[]>(INT_TO_LONG, LONG_TO_LONG_ARRAY)); + + // Input seed type is "int[]". + // Key is the implementation's "native" seed type. + CONV_INT_ARRAY.put(Integer.class, INT_ARRAY_TO_INT); + CONV_INT_ARRAY.put(Long.class, new SeedConverterComposer<int[],Integer,Long>(INT_ARRAY_TO_INT, INT_TO_LONG)); + CONV_INT_ARRAY.put(int[].class, new NoOpConverter<int[]>()); + CONV_INT_ARRAY.put(long[].class, INT_ARRAY_TO_LONG_ARRAY); + + // Input seed type is "long[]". + // Key is the implementation's "native" seed type. + CONV_LONG_ARRAY.put(Integer.class, new SeedConverterComposer<long[],Long,Integer>(LONG_ARRAY_TO_LONG, LONG_TO_INT)); + CONV_LONG_ARRAY.put(Long.class, LONG_ARRAY_TO_LONG); + CONV_LONG_ARRAY.put(int[].class, LONG_ARRAY_TO_INT_ARRAY); + CONV_LONG_ARRAY.put(long[].class, new NoOpConverter<long[]>()); + + // Input seed type is "byte[]". + // Key is the implementation's "native" seed type. + CONV_BYTE_ARRAY.put(Integer.class, new SeedConverterComposer<byte[],int[],Integer>(BYTE_ARRAY_TO_INT_ARRAY, INT_ARRAY_TO_INT)); + CONV_BYTE_ARRAY.put(Long.class, new SeedConverterComposer<byte[],long[],Long>(BYTE_ARRAY_TO_LONG_ARRAY, LONG_ARRAY_TO_LONG)); + CONV_BYTE_ARRAY.put(int[].class, BYTE_ARRAY_TO_INT_ARRAY); + CONV_BYTE_ARRAY.put(long[].class, BYTE_ARRAY_TO_LONG_ARRAY); + } + + /** + * Class only contains static method. + */ + private ProviderBuilder() {} + + /** + * Creates a RNG instance. + * + * @param source RNG specification. + * @param seed Seed value. It can be {@code null} (in which case a + * random value will be used). + * @param args Additional arguments to the implementation's constructor. + * @return a new RNG instance. + * @throws UnsupportedOperationException if the seed type is invalid. + */ + public static RestorableUniformRandomProvider create(RandomSourceInternal source, + Object seed, + Object[] args) { + // Convert seed to native type. + final Object nativeSeed = createSeed(source, seed); + + // Build a single array with all the arguments to be passed + // (in the right order) to the constructor. + final List<Object> all = new ArrayList<Object>(); + all.add(nativeSeed); + if (args != null) { + all.addAll(Arrays.asList(args)); + } + + // Instantiate. + return create(createConstructor(source), all.toArray()); + } + + /** + * Creates a native seed from any of the supported seed types. + * + * @param source Source. + * @param seed Input seed. + * @return the native seed. + * @throw UnsupportedOperationException if the {@code seed} type is invalid. + */ + private static Object createSeed(RandomSourceInternal source, + Object seed) { + Object nativeSeed = null; + + if (seed == null) { + // Create a random seed of the appropriate native type. + + if (source.getSeed().equals(Integer.class)) { + nativeSeed = SeedFactory.createInt(); + } else if (source.getSeed().equals(Long.class)) { + nativeSeed = SeedFactory.createLong(); + } else if (source.getSeed().equals(int[].class)) { + nativeSeed = SeedFactory.createIntArray(RANDOM_SEED_ARRAY_SIZE); + } else if (source.getSeed().equals(long[].class)) { + nativeSeed = SeedFactory.createLongArray(RANDOM_SEED_ARRAY_SIZE); + } else { + // Source's native type is not handled. + throw new IllegalStateException(INTERNAL_ERROR_MSG); + } + } else { + // Convert to native type. + + if (seed instanceof Integer) { + nativeSeed = CONV_INT.get(source.getSeed()).convert((Integer) seed); + } else if (seed instanceof Long) { + nativeSeed = CONV_LONG.get(source.getSeed()).convert((Long) seed); + } else if (seed instanceof int[]) { + nativeSeed = CONV_INT_ARRAY.get(source.getSeed()).convert((int[]) seed); + } else if (seed instanceof long[]) { + nativeSeed = CONV_LONG_ARRAY.get(source.getSeed()).convert((long[]) seed); + } else if (seed instanceof byte[]) { + nativeSeed = CONV_BYTE_ARRAY.get(source.getSeed()).convert((byte[]) seed); + } + + if (nativeSeed == null) { + // Since the input seed was not null, getting here means that + // no suitable converter is present in the maps. + throw new UnsupportedOperationException("Unrecognized seed type"); + } + + if (!source.isNativeSeed(nativeSeed)) { + // Conversion setup is wrong. + throw new IllegalStateException(INTERNAL_ERROR_MSG); + } + } + + return nativeSeed; + } + + /** + * Creates a constructor. + * + * @param source RNG specification. + * @return a RNG constructor. + */ + private static Constructor<?> createConstructor(RandomSourceInternal source) { + try { + return source.getRng().getConstructor(source.getArgs()); + } catch (NoSuchMethodException e) { + // Info in "RandomSourceInternal" is inconsistent with the + // constructor of the implementation. + throw new IllegalStateException(INTERNAL_ERROR_MSG, e); + } + } + + /** + * Creates a RNG. + * + * @param rng RNG specification. + * @param args Arguments to the implementation's constructor. + * @return a new RNG instance. + */ + private static RestorableUniformRandomProvider create(Constructor<?> rng, + Object[] args) { + try { + return (RestorableUniformRandomProvider) rng.newInstance(args); + } catch (InvocationTargetException e) { + throw new IllegalStateException(INTERNAL_ERROR_MSG, e); + } catch (InstantiationException e) { + throw new IllegalStateException(INTERNAL_ERROR_MSG, e); + } catch (IllegalAccessException e) { + throw new IllegalStateException(INTERNAL_ERROR_MSG, e); + } + } + + /** + * Identifiers of the generators. + */ + public enum RandomSourceInternal { + /** Source of randomness is {@link JDKRandom}. */ + JDK(JDKRandom.class, + Long.class), + /** Source of randomness is {@link Well512a}. */ + WELL_512_A(Well512a.class, + int[].class), + /** Source of randomness is {@link Well1024a}. */ + WELL_1024_A(Well1024a.class, + int[].class), + /** Source of randomness is {@link Well19937a}. */ + WELL_19937_A(Well19937a.class, + int[].class), + /** Source of randomness is {@link Well19937c}. */ + WELL_19937_C(Well19937c.class, + int[].class), + /** Source of randomness is {@link Well44497a}. */ + WELL_44497_A(Well44497a.class, + int[].class), + /** Source of randomness is {@link Well44497b}. */ + WELL_44497_B(Well44497b.class, + int[].class), + /** Source of randomness is {@link MersenneTwister}. */ + MT(MersenneTwister.class, + int[].class), + /** Source of randomness is {@link ISAACRandom}. */ + ISAAC(ISAACRandom.class, + int[].class), + /** Source of randomness is {@link SplitMix64}. */ + SPLIT_MIX_64(SplitMix64.class, + Long.class), + /** Source of randomness is {@link XorShift1024Star}. */ + XOR_SHIFT_1024_S(XorShift1024Star.class, + long[].class), + /** Source of randomness is {@link TwoCmres}. */ + TWO_CMRES(TwoCmres.class, + Integer.class), + /** + * Source of randomness is {@link TwoCmres} with explicit selection + * of the two subcycle generators. + */ + TWO_CMRES_SELECT(TwoCmres.class, + Integer.class, + Integer.TYPE, + Integer.TYPE), + /** Source of randomness is {@link MersenneTwister64}. */ + MT_64(MersenneTwister64.class, + long[].class), + /** Source of randomness is {@link MultiplyWithCarry256}. */ + MWC_256(MultiplyWithCarry256.class, + int[].class), + /** Source of randomness is {@link KISSRandom}. */ + KISS(KISSRandom.class, + int[].class); + + /** Source type. */ + private final Class<? extends UniformRandomProvider> rng; + /** Data needed to build the generator. */ + private final Class<?>[] args; + + /** + * @param rng Source type. + * @param args Data needed to create a generator instance. + * The first element must be the native seed type. + */ + RandomSourceInternal(Class<? extends UniformRandomProvider> rng, + Class<?> ... args) { + this.rng = rng; + this.args = Arrays.copyOf(args, args.length); + } + + /** + * @return the source type. + */ + public Class<?> getRng() { + return rng; + } + + /** + * @return the seed type. + */ + Class<?> getSeed() { + return args[0]; + } + + /** + * @return the data needed to build the generator. + */ + Class<?>[] getArgs() { + return args; + } + + /** + * Checks whether the type of given {@code seed} is the native type + * of the implementation. + * + * @param <SEED> Seed type. + * + * @param seed Seed value. + * @return {@code true} if the seed can be passed to the builder + * for this RNG type. + */ + public <SEED> boolean isNativeSeed(SEED seed) { + return seed == null ? + false : + getSeed().equals(seed.getClass()); + } + } +}
http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/package-info.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/package-info.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/package-info.java new file mode 100644 index 0000000..f3c5970 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/package-info.java @@ -0,0 +1,52 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * <h3>Base classes for the {@link org.apache.commons.rng.UniformRandomProvider + * generation of uniformly distributed random numbers}. + * </h3> + * + * <p> + * <b>For internal use only:</b> Direct access to classes in this package + * and below, is discouraged, as they could be modified without notice. + * </p> + * + * <p><b>Notes for developers</b></p> + * + * <p> + * This package contains the common functionality. + * <br> + * Implementations that produce + * {@link org.apache.commons.rng.internal.source32.RandomIntSource int} + * values are defined in the + * {@link org.apache.commons.rng.internal.source32 source32} package. + * <br> + * Implementations that produce + * {@link org.apache.commons.rng.internal.source64.RandomLongSource long} + * values are defined in the + * {@link org.apache.commons.rng.internal.source64 source64} package. + * </p> + * + * <p> + * Each implementation must have an identifier in + * {@link org.apache.commons.rng.internal.ProviderBuilder.RandomSourceInternal + * ProviderBuilder.RandomSourceInternal} which must be referred to from the + * {@link org.apache.commons.rng.RandomSource public API}. + * </p> + */ + +package org.apache.commons.rng.internal; http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/AbstractWell.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/AbstractWell.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/AbstractWell.java new file mode 100644 index 0000000..2043ec6 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/AbstractWell.java @@ -0,0 +1,201 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +import java.util.Arrays; +import org.apache.commons.rng.internal.util.NumberFactory; + +/** + * This abstract class implements the WELL class of pseudo-random number + * generator from François Panneton, Pierre L'Ecuyer and Makoto + * Matsumoto. + * <p> + * This generator is described in a paper by François Panneton, + * Pierre L'Ecuyer and Makoto Matsumoto + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf";> + * Improved Long-Period Generators Based on Linear Recurrences Modulo 2</a> + * ACM Transactions on Mathematical Software, 32, 1 (2006). + * The errata for the paper are in + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt";>wellrng-errata.txt</a>. + * </p> + * + * @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html";>WELL Random number generator</a> + * + * @since 1.0 + */ +public abstract class AbstractWell extends IntProvider { + /** Current index in the bytes pool. */ + protected int index; + /** Bytes pool. */ + protected final int[] v; + + /** + * Creates an instance with the given {@code seed}. + * + * @param k Number of bits in the pool (not necessarily a multiple of 32). + * @param seed Initial seed. + */ + protected AbstractWell(final int k, + final int[] seed) { + final int r = calculateBlockCount(k); + v = new int[r]; + index = 0; + + // Initialize the pool content. + setSeedInternal(seed); + } + + /** {@inheritDoc} */ + @Override + protected byte[] getStateInternal() { + final int[] s = Arrays.copyOf(v, v.length + 1); + s[v.length] = index; + + return NumberFactory.makeByteArray(s); + } + + /** {@inheritDoc} */ + @Override + protected void setStateInternal(byte[] s) { + checkStateSize(s, (v.length + 1) * 4); + + final int[] tmp = NumberFactory.makeIntArray(s); + System.arraycopy(tmp, 0, v, 0, v.length); + index = tmp[v.length]; + } + + /** + * Initializes the generator with the given {@code seed}. + * + * @param seed Seed. Cannot be null. + */ + private void setSeedInternal(final int[] seed) { + System.arraycopy(seed, 0, v, 0, Math.min(seed.length, v.length)); + + if (seed.length < v.length) { + for (int i = seed.length; i < v.length; ++i) { + final long current = v[i - seed.length]; + v[i] = (int) ((1812433253L * (current ^ (current >> 30)) + i) & 0xffffffffL); + } + } + + index = 0; + } + + /** + * Calculate the number of 32-bits blocks. + * + * @param k Number of bits in the pool (not necessarily a multiple of 32). + * @return the number of 32-bits blocks. + */ + private static int calculateBlockCount(final int k) { + // the bits pool contains k bits, k = r w - p where r is the number + // of w bits blocks, w is the block size (always 32 in the original paper) + // and p is the number of unused bits in the last block + final int w = 32; + final int r = (k + w - 1) / w; + return r; + } + + /** + * Inner class used to store the indirection index table which is fixed for a given + * type of WELL class of pseudo-random number generator. + */ + protected static final class IndexTable { + /** Index indirection table giving for each index its predecessor taking table size into account. */ + private final int[] iRm1; + /** Index indirection table giving for each index its second predecessor taking table size into account. */ + private final int[] iRm2; + /** Index indirection table giving for each index the value index + m1 taking table size into account. */ + private final int[] i1; + /** Index indirection table giving for each index the value index + m2 taking table size into account. */ + private final int[] i2; + /** Index indirection table giving for each index the value index + m3 taking table size into account. */ + private final int[] i3; + + /** Creates a new pre-calculated indirection index table. + * @param k number of bits in the pool (not necessarily a multiple of 32) + * @param m1 first parameter of the algorithm + * @param m2 second parameter of the algorithm + * @param m3 third parameter of the algorithm + */ + public IndexTable(final int k, final int m1, final int m2, final int m3) { + + final int r = calculateBlockCount(k); + + // precompute indirection index tables. These tables are used for optimizing access + // they allow saving computations like "(j + r - 2) % r" with costly modulo operations + iRm1 = new int[r]; + iRm2 = new int[r]; + i1 = new int[r]; + i2 = new int[r]; + i3 = new int[r]; + for (int j = 0; j < r; ++j) { + iRm1[j] = (j + r - 1) % r; + iRm2[j] = (j + r - 2) % r; + i1[j] = (j + m1) % r; + i2[j] = (j + m2) % r; + i3[j] = (j + m3) % r; + } + } + + /** + * Returns the predecessor of the given index modulo the table size. + * @param index the index to look at + * @return (index - 1) % table size + */ + public int getIndexPred(final int index) { + return iRm1[index]; + } + + /** + * Returns the second predecessor of the given index modulo the table size. + * @param index the index to look at + * @return (index - 2) % table size + */ + public int getIndexPred2(final int index) { + return iRm2[index]; + } + + /** + * Returns index + M1 modulo the table size. + * @param index the index to look at + * @return (index + M1) % table size + */ + public int getIndexM1(final int index) { + return i1[index]; + } + + /** + * Returns index + M2 modulo the table size. + * @param index the index to look at + * @return (index + M2) % table size + */ + public int getIndexM2(final int index) { + return i2[index]; + } + + /** + * Returns index + M3 modulo the table size. + * @param index the index to look at + * @return (index + M3) % table size + */ + public int getIndexM3(final int index) { + return i3[index]; + } + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/ISAACRandom.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/ISAACRandom.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/ISAACRandom.java new file mode 100644 index 0000000..79433c9 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/ISAACRandom.java @@ -0,0 +1,267 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.rng.internal.source32; + +import java.util.Arrays; +import org.apache.commons.rng.internal.util.NumberFactory; + +/** + * A fast cryptographic pseudo-random number generator. + * <p> + * ISAAC (Indirection, Shift, Accumulate, Add, and Count) generates 32-bit + * random numbers. + * ISAAC has been designed to be cryptographically secure and is inspired + * by RC4. + * Cycles are guaranteed to be at least 2<sup>40</sup> values long, and they + * are 2<sup>8295</sup> values long on average. + * The results are uniformly distributed, unbiased, and unpredictable unless + * you know the seed. + * <p> + * This code is based (with minor changes and improvements) on the original + * implementation of the algorithm by Bob Jenkins. + * + * @see <a href="http://burtleburtle.net/bob/rand/isaacafa.html";> + * ISAAC: a fast cryptographic pseudo-random number generator</a> + * + * @see <a href="https://en.wikipedia.org/wiki/ISAAC_(cipher)">ISAAC (Wikipedia)</a> + * @since 1.0 + */ +public class ISAACRandom extends IntProvider { + /** Log of size of rsl[] and mem[]. */ + private static final int SIZE_L = 8; + /** Size of rsl[] and mem[]. */ + private static final int SIZE = 1 << SIZE_L; + /** Half-size of rsl[] and mem[]. */ + private static final int H_SIZE = SIZE >> 1; + /** For pseudo-random lookup. */ + private static final int MASK = SIZE - 1 << 2; + /** The golden ratio. */ + private static final int GLD_RATIO = 0x9e3779b9; + /** The results given to the user. */ + private final int[] rsl = new int[SIZE]; + /** The internal state. */ + private final int[] mem = new int[SIZE]; + /** Count through the results in rsl[]. */ + private int count; + /** Accumulator. */ + private int isaacA; + /** The last result. */ + private int isaacB; + /** Counter, guarantees cycle is at least 2^40. */ + private int isaacC; + /** Service variable. */ + private final int[] arr = new int[8]; + /** Service variable. */ + private int isaacX; + /** Service variable. */ + private int isaacI; + /** Service variable. */ + private int isaacJ; + + /** + * Creates a new ISAAC random number generator. + * + * @param seed Initial seed + */ + public ISAACRandom(int[] seed) { + setSeedInternal(seed); + } + + /** {@inheritDoc} */ + @Override + protected byte[] getStateInternal() { + final int[] sRsl = Arrays.copyOf(rsl, SIZE); + final int[] sMem = Arrays.copyOf(mem, SIZE); + final int[] sRem = Arrays.copyOf(new int[] { count, isaacA, isaacB, isaacC }, 4); + + final int[] s = new int[2 * SIZE + sRem.length]; + System.arraycopy(sRsl, 0, s, 0, SIZE); + System.arraycopy(sMem, 0, s, SIZE, SIZE); + System.arraycopy(sRem, 0, s, 2 * SIZE, sRem.length); + + return NumberFactory.makeByteArray(s); + } + + /** {@inheritDoc} */ + @Override + protected void setStateInternal(byte[] s) { + checkStateSize(s, (2 * SIZE + 4) * 4); + + final int[] tmp = NumberFactory.makeIntArray(s); + System.arraycopy(tmp, 0, rsl, 0, SIZE); + System.arraycopy(tmp, SIZE, mem, 0, SIZE); + final int offset = 2 * SIZE; + count = tmp[offset]; + isaacA = tmp[offset + 1]; + isaacB = tmp[offset + 2]; + isaacC = tmp[offset + 3]; + } + + /** + * Reseeds the RNG. + * + * @param seed Seed. Cannot be null. + */ + private void setSeedInternal(int[] seed) { + final int seedLen = seed.length; + final int rslLen = rsl.length; + System.arraycopy(seed, 0, rsl, 0, Math.min(seedLen, rslLen)); + if (seedLen < rslLen) { + for (int j = seedLen; j < rslLen; j++) { + long k = rsl[j - seedLen]; + rsl[j] = (int) (0x6c078965L * (k ^ k >> 30) + j & 0xffffffffL); + } + } + initState(); + } + + /** {@inheritDoc} */ + @Override + public int next() { + if (count < 0) { + isaac(); + count = SIZE - 1; + } + return rsl[count--]; + } + + /** Generate 256 results */ + private void isaac() { + isaacI = 0; + isaacJ = H_SIZE; + isaacB += ++isaacC; + while (isaacI < H_SIZE) { + isaac2(); + } + isaacJ = 0; + while (isaacJ < H_SIZE) { + isaac2(); + } + } + + /** Intermediate internal loop. */ + private void isaac2() { + isaacX = mem[isaacI]; + isaacA ^= isaacA << 13; + isaacA += mem[isaacJ++]; + isaac3(); + isaacX = mem[isaacI]; + isaacA ^= isaacA >>> 6; + isaacA += mem[isaacJ++]; + isaac3(); + isaacX = mem[isaacI]; + isaacA ^= isaacA << 2; + isaacA += mem[isaacJ++]; + isaac3(); + isaacX = mem[isaacI]; + isaacA ^= isaacA >>> 16; + isaacA += mem[isaacJ++]; + isaac3(); + } + + /** Lowest level internal loop. */ + private void isaac3() { + mem[isaacI] = mem[(isaacX & MASK) >> 2] + isaacA + isaacB; + isaacB = mem[(mem[isaacI] >> SIZE_L & MASK) >> 2] + isaacX; + rsl[isaacI++] = isaacB; + } + + /** Initialize, or reinitialize, this instance of rand. */ + private void initState() { + isaacA = 0; + isaacB = 0; + isaacC = 0; + for (int j = 0; j < arr.length; j++) { + arr[j] = GLD_RATIO; + } + for (int j = 0; j < 4; j++) { + shuffle(); + } + // fill in mem[] with messy stuff + for (int j = 0; j < SIZE; j += 8) { + arr[0] += rsl[j]; + arr[1] += rsl[j + 1]; + arr[2] += rsl[j + 2]; + arr[3] += rsl[j + 3]; + arr[4] += rsl[j + 4]; + arr[5] += rsl[j + 5]; + arr[6] += rsl[j + 6]; + arr[7] += rsl[j + 7]; + shuffle(); + setState(j); + } + // second pass makes all of seed affect all of mem + for (int j = 0; j < SIZE; j += 8) { + arr[0] += mem[j]; + arr[1] += mem[j + 1]; + arr[2] += mem[j + 2]; + arr[3] += mem[j + 3]; + arr[4] += mem[j + 4]; + arr[5] += mem[j + 5]; + arr[6] += mem[j + 6]; + arr[7] += mem[j + 7]; + shuffle(); + setState(j); + } + isaac(); + count = SIZE - 1; + } + + /** Shuffle array. */ + private void shuffle() { + arr[0] ^= arr[1] << 11; + arr[3] += arr[0]; + arr[1] += arr[2]; + arr[1] ^= arr[2] >>> 2; + arr[4] += arr[1]; + arr[2] += arr[3]; + arr[2] ^= arr[3] << 8; + arr[5] += arr[2]; + arr[3] += arr[4]; + arr[3] ^= arr[4] >>> 16; + arr[6] += arr[3]; + arr[4] += arr[5]; + arr[4] ^= arr[5] << 10; + arr[7] += arr[4]; + arr[5] += arr[6]; + arr[5] ^= arr[6] >>> 4; + arr[0] += arr[5]; + arr[6] += arr[7]; + arr[6] ^= arr[7] << 8; + arr[1] += arr[6]; + arr[7] += arr[0]; + arr[7] ^= arr[0] >>> 9; + arr[2] += arr[7]; + arr[0] += arr[1]; + } + + /** Set the state by copying the internal arrays. + * + * @param start First index into {@link #mem} array. + */ + private void setState(int start) { + mem[start] = arr[0]; + mem[start + 1] = arr[1]; + mem[start + 2] = arr[2]; + mem[start + 3] = arr[3]; + mem[start + 4] = arr[4]; + mem[start + 5] = arr[5]; + mem[start + 6] = arr[6]; + mem[start + 7] = arr[7]; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/IntProvider.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/IntProvider.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/IntProvider.java new file mode 100644 index 0000000..ba30fd9 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/IntProvider.java @@ -0,0 +1,130 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.rng.internal.source32; + +import org.apache.commons.rng.internal.util.NumberFactory; +import org.apache.commons.rng.internal.BaseProvider; + +/** + * Base class for all implementations that provide an {@code int}-based + * source randomness. + */ +public abstract class IntProvider + extends BaseProvider + implements RandomIntSource { + + /** {@inheritDoc} */ + @Override + public abstract int next(); + + /** {@inheritDoc} */ + @Override + public int nextInt() { + return next(); + } + + /** {@inheritDoc} */ + @Override + public boolean nextBoolean() { + return NumberFactory.makeBoolean(nextInt()); + } + + /** {@inheritDoc} */ + @Override + public double nextDouble() { + return NumberFactory.makeDouble(nextInt(), nextInt()); + } + + /** {@inheritDoc} */ + @Override + public float nextFloat() { + return NumberFactory.makeFloat(nextInt()); + } + + /** {@inheritDoc} */ + @Override + public long nextLong() { + return NumberFactory.makeLong(nextInt(), nextInt()); + } + + /** {@inheritDoc} */ + @Override + public void nextBytes(byte[] bytes) { + nextBytesFill(this, bytes, 0, bytes.length); + } + + /** {@inheritDoc} */ + @Override + public void nextBytes(byte[] bytes, + int start, + int len) { + checkIndex(0, bytes.length - 1, start); + checkIndex(0, bytes.length - start, len); + + nextBytesFill(this, bytes, start, len); + } + + /** + * Generates random bytes and places them into a user-supplied array. + * + * <p> + * The array is filled with bytes extracted from random {@code int} values. + * This implies that the number of random bytes generated may be larger than + * the length of the byte array. + * </p> + * + * @param source Source of randomness. + * @param bytes Array in which to put the generated bytes. Cannot be null. + * @param start Index at which to start inserting the generated bytes. + * @param len Number of bytes to insert. + */ + static void nextBytesFill(RandomIntSource source, + byte[] bytes, + int start, + int len) { + int index = start; // Index of first insertion. + + // Index of first insertion plus multiple of 4 part of length + // (i.e. length with 2 least significant bits unset). + final int indexLoopLimit = index + (len & 0x7ffffffc); + + // Start filling in the byte array, 4 bytes at a time. + while (index < indexLoopLimit) { + final int random = source.next(); + bytes[index++] = (byte) random; + bytes[index++] = (byte) (random >>> 8); + bytes[index++] = (byte) (random >>> 16); + bytes[index++] = (byte) (random >>> 24); + } + + final int indexLimit = start + len; // Index of last insertion + 1. + + // Fill in the remaining bytes. + if (index < indexLimit) { + int random = source.next(); + while (true) { + bytes[index++] = (byte) random; + if (index < indexLimit) { + random >>>= 8; + } else { + break; + } + } + } + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/JDKRandom.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/JDKRandom.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/JDKRandom.java new file mode 100644 index 0000000..028469b --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/JDKRandom.java @@ -0,0 +1,98 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +import java.util.Random; +import java.io.IOException; +import java.io.ObjectOutputStream; +import java.io.ObjectInputStream; +import java.io.ByteArrayOutputStream; +import java.io.ByteArrayInputStream; + +/** + * A provider that uses the {@link Random#nextInt()} method of the JDK's + * {@link Random} class as the source of randomness. + * + * <p> + * <b>Caveat:</b> All the other calls will be redirected to the methods + * implemented within this library. + * </p> + * + * <p> + * The state of this source of randomness is saved and restored through + * the serialization of the {@link Random} instance. + * </p> + * + * @since 1.0 + */ +public class JDKRandom extends IntProvider { + /** Delegate. Cannot be "final" (to allow serialization). */ + private Random delegate; + + /** + * Creates an instance with the given seed. + * + * @param seed Initial seed. + */ + public JDKRandom(Long seed) { + delegate = new Random(seed); + } + + /** + * {@inheritDoc} + * + * @see Random#nextInt() + */ + @Override + public int next() { + return delegate.nextInt(); + } + + /** {@inheritDoc} */ + @Override + protected byte[] getStateInternal() { + try { + final ByteArrayOutputStream bos = new ByteArrayOutputStream(); + final ObjectOutputStream oos = new ObjectOutputStream(bos); + + // Serialize the "delegate". + oos.writeObject(delegate); + + return bos.toByteArray(); + } catch (IOException e) { + // Workaround checked exception. + throw new RuntimeException(e); + } + } + + /** {@inheritDoc} */ + @Override + protected void setStateInternal(byte[] s) { + try { + final ByteArrayInputStream bis = new ByteArrayInputStream(s); + final ObjectInputStream ois = new ObjectInputStream(bis); + + delegate = (Random) ois.readObject(); + } catch (ClassNotFoundException e) { + // Workaround checked exception. + throw new RuntimeException(e); + } catch (IOException e) { + // Workaround checked exception. + throw new RuntimeException(e); + } + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/KISSRandom.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/KISSRandom.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/KISSRandom.java new file mode 100644 index 0000000..5c0ecf4 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/KISSRandom.java @@ -0,0 +1,121 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +import org.apache.commons.rng.internal.util.NumberFactory; +import org.apache.commons.rng.internal.util.SeedFactory; + +/** + * Port from Marsaglia's <a href="http://www.cse.yorku.ca/~oz/marsaglia-rng.html";> + * "KISS" algorithm</a>. + * This version contains the correction referred to + * <a href="https://programmingpraxis.com/2010/10/05/george-marsaglias-random-number-generators/";>here</a> + * in a reply to the original post. + * + * @see <a href="https://en.wikipedia.org/wiki/KISS_(algorithm)">KISS (Wikipedia)</a> + * @since 1.0 + */ +public class KISSRandom extends IntProvider { + /** Size of the seed. */ + private static final int SEED_SIZE = 4; + /** State variable. */ + private int z; + /** State variable. */ + private int w; + /** State variable. */ + private int jsr; + /** State variable. */ + private int jcong; + + /** + * Creates a new instance. + * + * @param seed Seed. + * If the length is larger than 4, only the first 4 elements will + * be used; if smaller, the remaining elements will be automatically + * set. + */ + public KISSRandom(int[] seed) { + setSeedInternal(seed); + } + + /** {@inheritDoc} */ + @Override + protected byte[] getStateInternal() { + return NumberFactory.makeByteArray(new int[] { z, w, jsr, jcong }); + } + + /** {@inheritDoc} */ + @Override + protected void setStateInternal(byte[] s) { + checkStateSize(s, SEED_SIZE * 4); + + final int[] tmp = NumberFactory.makeIntArray(s); + + z = tmp[0]; + w = tmp[1]; + jsr = tmp[2]; + jcong = tmp[3]; + } + + /** + * Seeds the RNG. + * + * @param seed Seed. + */ + private void setSeedInternal(int[] seed) { + // Reset the whole state of this RNG (i.e. the 4 state variables). + // Filling procedure is not part of the reference code. + final int[] tmp = new int[SEED_SIZE]; + SeedFactory.fillState(tmp, seed); + + z = tmp[0]; + w = tmp[1]; + jsr = tmp[2]; + jcong = tmp[3]; + } + + /** {@inheritDoc} */ + @Override + public int next() { + z = computeNew(36969, z); + w = computeNew(18000, w); + final int mwc = (z << 16) + w; + + // Cf. correction mentioned in the reply to the original post: + // https://programmingpraxis.com/2010/10/05/george-marsaglias-random-number-generators/ + jsr ^= jsr << 13; + jsr ^= jsr >>> 17; + jsr ^= jsr << 5; + + jcong = 69069 * jcong + 1234567; + + return (mwc ^ jcong) + jsr; + } + + /** + * Compute new value. + * + * @param mult Multiplier. + * @param previous Previous value. + * @return new value. + */ + private int computeNew(int mult, + int previous) { + return mult * (previous & 65535) + (previous >>> 16); + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MersenneTwister.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MersenneTwister.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MersenneTwister.java new file mode 100644 index 0000000..baa0793 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MersenneTwister.java @@ -0,0 +1,244 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +import java.util.Arrays; +import org.apache.commons.rng.internal.util.NumberFactory; + +/** + * This class implements a powerful pseudo-random number generator + * developed by Makoto Matsumoto and Takuji Nishimura during + * 1996-1997. + * + * <p> + * This generator features an extremely long period + * (2<sup>19937</sup>-1) and 623-dimensional equidistribution up to + * 32 bits accuracy. The home page for this generator is located at + * <a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html";> + * http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html</a>. + * </p> + * + * <p> + * This generator is described in a paper by Makoto Matsumoto and + * Takuji Nishimura in 1998: + * <a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf";> + * Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random + * Number Generator</a>, + * ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, + * January 1998, pp 3--30 + * </p> + * + * <p> + * This class is mainly a Java port of the + * <a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html";> + * 2002-01-26 version of the generator</a> written in C by Makoto Matsumoto + * and Takuji Nishimura. Here is their original copyright: + * </p> + * + * <table border="0" width="80%" cellpadding="10" style="background-color: #E0E0E0" summary="Mersenne Twister licence"> + * <tr><td>Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, + * All rights reserved.</td></tr> + * + * <tr><td>Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * <ol> + * <li>Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer.</li> + * <li>Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution.</li> + * <li>The names of its contributors may not be used to endorse or promote + * products derived from this software without specific prior written + * permission.</li> + * </ol></td></tr> + * + * <tr><td><strong>THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS + * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, + * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE + * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE.</strong></td></tr> + * </table> + * + * @see <a href="https://en.wikipedia.org/wiki/Mersenne_Twister";>Mersenne Twister (Wikipedia)</a> + * @since 1.0 + */ +public class MersenneTwister extends IntProvider { + /** Mask 32 most significant bits. */ + private static final long INT_MASK_LONG = 0xffffffffL; + /** Most significant w-r bits. */ + private static final long UPPER_MASK_LONG = 0x80000000L; + /** Least significant r bits. */ + private static final long LOWER_MASK_LONG = 0x7fffffffL; + /** Most significant w-r bits. */ + private static final int UPPER_MASK = 0x80000000; + /** Least significant r bits. */ + private static final int LOWER_MASK = 0x7fffffff; + /** Size of the bytes pool. */ + private static final int N = 624; + /** Period second parameter. */ + private static final int M = 397; + /** X * MATRIX_A for X = {0, 1}. */ + private static final int[] MAG01 = { 0x0, 0x9908b0df }; + /** Bytes pool. */ + private int[] mt = new int[N]; + /** Current index in the bytes pool. */ + private int mti; + + /** + * Creates a new random number generator. + * + * @param seed Initial seed. + */ + public MersenneTwister(int[] seed) { + setSeedInternal(seed); + } + + /** {@inheritDoc} */ + @Override + protected byte[] getStateInternal() { + final int[] s = Arrays.copyOf(mt, N + 1); + s[N] = mti; + + return NumberFactory.makeByteArray(s); + } + + /** {@inheritDoc} */ + @Override + protected void setStateInternal(byte[] s) { + checkStateSize(s, (N + 1) * 4); + + final int[] tmp = NumberFactory.makeIntArray(s); + System.arraycopy(tmp, 0, mt, 0, N); + mti = tmp[N]; + } + + /** + * Initializes the generator with the given seed. + * + * @param seed Initial seed. + */ + private void setSeedInternal(int[] seed) { + fillStateMersenneTwister(mt, seed); + + // Initial index. + mti = N; + } + + /** + * Utility for wholly filling a {@code state} array with non-zero + * bytes, even if the {@code seed} has a smaller size. + * The procedure is the one defined by the standard implementation + * of the algorithm. + * + * @param state State to be filled (must be allocated). + * @param seed Seed (cannot be {@code null}). + */ + private static void fillStateMersenneTwister(int[] state, + int[] seed) { + if (seed.length == 0) { + // Accept empty seed. + seed = new int[1]; + } + + final int stateSize = state.length; + + long mt = 19650218 & INT_MASK_LONG; + state[0] = (int) mt; + for (int i = 1; i < stateSize; i++) { + mt = (1812433253L * (mt ^ (mt >> 30)) + i) & INT_MASK_LONG; + state[i] = (int) mt; + } + + int i = 1; + int j = 0; + + for (int k = Math.max(stateSize, seed.length); k > 0; k--) { + final long a = (state[i] & LOWER_MASK_LONG) | ((state[i] < 0) ? UPPER_MASK_LONG : 0); + final long b = (state[i - 1] & LOWER_MASK_LONG) | ((state[i - 1] < 0) ? UPPER_MASK_LONG : 0); + final long c = (a ^ ((b ^ (b >> 30)) * 1664525L)) + seed[j] + j; // Non linear. + state[i] = (int) (c & INT_MASK_LONG); + i++; + j++; + if (i >= stateSize) { + state[0] = state[stateSize - 1]; + i = 1; + } + if (j >= seed.length) { + j = 0; + } + } + + for (int k = stateSize - 1; k > 0; k--) { + final long a = (state[i] & LOWER_MASK_LONG) | ((state[i] < 0) ? UPPER_MASK_LONG : 0); + final long b = (state[i - 1] & LOWER_MASK_LONG) | ((state[i - 1] < 0) ? UPPER_MASK_LONG : 0); + final long c = (a ^ ((b ^ (b >> 30)) * 1566083941L)) - i; // Non linear. + state[i] = (int) (c & INT_MASK_LONG); + i++; + if (i >= stateSize) { + state[0] = state[stateSize - 1]; + i = 1; + } + } + + state[0] = (int) UPPER_MASK_LONG; // MSB is 1, ensuring non-zero initial array. + } + + /** {@inheritDoc} */ + @Override + public int next() { + int y; + + if (mti >= N) { // Generate N words at one time. + int mtNext = mt[0]; + for (int k = 0; k < N - M; ++k) { + int mtCurr = mtNext; + mtNext = mt[k + 1]; + y = (mtCurr & UPPER_MASK) | (mtNext & LOWER_MASK); + mt[k] = mt[k + M] ^ (y >>> 1) ^ MAG01[y & 1]; + } + for (int k = N - M; k < N - 1; ++k) { + int mtCurr = mtNext; + mtNext = mt[k + 1]; + y = (mtCurr & UPPER_MASK) | (mtNext & LOWER_MASK); + mt[k] = mt[k + (M - N)] ^ (y >>> 1) ^ MAG01[y & 1]; + } + y = (mtNext & UPPER_MASK) | (mt[0] & LOWER_MASK); + mt[N - 1] = mt[M - 1] ^ (y >>> 1) ^ MAG01[y & 1]; + + mti = 0; + } + + y = mt[mti++]; + + // Tempering. + y ^= y >>> 11; + y ^= (y << 7) & 0x9d2c5680; + y ^= (y << 15) & 0xefc60000; + y ^= y >>> 18; + + return y; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MultiplyWithCarry256.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MultiplyWithCarry256.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MultiplyWithCarry256.java new file mode 100644 index 0000000..65cf152 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/MultiplyWithCarry256.java @@ -0,0 +1,124 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +import java.util.Arrays; +import org.apache.commons.rng.internal.util.NumberFactory; +import org.apache.commons.rng.internal.util.SeedFactory; + +/** + * Port from Marsaglia's <a href="https://en.wikipedia.org/wiki/Multiply-with-carry";> + * "Multiply-With-Carry" algorithm</a>. + * + * <p> + * Implementation is based on the (non-portable!) C code reproduced on + * <a href="http://school.anhb.uwa.edu.au/personalpages/kwessen/shared/Marsaglia03.html";> + * that page</a>. + * </p> + * + * @see <a href="https://en.wikipedia.org/wiki/Multiply-with-carry";>Multiply with carry (Wikipedia)</a> + * @since 1.0 + */ +public class MultiplyWithCarry256 extends IntProvider { + /** Length of the state array. */ + private static final int Q_SIZE = 256; + /** Size of the seed. */ + private static final int SEED_SIZE = Q_SIZE + 1; + /** Multiply. */ + private static final long A = 809430660; + /** State. */ + private final int[] state = new int[Q_SIZE]; + /** Current index in "state" array. */ + private int index; + /** Carry. */ + private int carry; + + /** + * Creates a new instance. + * + * @param seed Seed. + * If the length is larger than 257, only the first 257 elements will + * be used; if smaller, the remaining elements will be automatically + * set. + */ + public MultiplyWithCarry256(int[] seed) { + setSeedInternal(seed); + } + + /** {@inheritDoc} */ + @Override + protected byte[] getStateInternal() { + final int[] s = Arrays.copyOf(state, SEED_SIZE + 1); + s[SEED_SIZE - 1] = carry; + s[SEED_SIZE] = index; + + return NumberFactory.makeByteArray(s); + } + + /** {@inheritDoc} */ + @Override + protected void setStateInternal(byte[] s) { + checkStateSize(s, (SEED_SIZE + 1) * 4); + + final int[] tmp = NumberFactory.makeIntArray(s); + + System.arraycopy(tmp, 0, state, 0, Q_SIZE); + carry = tmp[SEED_SIZE - 1]; + index = tmp[SEED_SIZE]; + } + + /** + * Seeds the RNG. + * + * @param seed Seed. + */ + private void setSeedInternal(int[] seed) { + // Reset the whole state of this RNG (i.e. "state" and "index"). + // Filling procedure is not part of the reference code. + final int[] tmp = new int[SEED_SIZE]; + SeedFactory.fillState(tmp, seed); + + // First element of the "seed" is the initial "carry". + final int c = tmp[0]; + // Marsaglia's recommendation: 0 <= carry < A. + carry = (int) ((c < 0 ? -c : c) % A); + + // Initial state. + System.arraycopy(tmp, 1, state, 0, Q_SIZE); + + // Initial index. + index = Q_SIZE; + } + + /** {@inheritDoc} */ + @Override + public int next() { + if (index == Q_SIZE) { // Whole state used up. + // Refill. + for (int i = 0; i < Q_SIZE; i++) { + final long t = A * (state[i] & 0xffffffffL) + carry; + carry = (int) (t >> 32); + state[i] = (int) t; + } + + // Reset current index. + index = 0; + } + + return state[index++]; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/RandomIntSource.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/RandomIntSource.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/RandomIntSource.java new file mode 100644 index 0000000..fe5a853 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/RandomIntSource.java @@ -0,0 +1,30 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.commons.rng.internal.source32; + +/** + * Source of randomness that generates values of type {@code int}. + * + * @since 1.0 + */ +public interface RandomIntSource { + /** + * @return the next random value. + */ + int next(); +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well1024a.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well1024a.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well1024a.java new file mode 100644 index 0000000..f465212 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well1024a.java @@ -0,0 +1,78 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +/** + * This class implements the WELL1024a pseudo-random number generator + * from François Panneton, Pierre L'Ecuyer and Makoto Matsumoto. + * <p> + * This generator is described in a paper by François Panneton, + * Pierre L'Ecuyer and Makoto Matsumoto + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf";> + * Improved Long-Period Generators Based on Linear Recurrences Modulo 2</a> + * ACM Transactions on Mathematical Software, 32, 1 (2006). + * The errata for the paper are in + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt";>wellrng-errata.txt</a>. + * </p> + * + * @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html";>WELL Random number generator</a> + * @since 1.0 + */ +public class Well1024a extends AbstractWell { + /** Number of bits in the pool. */ + private static final int K = 1024; + /** First parameter of the algorithm. */ + private static final int M1 = 3; + /** Second parameter of the algorithm. */ + private static final int M2 = 24; + /** Third parameter of the algorithm. */ + private static final int M3 = 10; + /** The indirection index table. */ + private static final IndexTable TABLE = new IndexTable(K, M1, M2, M3); + + /** + * Creates a new random number generator. + * + * @param seed Initial seed. + */ + public Well1024a(int[] seed) { + super(K, seed); + } + + /** {@inheritDoc} */ + @Override + public int next() { + final int indexRm1 = TABLE.getIndexPred(index); + + final int v0 = v[index]; + final int vM1 = v[TABLE.getIndexM1(index)]; + final int vM2 = v[TABLE.getIndexM2(index)]; + final int vM3 = v[TABLE.getIndexM3(index)]; + + final int z0 = v[indexRm1]; + final int z1 = v0 ^ (vM1 ^ (vM1 >>> 8)); + final int z2 = (vM2 ^ (vM2 << 19)) ^ (vM3 ^ (vM3 << 14)); + final int z3 = z1 ^ z2; + final int z4 = (z0 ^ (z0 << 11)) ^ (z1 ^ (z1 << 7)) ^ (z2 ^ (z2 << 13)); + + v[index] = z3; + v[indexRm1] = z4; + index = indexRm1; + + return z4; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937a.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937a.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937a.java new file mode 100644 index 0000000..866f43e --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937a.java @@ -0,0 +1,80 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +/** + * This class implements the WELL19937a pseudo-random number generator + * from François Panneton, Pierre L'Ecuyer and Makoto Matsumoto. + * <p> + * This generator is described in a paper by François Panneton, + * Pierre L'Ecuyer and Makoto Matsumoto + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf";> + * Improved Long-Period Generators Based on Linear Recurrences Modulo 2</a> + * ACM Transactions on Mathematical Software, 32, 1 (2006). + * The errata for the paper are in + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt";>wellrng-errata.txt</a>. + * </p> + * + * @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html";>WELL Random number generator</a> + * @since 1.0 + */ +public class Well19937a extends AbstractWell { + /** Number of bits in the pool. */ + private static final int K = 19937; + /** First parameter of the algorithm. */ + private static final int M1 = 70; + /** Second parameter of the algorithm. */ + private static final int M2 = 179; + /** Third parameter of the algorithm. */ + private static final int M3 = 449; + /** The indirection index table. */ + private static final IndexTable TABLE = new IndexTable(K, M1, M2, M3); + + /** + * Creates a new random number generator. + * + * @param seed Initial seed. + */ + public Well19937a(int[] seed) { + super(K, seed); + } + + /** {@inheritDoc} */ + @Override + public int next() { + final int indexRm1 = TABLE.getIndexPred(index); + final int indexRm2 = TABLE.getIndexPred2(index); + + final int v0 = v[index]; + final int vM1 = v[TABLE.getIndexM1(index)]; + final int vM2 = v[TABLE.getIndexM2(index)]; + final int vM3 = v[TABLE.getIndexM3(index)]; + + final int z0 = (0x80000000 & v[indexRm1]) ^ (0x7FFFFFFF & v[indexRm2]); + final int z1 = (v0 ^ (v0 << 25)) ^ (vM1 ^ (vM1 >>> 27)); + final int z2 = (vM2 >>> 9) ^ (vM3 ^ (vM3 >>> 1)); + final int z3 = z1 ^ z2; + final int z4 = z0 ^ (z1 ^ (z1 << 9)) ^ (z2 ^ (z2 << 21)) ^ (z3 ^ (z3 >>> 21)); + + v[index] = z3; + v[indexRm1] = z4; + v[indexRm2] &= 0x80000000; + index = indexRm1; + + return z4; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937c.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937c.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937c.java new file mode 100644 index 0000000..ca0783f --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well19937c.java @@ -0,0 +1,56 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +/** + * This class implements the WELL19937c pseudo-random number generator + * from François Panneton, Pierre L'Ecuyer and Makoto Matsumoto. + * <p> + * This generator is described in a paper by François Panneton, + * Pierre L'Ecuyer and Makoto Matsumoto + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf";> + * Improved Long-Period Generators Based on Linear Recurrences Modulo 2</a> + * ACM Transactions on Mathematical Software, 32, 1 (2006). + * The errata for the paper are in + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt";>wellrng-errata.txt</a>. + * </p> + * + * @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html";>WELL Random number generator</a> + * @since 1.0 + */ +public class Well19937c extends Well19937a { + /** + * Creates a new random number generator. + * + * @param seed Initial seed. + */ + public Well19937c(int[] seed) { + super(seed); + } + + /** {@inheritDoc} */ + @Override + public int next() { + int z4 = super.next(); + + // Matsumoto-Kurita tempering to get a maximally equidistributed generator. + z4 ^= (z4 << 7) & 0xe46e1700; + z4 ^= (z4 << 15) & 0x9b868000; + + return z4; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497a.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497a.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497a.java new file mode 100644 index 0000000..8cef728 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497a.java @@ -0,0 +1,83 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +/** + * This class implements the WELL44497a pseudo-random number generator + * from François Panneton, Pierre L'Ecuyer and Makoto Matsumoto. + * <p> + * This generator is described in a paper by François Panneton, + * Pierre L'Ecuyer and Makoto Matsumoto + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf";> + * Improved Long-Period Generators Based on Linear Recurrences Modulo 2</a> + * ACM Transactions on Mathematical Software, 32, 1 (2006). + * The errata for the paper are in + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt";>wellrng-errata.txt</a>. + * </p> + * + * @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html";>WELL Random number generator</a> + * @since 1.0 + */ +public class Well44497a extends AbstractWell { + /** Number of bits in the pool. */ + private static final int K = 44497; + /** First parameter of the algorithm. */ + private static final int M1 = 23; + /** Second parameter of the algorithm. */ + private static final int M2 = 481; + /** Third parameter of the algorithm. */ + private static final int M3 = 229; + /** The indirection index table. */ + private static final IndexTable TABLE = new IndexTable(K, M1, M2, M3); + + /** + * Creates a new random number generator. + * + * @param seed Initial seed. + */ + public Well44497a(int[] seed) { + super(K, seed); + } + + /** {@inheritDoc} */ + @Override + public int next() { + final int indexRm1 = TABLE.getIndexPred(index); + final int indexRm2 = TABLE.getIndexPred2(index); + + final int v0 = v[index]; + final int vM1 = v[TABLE.getIndexM1(index)]; + final int vM2 = v[TABLE.getIndexM2(index)]; + final int vM3 = v[TABLE.getIndexM3(index)]; + + // the values below include the errata of the original article + final int z0 = (0xFFFF8000 & v[indexRm1]) ^ (0x00007FFF & v[indexRm2]); + final int z1 = (v0 ^ (v0 << 24)) ^ (vM1 ^ (vM1 >>> 30)); + final int z2 = (vM2 ^ (vM2 << 10)) ^ (vM3 << 26); + final int z3 = z1 ^ z2; + final int z2Prime = ((z2 << 9) ^ (z2 >>> 23)) & 0xfbffffff; + final int z2Second = ((z2 & 0x00020000) != 0) ? (z2Prime ^ 0xb729fcec) : z2Prime; + final int z4 = z0 ^ (z1 ^ (z1 >>> 20)) ^ z2Second ^ z3; + + v[index] = z3; + v[indexRm1] = z4; + v[indexRm2] &= 0xFFFF8000; + index = indexRm1; + + return z4; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497b.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497b.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497b.java new file mode 100644 index 0000000..983b0d2 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well44497b.java @@ -0,0 +1,56 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +/** + * This class implements the WELL44497b pseudo-random number generator + * from François Panneton, Pierre L'Ecuyer and Makoto Matsumoto. + * <p> + * This generator is described in a paper by François Panneton, + * Pierre L'Ecuyer and Makoto Matsumoto + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf";> + * Improved Long-Period Generators Based on Linear Recurrences Modulo 2</a> + * ACM Transactions on Mathematical Software, 32, 1 (2006). + * The errata for the paper are in + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt";>wellrng-errata.txt</a>. + * </p> + * + * @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html";>WELL Random number generator</a> + * @since 1.0 + */ +public class Well44497b extends Well44497a { + /** + * Creates a new random number generator. + * + * @param seed Initial seed. + */ + public Well44497b(int[] seed) { + super(seed); + } + + /** {@inheritDoc} */ + @Override + public int next() { + int z4 = super.next(); + + // Matsumoto-Kurita tempering to get a maximally equidistributed generator. + z4 ^= (z4 << 7) & 0x93dd1400; + z4 ^= (z4 << 15) & 0xfa118000; + + return z4; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well512a.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well512a.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well512a.java new file mode 100644 index 0000000..ed01735 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/Well512a.java @@ -0,0 +1,78 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.internal.source32; + +/** + * This class implements the WELL512a pseudo-random number generator + * from François Panneton, Pierre L'Ecuyer and Makoto Matsumoto. + * <p> + * This generator is described in a paper by François Panneton, + * Pierre L'Ecuyer and Makoto Matsumoto + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng.pdf";> + * Improved Long-Period Generators Based on Linear Recurrences Modulo 2</a> + * ACM Transactions on Mathematical Software, 32, 1 (2006). + * The errata for the paper are in + * <a href="http://www.iro.umontreal.ca/~lecuyer/myftp/papers/wellrng-errata.txt";>wellrng-errata.txt</a>. + * </p> + * + * @see <a href="http://www.iro.umontreal.ca/~panneton/WELLRNG.html";>WELL Random number generator</a> + * @since 1.0 + */ +public class Well512a extends AbstractWell { + /** Number of bits in the pool. */ + private static final int K = 512; + /** First parameter of the algorithm. */ + private static final int M1 = 13; + /** Second parameter of the algorithm. */ + private static final int M2 = 9; + /** Third parameter of the algorithm. */ + private static final int M3 = 5; + /** The indirection index table. */ + private static final IndexTable TABLE = new IndexTable(K, M1, M2, M3); + + /** + * Creates a new random number generator. + * + * @param seed Initial seed. + */ + public Well512a(int[] seed) { + super(K, seed); + } + + /** {@inheritDoc} */ + @Override + public int next() { + final int indexRm1 = TABLE.getIndexPred(index); + + final int vi = v[index]; + final int vi1 = v[TABLE.getIndexM1(index)]; + final int vi2 = v[TABLE.getIndexM2(index)]; + final int z0 = v[indexRm1]; + + // the values below include the errata of the original article + final int z1 = (vi ^ (vi << 16)) ^ (vi1 ^ (vi1 << 15)); + final int z2 = vi2 ^ (vi2 >>> 11); + final int z3 = z1 ^ z2; + final int z4 = (z0 ^ (z0 << 2)) ^ (z1 ^ (z1 << 18)) ^ (z2 << 28) ^ (z3 ^ ((z3 << 5) & 0xda442d24)); + + v[index] = z3; + v[indexRm1] = z4; + index = indexRm1; + + return z4; + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/42530e25/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/package-info.java ---------------------------------------------------------------------- diff --git a/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/package-info.java b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/package-info.java new file mode 100644 index 0000000..e814765 --- /dev/null +++ b/commons-rng-core/src/main/java/org/apache/commons/rng/internal/source32/package-info.java @@ -0,0 +1,52 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * <h3> + * Concrete algorithms for {@code int}-based sources of randomness + * </h3> + * + * <p> + * <b>For internal use only:</b> Direct access to classes in this package + * is discouraged, as they could be modified without notice. + * </p> + * + * <p><b>Notes for developers</b></p> + * + * <ul> + * <li> + * A source of randomness must inherit from + * {@link org.apache.commons.rng.internal.source32.IntProvider} + * </li> + * <li> + * The "provider" must specify <em>one</em> way for setting the seed. + * For a given seed, the generated sequence must always be the same. + * </li> + * <li> + * The "provider" must implement methods {@code getStateInternal} and + * {@code setStateInternal} in order to save and restore the state of an + * instance (cf. {@link org.apache.commons.rng.internal.BaseProvider}). + * </li> + * <li> + * When a new class is implemented here, user-access to it must be provided + * through associated {@link org.apache.commons.rng.RandomSource + * factory methods}. + * </li> + * </ul> + */ + +package org.apache.commons.rng.internal.source32;
