3

我正在尝试为整数实现一个滞后的斐波那契伪随机数生成器，直到某个最大值。它维护一个值数组

int values[SIZE] = { /* 55 seed values */ };

并使用以下函数返回下一个值

unsigned lagfib()
{
    static unsigned idx = 0;
    int r = values[idx];

    /* The following does not work: */
    values[idx] = (values[(idx-24) % SIZE] + values[(idx-55) % SIZE])
                 % MAX_VALUE;
    idx = (idx+1) % SIZE;
    return r;
}

实际上，values应该是一个始终满的简单环形缓冲区。减法和模数应该将索引环绕到数组的末尾。SIZE应始终至少为 55，但我想四舍五入到 64 以加快模数。

但显然，我的模计算错误，我不知道如何解决它们。将索引类型更改为int不会改善情况。

（PS：是的，static数据风格不好，但我希望这对于 C 和 C++ 程序员来说都是可读的，因为它适用于两种语言。）

4

3 回答 3

3

让我们采取idx = 0和SIZE = 64。

(idx-24) % SIZE 将是一个非常大的值（4294967272对于 32 位 int ），因为idx它是无符号的，使其成为无效索引。

要获得圆形效果，您应该在取模SIZE 之前添加：

(idx-24+SIZE) % SIZE 将是(0-24+64)%64评估为40。

于 2010-10-18T13:02:34.630 回答
2

如果 egidx小于 24，您将环绕到数字范围的另一端unsigned int。55 不是例如 2^32 的除数，所以这不会给你正确的结果。

我可以看到两个选项：

  • 维护三个单独idx的变量，分别偏移 24 和 55。
  • 做例如(idx - 24 + SIZE) % SIZE。

实际上，我会选择第一个选项，并通过将增量重写为完全避免模数：

idx = ((SIZE-1) == idx) ? 0 : (idx+1);

这可能比计算模数要快得多。

于 2010-10-18T13:01:52.167 回答
0

您正在访问具有负索引的值。例如：

-24 % 55 == -24

所以你需要一些逻辑来环绕到数组的末尾。C/C++ 不会为您执行此操作。

于 2010-10-18T13:02:16.097 回答