I'm looking to create a deterministic number generation function where the input number will always generate the same number, but no two numbers will end up generating the same result.

E.g.:

1 -> 3
2 -> 5
3 -> 4
4 -> 2
5 -> 1

However I need this to work for all numbers that can be represented by a specific datatype, e.g. an int64.

This feels like something that should either be really straightforward, or completely impossible. Is there some random number generation scheme that guarantees this sort of distribution without me having to create an array of all possible numbers, randomly sort, and then use the index (and making me run out of memory in the meantime)?

Many thanks F

CodePudding user response：

The transformation formula you need is:

f(P) = (mP   s) mod n

// n = range - so for uint64 2^64
// s < range i.e. < 2^64
// m = must be coprime with n

This is modular arithmetic as used in the Affine cipher.

The mod ensures it is within desired range, s is a simple shift and m should be coprime with n. Coprime simply means n and m should not share any common factors. Since n is 2^64 its only factors are the number 2 - so m should basically not be even (i.e. not divisible by 2):

So for uint64 range:

var (
    m = uint64(39293)    // some non-even number
    s = uint64(75321908) // some random number below 2^64
)

func transform(p uint64) uint64 {
    return p*m   s // implicitly mod'ed 2^64 by the type's size
}

This may appear magic, but you can convince yourself it works with uint16:

https://go.dev/play/p/EKB6SH3-SGu

Since uint64 would take quite some resources to run :-)

CodePudding user response：

To add to colm.anseo answer, this kind of mapping is also known as Linear congruential generator.

X_{n 1} = (aX_n c) mod m

When c ≠ 0, correctly chosen parameters allow a period equal to m, for all seed values. This will occur if and only if:

• m and c are relatively prime,
• a-1 is divisible by all prime factors of m,
• a-1 is divisible by 4 if m is divisible by 4.

These three requirements are referred to as the Hull–Dobell Theorem.

For 64bit LCG a=6364136223846793005 and c=1442695040888963407 from Knuth looks good.

Note, that LCG mapping is 1-to-1, it maps whole [0...2⁶⁴-1] region to itself. You could invert it if you want. And as RNG it has distinctive ability for jump-ahead.