L32X64Mix.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */

  18. package org.apache.commons.rng.core.source32;

  20. import java.util.stream.Stream;
  21. import org.apache.commons.rng.JumpableUniformRandomProvider;
  22. import org.apache.commons.rng.LongJumpableUniformRandomProvider;
  23. import org.apache.commons.rng.SplittableUniformRandomProvider;
  24. import org.apache.commons.rng.UniformRandomProvider;
  25. import org.apache.commons.rng.core.util.NumberFactory;
  26. import org.apache.commons.rng.core.util.RandomStreams;

  28. /**
  29.  * A 32-bit all purpose generator.
  30.  *
  31.  * <p>This is a member of the LXM family of generators: L=Linear congruential generator;
  32.  * X=Xor based generator; and M=Mix. This member uses a 32-bit LCG and 64-bit Xor-based
  33.  * generator. It is named as {@code "L32X64MixRandom"} in the {@code java.util.random}
  34.  * package introduced in JDK 17; the LXM family is described in further detail in:
  35.  *
  36.  * <blockquote>Steele and Vigna (2021) LXM: better splittable pseudorandom number generators
  37.  * (and almost as fast). Proceedings of the ACM on Programming Languages, Volume 5,
  38.  * Article 148, pp 1–31.</blockquote>
  39.  *
  40.  * <p>Memory footprint is 128 bits and the period is 2<sup>32</sup> (2<sup>64</sup> - 1).
  41.  *
  42.  * <p>This generator implements {@link LongJumpableUniformRandomProvider}.
  43.  * In addition instances created with a different additive parameter for the LCG are robust
  44.  * against accidental correlation in a multi-threaded setting. The additive parameters must be
  45.  * different in the most significant 31-bits.
  46.  *
  47.  * <p>This generator implements
  48.  * {@link org.apache.commons.rng.SplittableUniformRandomProvider SplittableUniformRandomProvider}.
  49.  * The stream of generators created using the {@code splits} methods support parallelisation
  50.  * and are robust against accidental correlation by using unique values for the additive parameter
  51.  * for each instance in the same stream. The primitive streaming methods support parallelisation
  52.  * but with no assurances of accidental correlation; each thread uses a new instance with a
  53.  * randomly initialised state.
  54.  *
  55.  * @see <a href="https://doi.org/10.1145/3485525">Steele &amp; Vigna (2021) Proc. ACM Programming
  56.  *      Languages 5, 1-31</a>
  57.  * @see <a href="https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/random/package-summary.html">
  58.  *      JDK 17 java.util.random javadoc</a>
  59.  * @since 1.5
  60.  */
  61. public final class L32X64Mix extends IntProvider implements LongJumpableUniformRandomProvider,
  62.     SplittableUniformRandomProvider {
  63.     // Implementation note:
  64.     // This does not extend AbstractXoRoShiRo64 as the XBG function is re-implemented
  65.     // inline to allow parallel pipelining. Inheritance would provide only the XBG state.

  67.     /** LCG multiplier. */
  68.     private static final int M = LXMSupport.M32;
  69.     /** Size of the state vector. */
  70.     private static final int SEED_SIZE = 4;

  72.     /** Per-instance LCG additive parameter (must be odd).
  73.      * Cannot be final to support RestorableUniformRandomProvider. */
  74.     private int la;
  75.     /** State of the LCG generator. */
  76.     private int ls;
  77.     /** State 0 of the XBG generator. */
  78.     private int x0;
  79.     /** State 1 of the XBG generator. */
  80.     private int x1;

  82.     /**
  83.      * Creates a new instance.
  84.      *
  85.      * @param seed Initial seed.
  86.      * If the length is larger than 4, only the first 4 elements will
  87.      * be used; if smaller, the remaining elements will be automatically
  88.      * set. A seed containing all zeros in the last two elements
  89.      * will create a non-functional XBG sub-generator and a low
  90.      * quality output with a period of 2<sup>32</sup>.
  91.      *
  92.      * <p>The 1st element is used to set the LCG increment; the least significant bit
  93.      * is set to odd to ensure a full period LCG. The 2nd element is used
  94.      * to set the LCG state.</p>
  95.      */
  96.     public L32X64Mix(int[] seed) {
  97.         setState(extendSeed(seed, SEED_SIZE));
  98.     }

  100.     /**
  101.      * Creates a new instance using a 4 element seed.
  102.      * A seed containing all zeros in the last two elements
  103.      * will create a non-functional XBG sub-generator and a low
  104.      * quality output with a period of 2<sup>32</sup>.
  105.      *
  106.      * <p>The 1st element is used to set the LCG increment; the least significant bit
  107.      * is set to odd to ensure a full period LCG. The 2nd element is used
  108.      * to set the LCG state.</p>
  109.      *
  110.      * @param seed0 Initial seed element 0.
  111.      * @param seed1 Initial seed element 1.
  112.      * @param seed2 Initial seed element 2.
  113.      * @param seed3 Initial seed element 3.
  114.      */
  115.     public L32X64Mix(int seed0, int seed1, int seed2, int seed3) {
  116.         // Additive parameter must be odd
  117.         la = seed0 | 1;
  118.         ls = seed1;
  119.         x0 = seed2;
  120.         x1 = seed3;
  121.     }

  123.     /**
  124.      * Creates a copy instance.
  125.      *
  126.      * @param source Source to copy.
  127.      */
  128.     private L32X64Mix(L32X64Mix source) {
  129.         super(source);
  130.         la = source.la;
  131.         ls = source.ls;
  132.         x0 = source.x0;
  133.         x1 = source.x1;
  134.     }

  136.     /**
  137.      * Copies the state into the generator state.
  138.      *
  139.      * @param state the new state
  140.      */
  141.     private void setState(int[] state) {
  142.         // Additive parameter must be odd
  143.         la = state[0] | 1;
  144.         ls = state[1];
  145.         x0 = state[2];
  146.         x1 = state[3];
  147.     }

  149.     /** {@inheritDoc} */
  150.     @Override
  151.     protected byte[] getStateInternal() {
  152.         return composeStateInternal(NumberFactory.makeByteArray(new int[] {la, ls, x0, x1}),
  153.                                     super.getStateInternal());
  154.     }

  156.     /** {@inheritDoc} */
  157.     @Override
  158.     protected void setStateInternal(byte[] s) {
  159.         final byte[][] c = splitStateInternal(s, SEED_SIZE * Integer.BYTES);
  160.         setState(NumberFactory.makeIntArray(c[0]));
  161.         super.setStateInternal(c[1]);
  162.     }

  164.     /** {@inheritDoc} */
  165.     @Override
  166.     public int next() {
  167.         // LXM generate.
  168.         // Old state is used for the output allowing parallel pipelining
  169.         // on processors that support multiple concurrent instructions.

  171.         final int s0 = x0;
  172.         final int s = ls;

  174.         // Mix
  175.         final int z = LXMSupport.lea32(s + s0);

  177.         // LCG update
  178.         ls = M * s + la;

  180.         // XBG update
  181.         int s1 = x1;

  183.         s1 ^= s0;
  184.         x0 = Integer.rotateLeft(s0, 26) ^ s1 ^ (s1 << 9); // a, b
  185.         x1 = Integer.rotateLeft(s1, 13); // c

  187.         return z;
  188.     }

  190.     /**
  191.      * Creates a copy of the UniformRandomProvider and then <em>retreats</em> the state of the
  192.      * current instance. The copy is returned.
  193.      *
  194.      * <p>The jump is performed by advancing the state of the LCG sub-generator by 1 cycle.
  195.      * The XBG state is unchanged. The jump size is the equivalent of moving the state
  196.      * <em>backwards</em> by (2<sup>64</sup> - 1) positions. It can provide up to 2<sup>32</sup>
  197.      * non-overlapping subsequences.</p>
  198.      */
  199.     @Override
  200.     public UniformRandomProvider jump() {
  201.         final UniformRandomProvider copy = new L32X64Mix(this);
  202.         // Advance the LCG 1 step
  203.         ls = M * ls + la;
  204.         resetCachedState();
  205.         return copy;
  206.     }

  208.     /**
  209.      * Creates a copy of the UniformRandomProvider and then <em>retreats</em> the state of the
  210.      * current instance. The copy is returned.
  211.      *
  212.      * <p>The jump is performed by advancing the state of the LCG sub-generator by
  213.      * 2<sup>16</sup> cycles. The XBG state is unchanged. The jump size is the equivalent
  214.      * of moving the state <em>backwards</em> by 2<sup>16</sup> (2<sup>64</sup> - 1)
  215.      * positions. It can provide up to 2<sup>16</sup> non-overlapping subsequences of
  216.      * length 2<sup>16</sup> (2<sup>64</sup> - 1); each subsequence can provide up to
  217.      * 2<sup>16</sup> non-overlapping subsequences of length (2<sup>64</sup> - 1) using
  218.      * the {@link #jump()} method.</p>
  219.      */
  220.     @Override
  221.     public JumpableUniformRandomProvider longJump() {
  222.         final JumpableUniformRandomProvider copy = new L32X64Mix(this);
  223.         // Advance the LCG 2^16 steps
  224.         ls = LXMSupport.M32P * ls + LXMSupport.C32P * la;
  225.         resetCachedState();
  226.         return copy;
  227.     }

  229.     /** {@inheritDoc} */
  230.     @Override
  231.     public SplittableUniformRandomProvider split(UniformRandomProvider source) {
  232.         // The upper half of the long seed is discarded so use nextInt
  233.         return create(source.nextInt(), source);
  234.     }

  236.     /** {@inheritDoc} */
  237.     @Override
  238.     public Stream<SplittableUniformRandomProvider> splits(long streamSize, SplittableUniformRandomProvider source) {
  239.         return RandomStreams.generateWithSeed(streamSize, source, L32X64Mix::create);
  240.     }

  242.     /**
  243.      * Create a new instance using the given {@code seed} and {@code source} of randomness
  244.      * to initialise the instance.
  245.      *
  246.      * @param seed Seed used to initialise the instance.
  247.      * @param source Source of randomness used to initialise the instance.
  248.      * @return A new instance.
  249.      */
  250.     private static SplittableUniformRandomProvider create(long seed, UniformRandomProvider source) {
  251.         // LCG state. The addition uses the input seed.
  252.         // The LCG addition parameter is set to odd so left-shift the seed.
  253.         final int s0 = (int) seed << 1;
  254.         final int s1 = source.nextInt();
  255.         // XBG state must not be all zero
  256.         int x0 = source.nextInt();
  257.         int x1 = source.nextInt();
  258.         if ((x0 | x1) == 0) {
  259.             // SplitMix style seed ensures at least one non-zero value
  260.             x0 = LXMSupport.lea32(s1);
  261.             x1 = LXMSupport.lea32(s1 + LXMSupport.GOLDEN_RATIO_32);
  262.         }
  263.         return new L32X64Mix(s0, s1, x0, x1);
  264.     }
  265. }
Created with JaCoCo 0.8.12.202403310830Code Coverage Report for Apache Commons RNG 1.6