0

背景：我正在为基于微控制器的嵌入式系统编写一个外部 SRAM 测试仪。没有安全性，不涉及密码学。为了可重现地访问“尽可能不连续”的内存位置，我正在寻找一个实现

y = shuffle(x)，取并返回一个介于 0 和固定 N = 2^16 - 1 之间的整数

它本身可能不会使用大量的 RAM，例如一个简单的随机地址数组。从好的方面来说，它可以变慢。对非连续没有严格的定义——它是关于上下颠簸地址线，寻找印刷电路板的焊接和其他故障。建议？

到目前为止，我发现Knuth shuffle aka Fisher-Yates shuffle。

后期编辑：我想我正在寻找最大化汉明距离。“反格雷码”？

4

2 回答 2

2

我同意 Jim Mischel 的观点，即 xorshift 是快速非加密 PRNG 的理想选择。需要仔细选择系数以实现全周期，其中包括除 0 以外的所有值。

由于您在问题中将问题连接到 16 位，因此这是一个用 Ruby 编写的 16 位实现，但很容易移植到您喜欢的任何其他东西：

# << is shift left, >> is shift right, ^ is bitwise XOR, & is bitwise AND

MASK_16 = (1 << 16) - 1

def xorshift(x)
  x ^= x << 7 & MASK_16
  x ^= x >> 9
  x ^= x << 8 & MASK_16
  return x
end

counter = 0
x = 1
y = 1

# Floyd's "Tortoise and Hare" cycle-finding algorithm shows
# the generator to be full cycle for 16 bits, excluding zero.
loop do
  counter += 1
  x = xorshift(x)
  y = xorshift(xorshift(y))
  break if x == y
end
puts counter   # => 65535
于 2020-02-27T21:36:11.083 回答
2

我建议实施Xorshift或类似的东西。它们速度快，需要很少的内存，可以构造成有很长的周期，并满足许多随机性测试。

另一种方法是将 0..(n-1) 范围内的每个数字唯一地映射到该范围内的另一个数字。正如我在这个答案中描述的那样，使用模乘逆很容易做到这一点。

于 2020-02-27T19:05:16.637 回答