This is an automated email from the ASF dual-hosted git repository. aherbert pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-rng.git
commit ef9722b5dcce2e23c250deadbed8589893d82845 Author: Alex Herbert <[email protected]> AuthorDate: Thu Mar 17 09:26:14 2022 +0000 RNG-169: Expand primitive input seeds using a SplitMix64 This changes behaviour so that if int == long: int -> array1 long -> array2 array1 == array2 int -> array[0] == int -> long --- .../commons/rng/simple/internal/Conversions.java | 120 +++++++++++++++++++++ .../commons/rng/simple/internal/Int2Long.java | 5 +- .../commons/rng/simple/internal/Long2IntArray.java | 34 +----- .../rng/simple/internal/Long2LongArray.java | 26 +---- .../rng/simple/internal/NativeSeedType.java | 18 ++-- .../rng/simple/internal/ConversionsTest.java | 70 ++++++++++++ .../rng/simple/internal/NativeSeedTypeTest.java | 50 +++++++-- 7 files changed, 244 insertions(+), 79 deletions(-) diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java index 3b00f6a..140f59d 100644 --- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java +++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Conversions.java @@ -27,10 +27,130 @@ package org.apache.commons.rng.simple.internal; * @since 1.5 */ final class Conversions { + /** + * The fractional part of the the golden ratio, phi, scaled to 64-bits and rounded to odd. + * <pre> + * phi = (sqrt(5) - 1) / 2) * 2^64 + * </pre> + * @see <a href="https://en.wikipedia.org/wiki/Golden_ratio";>Golden ratio</a> + */ + private static final long GOLDEN_RATIO = 0x9e3779b97f4a7c15L; + /** No instances. */ private Conversions() {} /** + * Perform variant 13 of David Stafford's 64-bit mix function. + * This is the mix function used in the {@link SplitMix64} RNG. + * + * <p>This is ranked first of the top 14 Stafford mixers. + * + * @param x the input value + * @return the output value + * @see <a href="http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html";>Better + * Bit Mixing - Improving on MurmurHash3's 64-bit Finalizer.</a> + */ + private static long stafford13(long x) { + x = (x ^ (x >>> 30)) * 0xbf58476d1ce4e5b9L; + x = (x ^ (x >>> 27)) * 0x94d049bb133111ebL; + return x ^ (x >>> 31); + } + + /** + * Creates a {@code long} value from an {@code int}. The conversion + * is made as if seeding a SplitMix64 RNG and calling nextLong(). + * + * @param input Input + * @return a {@code long}. + */ + static long int2long(int input) { + return stafford13(input + GOLDEN_RATIO); + } + + /** + * Creates an {@code int[]} value from an {@code int}. The conversion + * is made as if seeding a SplitMix64 RNG and calling nextLong() to + * generate the sequence and filling the ints + * in little-endian order (least significant byte first). + * + * @param input Input + * @param length Array length + * @return an {@code int[]}. + */ + static int[] int2intArray(int input, int length) { + return long2intArray(input, length); + } + + /** + * Creates a {@code long[]} value from an {@code int}. The conversion + * is made as if seeding a SplitMix64 RNG and calling nextLong() to + * generate the sequence. + * + * @param input Input + * @param length Array length + * @return a {@code long[]}. + */ + static long[] int2longArray(int input, int length) { + return long2longArray(input, length); + } + + /** + * Creates an {@code int} value from a {@code long}. The conversion + * is made by xoring the upper and lower bits. + * + * @param input Input + * @return an {@code int}. + */ + static int long2int(long input) { + return (int) input ^ (int) (input >>> 32); + } + + /** + * Creates an {@code int[]} value from a {@code long}. The conversion + * is made as if seeding a SplitMix64 RNG and calling nextLong() to + * generate the sequence and filling the ints + * in little-endian order (least significant byte first). + * + * @param input Input + * @param length Array length + * @return an {@code int[]}. + */ + static int[] long2intArray(long input, int length) { + long v = input; + final int[] output = new int[length]; + // Process pairs + final int n = length & ~0x1; + for (int i = 0; i < n; i += 2) { + long x = stafford13(v += GOLDEN_RATIO); + output[i] = (int) x; + output[i + 1] = (int) (x >>> 32); + } + // Final value + if (n < length) { + output[n] = (int) stafford13(v + GOLDEN_RATIO); + } + return output; + } + + /** + * Creates a {@code long[]} value from a {@code long}. The conversion + * is made as if seeding a SplitMix64 RNG and calling nextLong() to + * generate the sequence. + * + * @param input Input + * @param length Array length + * @return a {@code long}. + */ + static long[] long2longArray(long input, int length) { + long v = input; + final long[] output = new long[length]; + for (int i = 0; i < length; i++) { + output[i] = stafford13(v += GOLDEN_RATIO); + } + return output; + } + + /** * Creates an {@code int} value from a sequence of bytes. The conversion * is made as if converting to a {@code int[]} array by filling the ints * in little-endian order (least significant byte first), then combining diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Int2Long.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Int2Long.java index e614bec..cd1c207 100644 --- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Int2Long.java +++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Int2Long.java @@ -16,8 +16,6 @@ */ package org.apache.commons.rng.simple.internal; -import org.apache.commons.rng.core.util.NumberFactory; - /** * Converts a {@code Integer} to an {@code Long}. * @@ -27,7 +25,6 @@ public class Int2Long implements SeedConverter<Integer, Long> { /** {@inheritDoc} */ @Override public Long convert(Integer seed) { - final int s = seed; - return NumberFactory.makeLong(s, ~s); + return Conversions.int2long(seed); } } diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2IntArray.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2IntArray.java index 47866b2..352ca50 100644 --- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2IntArray.java +++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2IntArray.java @@ -16,11 +16,9 @@ */ package org.apache.commons.rng.simple.internal; -import org.apache.commons.rng.core.source64.SplitMix64; -import org.apache.commons.rng.core.util.NumberFactory; - /** - * Uses a {@code long} value to seed a {@link SplitMix64} RNG and + * Uses a {@code long} value to seed a + * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64} RNG and * create a {@code int[]} with the requested number of random * values. * @@ -40,7 +38,7 @@ public class Long2IntArray implements Seed2ArrayConverter<Long, int[]> { /** {@inheritDoc} */ @Override public int[] convert(Long seed) { - return convertSeed(seed, size); + return Conversions.long2intArray(seed, size); } /** @@ -50,30 +48,6 @@ public class Long2IntArray implements Seed2ArrayConverter<Long, int[]> { */ @Override public int[] convert(Long seed, int outputSize) { - return convertSeed(seed, outputSize); - } - - /** - * Convert the seed. - * - * @param seed Input seed. - * @param size Output array size. - * @return the converted seed. - */ - private static int[] convertSeed(Long seed, int size) { - final int[] out = new int[size]; - final SplitMix64 rng = new SplitMix64(seed); - // Fill pairs of ints from a long. - // The array is filled from the end towards the start. - for (int i = size - 1; i > 0; i -= 2) { - final long v = rng.nextLong(); - out[i] = NumberFactory.extractHi(v); - out[i - 1] = NumberFactory.extractLo(v); - } - // An odd size requires a final single int at the start - if ((size & 1) == 1) { - out[0] = NumberFactory.extractHi(rng.nextLong()); - } - return out; + return Conversions.long2intArray(seed, outputSize); } } diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2LongArray.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2LongArray.java index e219b45..1806ca9 100644 --- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2LongArray.java +++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/Long2LongArray.java @@ -16,10 +16,9 @@ */ package org.apache.commons.rng.simple.internal; -import org.apache.commons.rng.core.source64.SplitMix64; - /** - * Uses a {@code Long} value to seed a {@link SplitMix64} RNG and + * Uses a {@code Long} value to seed a + * {@link org.apache.commons.rng.core.source64.SplitMix64 SplitMix64} RNG and * create a {@code long[]} with the requested number of random * values. * @@ -40,7 +39,7 @@ public class Long2LongArray implements Seed2ArrayConverter<Long, long[]> { /** {@inheritDoc} */ @Override public long[] convert(Long seed) { - return convertSeed(seed, size); + return Conversions.long2longArray(seed, size); } /** @@ -50,23 +49,6 @@ public class Long2LongArray implements Seed2ArrayConverter<Long, long[]> { */ @Override public long[] convert(Long seed, int outputSize) { - return convertSeed(seed, outputSize); - } - - /** - * Convert the seed. - * - * @param seed Input seed. - * @param size Output array size. - * @return the converted seed. - */ - private static long[] convertSeed(Long seed, int size) { - final long[] out = new long[size]; - final SplitMix64 rng = new SplitMix64(seed); - for (int i = 0; i < size; i++) { - out[i] = rng.nextLong(); - } - - return out; + return Conversions.long2longArray(seed, outputSize); } } diff --git a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java index 9d73da8..6ccc436 100644 --- a/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java +++ b/commons-rng-simple/src/main/java/org/apache/commons/rng/simple/internal/NativeSeedType.java @@ -54,7 +54,7 @@ public enum NativeSeedType { } @Override protected Integer convert(Long seed, int size) { - return LONG_TO_INT.convert(seed); + return Conversions.long2int(seed); } @Override protected Integer convert(int[] seed, int size) { @@ -77,7 +77,7 @@ public enum NativeSeedType { } @Override protected Long convert(Integer seed, int size) { - return INT_TO_LONG.convert(seed); + return Conversions.int2long(seed); } @Override protected Long convert(Long seed, int size) { @@ -106,11 +106,11 @@ public enum NativeSeedType { } @Override protected int[] convert(Integer seed, int size) { - return LONG_TO_INT_ARRAY.convert(INT_TO_LONG.convert(seed), size); + return Conversions.int2intArray(seed, size); } @Override protected int[] convert(Long seed, int size) { - return LONG_TO_INT_ARRAY.convert(seed, size); + return Conversions.long2intArray(seed, size); } @Override protected int[] convert(int[] seed, int size) { @@ -139,11 +139,11 @@ public enum NativeSeedType { } @Override protected long[] convert(Integer seed, int size) { - return LONG_TO_LONG_ARRAY.convert(INT_TO_LONG.convert(seed), size); + return Conversions.int2longArray(seed, size); } @Override protected long[] convert(Long seed, int size) { - return LONG_TO_LONG_ARRAY.convert(seed, size); + return Conversions.long2longArray(seed, size); } @Override protected long[] convert(int[] seed, int size) { @@ -169,12 +169,6 @@ public enum NativeSeedType { private static final int RANDOM_SEED_ARRAY_SIZE = 128; /** Convert {@code Long} to {@code Integer}. */ private static final Long2Int LONG_TO_INT = new Long2Int(); - /** Convert {@code Integer} to {@code Long}. */ - private static final Int2Long INT_TO_LONG = new Int2Long(); - /** Convert {@code Long} to {@code int[]}. */ - private static final Long2IntArray LONG_TO_INT_ARRAY = new Long2IntArray(0); - /** Convert {@code Long} to {@code long[]}. */ - private static final Long2LongArray LONG_TO_LONG_ARRAY = new Long2LongArray(0); /** Convert {@code long[]} to {@code Long}. */ private static final LongArray2Long LONG_ARRAY_TO_LONG = new LongArray2Long(); /** Convert {@code int[]} to {@code Integer}. */ diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/ConversionsTest.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/ConversionsTest.java index de0bc89..840eefd 100644 --- a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/ConversionsTest.java +++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/ConversionsTest.java @@ -22,7 +22,11 @@ import java.nio.ByteOrder; import java.util.Arrays; import java.util.concurrent.ThreadLocalRandom; import java.util.stream.IntStream; +import java.util.stream.LongStream; +import org.apache.commons.rng.core.source64.SplitMix64; +import org.apache.commons.rng.core.util.NumberFactory; import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.RepeatedTest; import org.junit.jupiter.params.ParameterizedTest; import org.junit.jupiter.params.provider.MethodSource; @@ -48,6 +52,72 @@ class ConversionsTest { return IntStream.rangeClosed(0, (Long.BYTES / Integer.BYTES) * 2); } + @RepeatedTest(value = 5) + void testInt2Long() { + final int v = ThreadLocalRandom.current().nextInt(); + Assertions.assertEquals(new SplitMix64(v).nextLong(), Conversions.int2long(v)); + } + + @RepeatedTest(value = 5) + void testInt2IntArray() { + final int v = ThreadLocalRandom.current().nextInt(); + getIntLengths().forEach(len -> { + Assertions.assertArrayEquals(Conversions.long2intArray(v, len), + Conversions.int2intArray(v, len)); + }); + } + + @RepeatedTest(value = 5) + void testInt2LongArray() { + final int v = ThreadLocalRandom.current().nextInt(); + getIntLengths().forEach(len -> { + final long[] a = Conversions.int2longArray(v, len); + Assertions.assertArrayEquals(Conversions.long2longArray(v, len), a); + if (len != 0) { + // Special case of expansion to length 1 + // Expandion is done by mixing + Assertions.assertEquals(Conversions.int2long(v), a[0]); + } + }); + } + + @RepeatedTest(value = 5) + void testLong2Int() { + final long v = ThreadLocalRandom.current().nextLong(); + Assertions.assertEquals(NumberFactory.makeInt(v), Conversions.long2int(v)); + } + + @RepeatedTest(value = 5) + void testLong2IntArray() { + final long v = ThreadLocalRandom.current().nextLong(); + getIntLengths().forEach(len -> { + final int longs = SeedUtils.longSizeFromIntSize(len); + // Little-endian conversion + final ByteBuffer bb = ByteBuffer.allocate(longs * Long.BYTES).order(ByteOrder.LITTLE_ENDIAN); + LongStream.generate(new SplitMix64(v)::nextLong).limit(longs).forEach(bb::putLong); + bb.clear(); + final int[] expected = new int[len]; + for (int i = 0; i < len; i++) { + expected[i] = bb.getInt(); + } + Assertions.assertArrayEquals(expected, + Conversions.long2intArray(v, len)); + + // Note: + // long -> int[] position[0] != long -> int + // Reduction is done by folding upper and lower using xor + }); + } + + @RepeatedTest(value = 5) + void testLong2LongArray() { + final long v = ThreadLocalRandom.current().nextLong(); + getIntLengths().forEach(len -> { + Assertions.assertArrayEquals(LongStream.generate(new SplitMix64(v)::nextLong).limit(len).toArray(), + Conversions.long2longArray(v, len)); + }); + } + @ParameterizedTest @MethodSource(value = {"getIntLengths"}) void testByteArray2Int(int bytes) { diff --git a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeTest.java b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeTest.java index aae91cb..c81b51e 100644 --- a/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeTest.java +++ b/commons-rng-simple/src/test/java/org/apache/commons/rng/simple/internal/NativeSeedTypeTest.java @@ -45,7 +45,7 @@ class NativeSeedTypeTest { /** * Perform the reference int to long conversion. * This may change between release versions. - * The reference implementation is in the Int2LongConverter. + * The reference implementation is in the Int2Long converter. * * @param v Value * @return the result @@ -57,7 +57,7 @@ class NativeSeedTypeTest { /** * Perform the reference long to int[] conversion. * This may change between release versions. - * The reference implementation is in the Long2IntArray. + * The reference implementation is in the Long2IntArray converter. * * @param v Value * @param length Array length @@ -70,7 +70,7 @@ class NativeSeedTypeTest { /** * Perform the reference long to long[] conversion. * This may change between release versions. - * The reference implementation is in the Long2LongArray. + * The reference implementation is in the Long2LongArray converter. * * @param v Value * @param length Array length @@ -278,6 +278,9 @@ class NativeSeedTypeTest { // The Long2LongArray converter is the reference implementation. // - long to int[] conversion seeds a RNG then expands. // The Long2IntArray converter is the reference implementation. + // - Primitive expansion should produce equivalent output bits + // for all larger output seed types, + // i.e. int -> long == int -> int[0]+int[1] == int -> long[0] // - int[] to int conversion uses ^ of all the bits // - long[] to long conversion uses ^ of all the bits // - Array-to-array conversions are little-endian. @@ -302,14 +305,14 @@ class NativeSeedTypeTest { // byte[] -> F long[] -> int // // int[] - // int -> long -> int[] + // int -> int[] // long -> int[] // int[] -> int[] // long[] -> T int[] // byte[] -> T int[] // // int[] - // int -> long -> long[] + // int -> long[] // long -> long[] // int[] -> T long[] // long[] -> long[] @@ -318,8 +321,33 @@ class NativeSeedTypeTest { // Notes: // 1. The actual implementation may be optimised to avoid redundant steps. // 2. Primitive type native seed use all bits from an array (F). - // 3. Array type native seed use only the initial n bytes from an array (T) required + // 3. Array type native seeds use only the initial n bytes from an array (T) required // to satisfy the native seed length n + // 4. Expansion of primitive seeds to a different native type should be consistent. + // Seeding an integer to create an int[] should match the byte output of + // using the same integer (or long) to create a long[] of equivalent length + + @ParameterizedTest + @MethodSource(value = {"getIntSeeds"}) + void testPrimitiveSeedExpansion(int seed) { + for (int i = 1; i < 3; i++) { + final long l1 = (Long) NativeSeedType.LONG.convert(seed, i); + final int[] ia1 = (int[]) NativeSeedType.INT_ARRAY.convert(seed, i * 2); + final long[] la1 = (long[]) NativeSeedType.LONG_ARRAY.convert(seed, i); + final int[] ia2 = (int[]) NativeSeedType.INT_ARRAY.convert(Long.valueOf(seed), i * 2); + final long[] la2 = (long[]) NativeSeedType.LONG_ARRAY.convert(Long.valueOf(seed), i); + Assertions.assertEquals(i, la1.length); + Assertions.assertEquals(l1, la1[0], "int -> long != int -> long[0]"); + Assertions.assertArrayEquals(ia1, ia2, "int -> int[] != long -> int[]"); + Assertions.assertArrayEquals(la1, la2, "int -> long[] != long -> long[]"); + final ByteBuffer bb = ByteBuffer.allocate(i * Long.BYTES).order(ByteOrder.LITTLE_ENDIAN); + Arrays.stream(ia1).forEach(bb::putInt); + bb.flip(); + for (int j = 0; j < i; j++) { + Assertions.assertEquals(bb.getLong(), la1[j]); + } + } + } @ParameterizedTest @MethodSource(value = {"getIntSeeds"}) @@ -333,7 +361,7 @@ class NativeSeedTypeTest { @ParameterizedTest @MethodSource(value = {"getIntSeeds"}) - void testIntNativeSeedWithInt(long seed) { + void testIntNativeSeedWithLong(long seed) { // Primitive conversion: Note: >>> takes precendence over ^ final Integer l = (int) (seed ^ seed >>> 32); for (int i = 0; i < 3; i++) { @@ -429,9 +457,9 @@ class NativeSeedTypeTest { @MethodSource(value = {"getIntSeeds"}) void testIntArrayNativeSeedWithInt(int seed) { // Full-length conversion - final long l = int2long(seed); for (int i = 0; i < 3; i++) { - Assertions.assertArrayEquals(long2intArray(l, i), + // Note: int seed is expanded using the same method as a long seed + Assertions.assertArrayEquals(long2intArray(seed, i), (int[]) NativeSeedType.INT_ARRAY.convert(seed, i)); } } @@ -492,9 +520,9 @@ class NativeSeedTypeTest { @MethodSource(value = {"getIntSeeds"}) void testLongArrayNativeSeedWithInt(int seed) { // Full-length conversion - final long l = int2long(seed); for (int i = 0; i < 3; i++) { - Assertions.assertArrayEquals(long2longArray(l, i), + // Note: int seed is expanded using the same method as a long seed + Assertions.assertArrayEquals(long2longArray(seed, i), (long[]) NativeSeedType.LONG_ARRAY.convert(seed, i)); } }
