How to Deterministically Generate Unique Integers from Inputs?

Deterministic Generation of Unique Integers from Inputs

In seeking a solution for generating deterministic integers that avoid duplicates, the question revolves around finding a transformation method that maps input numbers to distinct outputs within a given range, such as an int64.

The answer lies in applying modular arithmetic derived from the Affine cipher:

f(P) = (mP + s) mod n

where:

• n = range of possible integers (e.g., 2^64 for int64)
• s
• m is coprime with n (meaning they share no common factors other than 1)

By choosing an appropriate m and s, this formula guarantees a unique mapping of input numbers to output integers within the specified range. For instance, for int64:

m = 39293 (any non-even number)
s = 75321908 (any random number below 2^64)

With these values, the transform function:

func transform(p uint64) uint64 {
    return p*m + s
}

ensures that each input integer produces a unique output integer, as demonstrated in the following Go playground example:

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

For negative numbers, the logic remains the same. We can simply convert inputs and outputs between uint64 and int64 to maintain the unique mapping:

func signedTransform(p int64) int64 {
    return int64(transform(uint64(p)))
}

This approach ensures that all possible integers within a given range are mapped to distinct output integers deterministically and without any collisions.

The above is the detailed content of How to Deterministically Generate Unique Integers from Inputs?. For more information, please follow other related articles on the PHP Chinese website!