@@ 62,12 62,17 @@ public static partial class Uniform
if (_range == 0) // 0 is a special case where we sample the entire range.
return unchecked((System.Int128)unsigned);
- while (unsigned > _zone)
+ var zone = _zone;
+
+ while (true)
{
- unsigned = NextUInt128(rng);
+ var (hi, lo) = unsigned.WideningMultiply(_range);
+
+ if (lo <= zone)
+ return unchecked((System.Int128)hi + _low);
+
+ unsigned = rng.NextUInt128();
}
-
- return unchecked((System.Int128)(unsigned % _range) + _low);
}
/// <inheritdoc />
@@ 80,9 85,12 @@ public static partial class Uniform
return true;
}
- if (unsigned <= _zone)
+ var zone = _zone;
+ var (hi, lo) = unsigned.WideningMultiply(_range);
+
+ if (lo <= zone)
{
- result = unchecked((System.Int128)(unsigned % _range) + _low);
+ result = unchecked((System.Int128)hi + _low);
return true;
}
@@ 152,7 160,7 @@ public static partial class Uniform
/// <inheritdoc />
public System.UInt128 Sample<TRng>(TRng rng) where TRng : notnull, IRng
{
- var unsigned = NextUInt128(rng);
+ var unsigned = rng.NextUInt128();
if (_range == 0) // 0 is a special case where we sample the entire range.
return unsigned;
@@ 160,19 168,19 @@ public static partial class Uniform
while (true)
{
- var (hi, lo) = WideningMultiply(unsigned, _range);
+ var (hi, lo) = unsigned.WideningMultiply(_range);
if (lo <= zone)
- return unchecked(_low + hi);
+ return unchecked(hi + _low);
- unsigned = NextUInt128(rng);
+ unsigned = rng.NextUInt128();
}
}
/// <inheritdoc />
public Boolean TrySample<TRng>(TRng rng, out System.UInt128 result) where TRng : notnull, IRng
{
- var unsigned = NextUInt128(rng);
+ var unsigned = rng.NextUInt128();
if (_range == 0) // 0 is a special case where we sample the entire range.
{
result = unsigned;
@@ 180,44 188,17 @@ public static partial class Uniform
}
var zone = _zone;
- var (hi, lo) = WideningMultiply(unsigned, _range);
+ var (hi, lo) = unsigned.WideningMultiply(_range);
if (lo <= zone)
{
- result = unchecked(_low + hi);
+ result = unchecked(hi + _low);
return true;
}
result = default;
return false;
}
-
- private static (System.UInt128, System.UInt128) WideningMultiply(System.UInt128 left, System.UInt128 right)
- {
- System.UInt128 LOWER_MASK = System.UInt128.MaxValue >> 64;
- System.UInt128 low = unchecked((left & LOWER_MASK) * (right & LOWER_MASK));
- System.UInt128 t = low >> 64;
- low &= LOWER_MASK;
- t += unchecked((left >> 64) * (right & LOWER_MASK));
- low += (t & LOWER_MASK) << 64;
- System.UInt128 high = t >> 64;
- t = low >> 64;
- low &= LOWER_MASK;
- t += unchecked((right >> 64) * (left & LOWER_MASK));
- low += (t & LOWER_MASK) << 64;
- high += t >> 64;
- high += unchecked((left >> 64) * (right >> 64));
-
- return (high, low);
- }
-
- private static System.UInt128 NextUInt128<TRng>(TRng rng) where TRng : notnull, IRng
- {
- // Use Little Endian; we explicitly generate one value before the next.
- var x = rng.NextUInt64();
- var y = rng.NextUInt64();
- return new System.UInt128(y, x);
- }
}
}
#endif
@@ 0,0 1,48 @@
+#if NET8_0_OR_GREATER
+using System;
+
+namespace RandN.Distributions;
+
+/// <summary>
+/// Utilities for 128 bit distributions.
+/// </summary>
+internal static class Utils
+{
+ /// <summary>
+ /// Multiplies two <see cref="System.UInt128"/>s and returns the result split into upper and lower bits.
+ /// </summary>
+ /// <param name="left">The left multiplicand.</param>
+ /// <param name="right">The right multiplicand.</param>
+ /// <returns>A tuple of the high bits and the low bits of the multiplication result.</returns>
+ public static (UInt128 hi, UInt128 lo) WideningMultiply(this UInt128 left, UInt128 right)
+ {
+ UInt128 lowerMask = new UInt128(0, UInt64.MaxValue);
+
+ UInt128 low = unchecked((left & lowerMask) * (right & lowerMask));
+ UInt128 t = low >> 64;
+ low &= lowerMask;
+ t += unchecked((left >> 64) * (right & lowerMask));
+ low += (t & lowerMask) << 64;
+ UInt128 high = t >> 64;
+ t = low >> 64;
+ low &= lowerMask;
+ t += unchecked((right >> 64) * (left & lowerMask));
+ low += (t & lowerMask) << 64;
+ high += t >> 64;
+ high += unchecked((left >> 64) * (right >> 64));
+
+ return (high, low);
+ }
+
+ /// <summary>
+ /// Returns the next 128 bits in the RNG as a <see cref="System.UInt128"/>.
+ /// </summary>
+ public static UInt128 NextUInt128<TRng>(this TRng rng) where TRng : notnull, IRng
+ {
+ // Use Little Endian; we explicitly generate one value before the next.
+ var x = rng.NextUInt64();
+ var y = rng.NextUInt64();
+ return new UInt128(y, x);
+ }
+}
+#endif
@@ 136,7 136,6 @@ public sealed class UniformInteger128Tes
Assert.False(dist.TrySample(rng, out _));
Assert.True(dist.TrySample(rng, out result));
Assert.Equal(new UInt128(0x4000000000000000, 3), result);
- Assert.False(dist.TrySample(rng, out _));
// Now test a blocking sample
Assert.Equal(new UInt128(0x4000000000000000, 4), dist.Sample(rng));
@@ 289,70 288,29 @@ public sealed class UniformInteger128Tes
[Fact]
public void RejectionsInt128()
{
- Int128 midpoint = 0;
+ Int128 midpoint = Int128.MaxValue / 2 + Int128.MinValue / 2;
Int128 low = Int128.MinValue;
Int128 high = midpoint + 1;
- UInt128 maxRand = UInt128.MaxValue;
- UInt128 rangeSize = unchecked((UInt128)high - (UInt128)low + 1);
- UInt128 rejectCount = (maxRand - rangeSize + 1) % rangeSize;
-
- UInt128 lastAccepted = maxRand - rejectCount;
- UInt128 penultimateAccepted = lastAccepted - 1;
- UInt128 firstRejected = lastAccepted + 1;
- UInt128 secondRejected = firstRejected + 1;
- UInt128 thirdRejected = secondRejected + 1;
+ var sequence = Enumerable.Range(0, 10).Select(x => UInt128.MaxValue / 2 + (UInt128)x);
var dist = Uniform.NewInclusive(low, high);
- var rng = new SequenceRng([
- penultimateAccepted.IsolateLow(),
- penultimateAccepted.IsolateHigh(),
- lastAccepted.IsolateLow(),
- lastAccepted.IsolateHigh(),
- firstRejected.IsolateLow(),
- firstRejected.IsolateHigh(),
- secondRejected.IsolateLow(),
- secondRejected.IsolateHigh(),
- thirdRejected.IsolateLow(),
- thirdRejected.IsolateHigh(),
+ var rng = new SequenceRng(sequence.SelectMany(x => new[] { x.IsolateLow(), x.IsolateHigh() }));
- firstRejected.IsolateLow(),
- firstRejected.IsolateHigh(),
- secondRejected.IsolateLow(),
- secondRejected.IsolateHigh(),
- thirdRejected.IsolateLow(),
- thirdRejected.IsolateHigh(),
- 0,
- 0,
- ]);
-
+ Assert.False(dist.TrySample(rng, out _));
Assert.True(dist.TrySample(rng, out Int128 result));
- Assert.Equal(midpoint, result);
+ Assert.Equal(new Int128(0xC000000000000000, 0), result);
+ Assert.True(dist.TrySample(rng, out result));
+ Assert.Equal(new Int128(0xC000000000000000, 1), result);
+ Assert.False(dist.TrySample(rng, out _));
Assert.True(dist.TrySample(rng, out result));
- Assert.Equal(midpoint + 1, result);
+ Assert.Equal(new Int128(0xC000000000000000, 2), result);
Assert.False(dist.TrySample(rng, out _));
- Assert.False(dist.TrySample(rng, out _));
- Assert.False(dist.TrySample(rng, out _));
+ Assert.True(dist.TrySample(rng, out result));
+ Assert.Equal(new Int128(0xC000000000000000, 3), result);
// Now test a blocking sample
- Assert.Equal(Int128.MinValue, dist.Sample(rng));
- }
-
- [Fact]
- public void ZoneEqualToGeneratedInt128()
- {
- Int128 low = Int128.MinValue;
- Int128 high = Int128.MaxValue - 1;
- UInt128 rngState = UInt128.MaxValue - 1;
-
- var rng = new SequenceRng([rngState.IsolateLow(), rngState.IsolateHigh()]);
- var dist = Uniform.NewInclusive(low, high);
-
- Assert.Equal(UInt32.MaxValue - 1, rng.NextUInt32());
- Assert.Equal(UInt32.MaxValue, rng.NextUInt32());
- Assert.Equal(UInt32.MaxValue, rng.NextUInt32());
- Assert.Equal(UInt32.MaxValue, rng.NextUInt32());
- Assert.Equal(high, dist.Sample(rng));
+ Assert.Equal(new Int128(0xC000000000000000, 4), dist.Sample(rng));
}
/// <summary>
@@ 383,9 341,9 @@ public sealed class UniformInteger128Tes
var dist = Uniform.New(new Int128(0, 50), new Int128(2_000, 200_000_000_000ul));
var expectedValues = new[]
{
- new Int128(0x0E9, 0x2C2DE5AC5A44EFE3),
- new Int128(0x04C, 0xB23B6C6817A5B06C),
- new Int128(0x1F6, 0xBD76F937FCFCFB8D),
+ new Int128(0x666, 0xD3A5622DD2B654F2),
+ new Int128(0x45D, 0x5667CA7B62179B9D),
+ new Int128(0x4D4, 0x81F33768224909BA),
};
foreach (var expected in expectedValues)
Assert.Equal(expected, dist.Sample(rng));