MiddleSquareWeylSequence.java

/*
 * 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.core.source32;

import org.apache.commons.rng.core.util.NumberFactory;

import java.util.Arrays;

/**
 * Middle Square Weyl Sequence Random Number Generator.
 *
 * <p>A fast all-purpose 32-bit generator. Memory footprint is 192 bits and the period is at least
 * {@code 2^64}.</p>
 *
 * <p>Implementation is based on the paper
 * <a href="https://arxiv.org/abs/1704.00358v3">Middle Square Weyl Sequence RNG</a>.</p>
 *
 * @see <a href="https://en.wikipedia.org/wiki/Middle-square_method">Middle Square Method</a>
 * @since 1.3
 */
public class MiddleSquareWeylSequence extends IntProvider {
    /** Size of the seed array. */
    private static final int SEED_SIZE = 3;
    /**
     * The default seed.
     * This has a high quality Weyl increment (containing many bit state transitions).
     */
    private static final long[] DEFAULT_SEED =
        {0x012de1babb3c4104L, 0xc8161b4202294965L, 0xb5ad4eceda1ce2a9L};

    /** State of the generator. */
    private long x;
    /** State of the Weyl sequence. */
    private long w;
    /**
     * Increment for the Weyl sequence. This must be odd to ensure a full period.
     *
     * <p>This is not final to support the restore functionality.</p>
     */
    private long s;

    /**
     * Creates a new instance.
     *
     * <p>Note: The generator output quality is highly dependent on the initial seed.
     * If the generator is seeded poorly (for example with all zeros) it is possible the
     * generator may output zero for many cycles before the internal state recovers randomness.
     * The seed elements are used to set:</p>
     *
     * <ol>
     *   <li>The state of the generator
     *   <li>The state of the Weyl sequence
     *   <li>The increment of the Weyl sequence
     * </ol>
     *
     * <p>The third element is set to odd to ensure a period of at least 2<sup>64</sup>. If the
     * increment is of low complexity then the Weyl sequence does not contribute high quality
     * randomness. It is recommended to use a permutation of 8 hex characters for the upper
     * and lower 32-bits of the increment.</p>
     *
     * <p>The state of the generator is squared during each cycle. There is a possibility that
     * different seeds can produce the same output, for example 0 and 2<sup>32</sup> produce
     * the same square. This can be avoided by using the high complexity Weyl increment for the
     * state seed element.</p>
     *
     * @param seed Initial seed.
     * If the length is larger than 3, only the first 3 elements will
     * be used; if smaller, the remaining elements will be automatically set.
     */
    public MiddleSquareWeylSequence(long[] seed) {
        if (seed.length < SEED_SIZE) {
            // Complete the seed with a default to avoid
            // low complexity Weyl increments.
            final long[] tmp = Arrays.copyOf(seed, SEED_SIZE);
            System.arraycopy(DEFAULT_SEED, seed.length, tmp, seed.length, SEED_SIZE - seed.length);
            setSeedInternal(tmp);
        } else {
            setSeedInternal(seed);
        }
    }

    /**
     * Seeds the RNG.
     *
     * @param seed Seed.
     */
    private void setSeedInternal(long[] seed) {
        x = seed[0];
        w = seed[1];
        // Ensure the increment is odd to provide a maximal period Weyl sequence.
        this.s = seed[2] | 1L;
    }

    /** {@inheritDoc} */
    @Override
    protected byte[] getStateInternal() {
        return composeStateInternal(NumberFactory.makeByteArray(new long[] {x, w, s}),
                                    super.getStateInternal());
    }

    /** {@inheritDoc} */
    @Override
    protected void setStateInternal(byte[] state) {
        final byte[][] c = splitStateInternal(state, SEED_SIZE * 8);
        setSeedInternal(NumberFactory.makeLongArray(c[0]));
        super.setStateInternal(c[1]);
    }

    /** {@inheritDoc} */
    @Override
    public int next() {
        x *= x;
        x += w += s;
        x = (x >>> 32) | (x << 32);
        return (int) x;
    }

    /** {@inheritDoc} */
    @Override
    public long nextLong() {
        // Avoid round trip from long to int to long by performing two iterations inline
        x *= x;
        x += w += s;
        final long i1 = x & 0xffffffff00000000L;
        x = (x >>> 32) | (x << 32);
        x *= x;
        x += w += s;
        final long i2 = x >>> 32;
        x = i2 | x << 32;
        return i1 | i2;
    }
}