选择按位运算序列

Question

是否可以对随机生成的 64 位数字选择一系列按位运算，使得最终结果中的位具有给定的设置概率？我的目标是编写一个函数，该函数采用 [0, 1) 范围内的双精度数，并仅通过对随机生成的长数使用按位运算 OR 和 AND 来生成具有该比例的位的长数。

我的思考过程是，这可以减少 |p - (4^n - 1)/(4^m)| 的误差。其中 p 是所需的比率，m 代表总操作，n 代表 OR 的数量。这是因为将 k 个长整型运算后的比率为 1/(4^k)，而将 n 个长整型运算在一起后的比率应为 1 - 1/4^n，因此两者执行后的比率为 (4 ^k-1)/(4^(k+n))。但这就是我陷入困境的地方，因为我不知道如何找到 k 或 n 的最佳值。

Answer 1

如果我正确理解了你的问题陈述，这听起来很像俄罗斯农民的乘法。考虑随机生成的

long

每个位都是独立的，并且每个位的设置概率为 50%。假设（为了递归）我们有你想要的函数

f(p)

；然后

rand()       gives the same distribution as f(0.5)
f(p) & f(q)  gives the same distribution as f(p*q)
f(p) | f(q)  gives the same distribution as f(p + q - p*q)

假设我们正在寻找

f(0.9)

。我们知道

f(0.9) = f(0.5) | f(x) where 0.5 + x - 0.5*x = 0.9, i.e. 0.5x = 0.4

所以现在我们正在寻找

f(0.8)

。我们知道

f(0.8) = f(0.5) | f(x) where 0.5x = 0.3
f(0.6) = f(0.5) | f(x) where 0.5x = 0.1
f(0.2) = f(0.5) & f(x) where 0.5x = 0.2
f(0.4) = f(0.5) & f(x) where 0.5x = 0.4
f(0.8) = f(0.5) | f(x) where 0.5x = 0.3
[...]

这个递归永远不会真正完成；但在我们愿意的任何时候，我们都可以触底并开始重新缠绕堆栈。

f(0.9) = R | R | (R & R & (R | R | (R & R & ...)))

例如，这段 C 代码给出的分布非常接近 p=0.9：

#define R (rand() % 256)
unsigned get09() {
  unsigned x = R;  // 0.5
  x |= R; // 0.75      
  x |= R; // 0.875
  x &= R; // 0.4375     
  x &= R; // 0.21875
  x |= R; // 0.609375
  x |= R; // 0.8046875
  x |= R; // 0.90234375
  return x;
}

现在，除了直接使用 R 之外，您是否可以通过使用产生式来获得

 更接近

- 例如，我们可以使用

f(0.9) = f(0.684) | f(0.684)

这一事实，然后寻找产生

f(0.684)

的方法吗？当然可以。

现在，也许这就是正在发生的 Baader-Meinhof 效应，但这实际上（偶然！）感觉就像一个有向超图“最简洁路径”问题，类似于 https://mathoverflow.net/questions/466176/what-is -the-proper-name-for-this-tersest-path-problem-in-infinite-craft — 参见 https://quuxplusone.github.io/blog/2024/03/03/infinite-craft-theory/ 和 Knuth Volume 2 §4.6.3“Evaluation of Powers” 对于某些理论。我们正在寻找从 $V_0={0.5}$ 到

p

的最简洁路径，使用操作 $E$，它实际上是两个可能的操作：

&

和

|

。因此，从 {0.5} 开始，我们可以一步到达 {0.5, 0.25, 0.75} 中的任意一个；我们可以通过两步达到 {0.5, 0.25, 0.75, 0.125, 0.625, 0.375, 0.875, 0.1875, 0.8125} 中的任意一个；等等;你只想知道在达到某个

p

范围内的某个数字之前需要多少步。