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 */
017package org.apache.commons.rng.core.source64;
018
019import org.apache.commons.rng.core.util.NumberFactory;
020
021/**
022 * A Permuted Congruential Generator (PCG) that is composed of a 64-bit Linear Congruential
023 * Generator (LCG) combined with the RXS-M-XS (random xorshift; multiply; xorshift) output
024 * transformation to create 64-bit output.
025 *
026 * <p>State size is 128 bits and the period is 2<sup>64</sup>.</p>
027 *
028 * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
029 * effective: in effect, two seeds that only differ by the last 64 bits may produce
030 * highly correlated sequences.
031 *
032 * @see <a href="http://www.pcg-random.org/">
033 *  PCG, A Family of Better Random Number Generators</a>
034 * @since 1.3
035 */
036public class PcgRxsMXs64 extends LongProvider {
037    /** Size of the seed array. */
038    private static final int SEED_SIZE = 2;
039    /** The default increment. */
040    private static final long DEFAULT_INCREMENT = 1442695040888963407L;
041
042    /** The state of the LCG. */
043    private long state;
044
045    /** The increment of the LCG. */
046    private long increment;
047
048    /**
049     * Creates a new instance using a default increment.
050     *
051     * @param seed Initial state.
052     * @since 1.4
053     */
054    public PcgRxsMXs64(Long seed) {
055        increment = DEFAULT_INCREMENT;
056        state = bump(seed + this.increment);
057    }
058
059    /**
060     * Creates a new instance.
061     *
062     * <p><strong>Note:</strong> Although the seed size is 128 bits, only the first 64 are
063     * effective: in effect, two seeds that only differ by the last 64 bits may produce
064     * highly correlated sequences.
065     *
066     * @param seed Initial seed.
067     * If the length is larger than 2, only the first 2 elements will
068     * be used; if smaller, the remaining elements will be automatically set.
069     *
070     * <p>The 1st element is used to set the LCG state. The 2nd element is used
071     * to set the LCG increment; the most significant bit
072     * is discarded by left shift and the increment is set to odd.</p>
073     */
074    public PcgRxsMXs64(long[] seed) {
075        if (seed.length < SEED_SIZE) {
076            final long[] tmp = new long[SEED_SIZE];
077            fillState(tmp, seed);
078            setSeedInternal(tmp);
079        } else {
080            setSeedInternal(seed);
081        }
082    }
083
084    /**
085     * Seeds the RNG.
086     *
087     * @param seed Seed.
088     */
089    private void setSeedInternal(long[] seed) {
090        // Ensure the increment is odd to provide a maximal period LCG.
091        this.increment = (seed[1] << 1) | 1;
092        this.state = bump(seed[0] + this.increment);
093    }
094
095    /**
096     * Provides the next state of the LCG.
097     *
098     * @param input Current state.
099     * @return next state
100     */
101    private long bump(long input) {
102        return input * 6364136223846793005L + increment;
103    }
104
105    /** {@inheritDoc} */
106    @Override
107    public long next() {
108        final long x = state;
109        state = bump(state);
110        final long word = ((x >>> ((x >>> 59) + 5)) ^ x) * -5840758589994634535L;
111        return (word >>> 43) ^ word;
112    }
113
114    /** {@inheritDoc} */
115    @Override
116    protected byte[] getStateInternal() {
117        // The increment is divided by 2 before saving.
118        // This transform is used in the reference PCG code; it prevents restoring from
119        // a byte state a non-odd increment that results in a sub-maximal period generator.
120        return composeStateInternal(NumberFactory.makeByteArray(
121                new long[] {state, increment >>> 1}),
122                super.getStateInternal());
123    }
124
125    /** {@inheritDoc} */
126    @Override
127    protected void setStateInternal(byte[] s) {
128        final byte[][] c = splitStateInternal(s, SEED_SIZE * 8);
129        final long[] tempseed = NumberFactory.makeLongArray(c[0]);
130        state = tempseed[0];
131        // Reverse the transform performed during getState to make the increment odd again.
132        increment = tempseed[1] << 1 | 1;
133        super.setStateInternal(c[1]);
134    }
135}