计算科学 - 随机存取随机排列 - 吾爱随笔录

计算科学分区随机算法

2021-11-25 20:30:57

我有大量的并行进程和一个大整数 $n$ ，并且想要随机划分整数 $[0,n)$ 在过程中只有 $O(1)$ 沟通。

一种很好的方法是生成伪随机排列 $\pi \in S_n$ 表示为一个小函数，因此只需要交换随机密钥/种子。有没有好的方法来做到这一点？

1个回答

挑选 $2^k$ 略大于 $n$ , 生成一个块密码 $f \in S_{2^k}$ 操作于 $k$ 位块，并构造一个排列 $[0,n)$ 通过沿着循环行走 $f$ 直到我们回到所需的范围内。具体来说，给定 $x < n$ 我们设置

g (x) = f^{p} (x) = f (f (f (. . . x . . .)))

$g(x) = f^p(x) = f(f(f(...x...)))$ 在哪里

p

$p$ 是最小正整数 st

f^{p} (x) < n

$f^p(x) < n$ .

如果 $2^k = O(n)$ ，并且块密码很好，步行需要 $O(1)$ 预计时间。注意 $p$ 必然是有限的，因为最终我们将绕回循环并找到 $f^p(x) = x$ .

有关更多详细信息，请参阅

这是一个使用截断 TEA 块密码的示例实现，如 (2) 中所述：

其它你可能感兴趣的问题