Created
October 29, 2024 05:05
-
-
Save NickStrupat/464b3f63bfad7d780fada2974ae62a8f to your computer and use it in GitHub Desktop.
Random-ish Integer permuter based on https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
public readonly struct PrimeQuadraticResiduePermuter32(UInt32 seed) | |
{ | |
public UInt32 this[UInt32 x] => Permute(Permute(unchecked(x + seed)) ^ Xor); | |
private const UInt32 Xor = 0x5bf03635; | |
private static UInt32 Permute(UInt32 x) | |
{ | |
const UInt32 prime = 4_294_967_291; // The largest prime less than 2^32 that is congruent to 3 mod 4. | |
if (x >= prime) | |
return x; // The 5 integers out of range are mapped to themselves. | |
var square = (UInt64) x * x; | |
var residue = (UInt32)(square % prime); | |
return x <= prime / 2 ? residue : prime - residue; | |
} | |
} | |
public readonly struct PrimeQuadraticResiduePermuter64(UInt64 seed) | |
{ | |
public UInt64 this[UInt64 x] => Permute(Permute(unchecked(x + seed)) ^ Xor); | |
private const UInt64 Xor = 0x5bf036355bf03635; | |
private static UInt64 Permute(UInt64 x) | |
{ | |
const UInt64 prime = 18_446_744_073_709_551_427; // The largest prime less than 2^64 that is congruent to 3 mod 4. | |
if (x >= prime) | |
return x; // The 188 integers out of range are mapped to themselves. | |
var square = (UInt128) x * x; | |
var residue = (UInt64)(square % prime); | |
return x <= prime / 2 ? residue : prime - residue; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment