从没有重复的另一个人中产生确定性的INT

发布于 2025-02-12 06:33:52 字数 303 浏览 3 评论 0原文

我希望创建一个确定的数字生成函数，其中输入号始终会生成相同的数字，但是没有两个数字最终会生成相同的结果。

例如：

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

但是，我需要为所有可以用特定数据类型表示的数字（例如INT64）代表的所有数字工作。

这感觉像是应该很简单或完全不可能的东西。是否有一些随机数生成方案可以保证这种分布，而无需我创建所有可能数字的数组，然后随机排序，然后使用索引（并在此期间让我用尽我的内存）？

非常感谢 f

原文

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

像你 2025-02-19 06:33:54

您需要的转换公式是：

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

这是仿射密码。

mod确保它在所需的范围内，s是一个简单的偏移，m应该为 coprime 带有n。
企业简单地表示n和m不应共享任何常见因素。
由于n是2^64，其唯一的因素是2 - so m基本上不应偶尔（即2）：2）：

因此，对于uint64范围：

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
}

这可能看起来很魔术，但是您可以说服自己，它可以与uint16：

https://go.dev/play/p/ekb6sh3-sgu

uint64 将需要大量资源来运行:-)

更新：

对于签名的数字（即int64）逻辑没有什么不同。由于我们知道我们使用uint64的唯一一对一映射，一种方法就是转换输入＆amp;输出从UINT64到INT64，反之亦然：

// original unsigned version
func transform(p uint64) uint64 {
    return m*p + s
}

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

再次是int16示例证明没有碰撞：

https://go.dev/play/p/fkw5flmk0fu

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

(as uint64 would take quite some resources to run :-)

Update:

For signed numbers (i.e. int64) the logic is no different. Since we know we have a unique one-to-one mapping with uint64 one approach would simply be to convert inputs & outputs from uint64 to int64 and vice versa:

// original unsigned version
func transform(p uint64) uint64 {
    return m*p + s
}

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

again here's a int16 example proving there's no collisions:

https://go.dev/play/p/Fkw5FLMK0Fu

回复收藏 0 原文