You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2022/03/17 22:38:21 UTC
[commons-rng] 01/07: RNG-169: Expand primitive input seeds using a SplitMix64
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 <ah...@apache.org>
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));
}
}