无符号数的取模数组环绕

Question

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

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++ 程序员都可读，因为它涉及两种语言。）

- Fred Foo

---

为什么在C语言中使用static数据是不好的风格（或者你只是指C++）？ - pmg

在C语言中，这也是不好的编程风格，因为它会导致非可重入代码。 - Fred Foo

@endolith：因为它会使代码不支持多线程。 - Fred Foo

@larsmans：为什么这是不好的？或者说，什么情况下会出现问题？如果它总是有问题，那么这种语言结构就不应该存在，对吧？ - endolith

@endolith：我倾向于以线程安全的方式编写我的代码，除非像这种情况一样进行实验。所以是的，static 有用处，而这就是它的用途，但只是一个一次性程序。 - Fred Foo

@larmans：您可以通过将状态（在本例中为idx）作为指针传递并使用它来解决您的“静态”数据问题（以及可重入性问题）：“unsigned lagfib(unsigned* idx)”。然后用户只需在第一次调用之前手动将其初始化为0（或使用lagfib_init(&state)）。如果您不确定idx是否始终是unsigned，则可以在typedef后面隐藏其类型，或者将它隐藏在（非不透明的实现原因，不透明的API方式）struct lagfib_stat中。 - Tim Čas

Answer 1

让我们假设 idx = 0，SIZE = 64。

由于 idx 是无符号的，因此 (idx-24) % SIZE 的结果会非常大（32位整数为4294967272），导致索引无效。

为了实现循环效果，您需要在取模之前加上 SIZE：(idx-24+SIZE) % SIZE 的结果将是(0-24+64)%64，其值为40。

- codaddict

Answer 2

如果 idx 小于 24，您将会得到一个对于 unsigned int 数字范围的另一端的循环。55 不是 e.g. 2^32 的约数，因此这样做将不会给出正确的结果。

我可以看到两个选项：

- 维护三个分别为 24 和 55 偏移的不同的 idx 变量。 - 进行如下操作：(idx - 24 + SIZE) % SIZE。

实际上，我会选择第一个选项，并通过重新编写增量来避免模运算：

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

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

- Oliver Charlesworth

---

+1并被接受，但我假设模64被编译为位掩码操作。我真的应该刷新一下我的模算术知识。 - Fred Foo

@larsmans：哦，所以你的代码中实际上有“SIZE == 64”？ - Oliver Charlesworth

顺便问一下，你有没有考虑到你的种子值需要以“相反”的顺序呢？ - Oliver Charlesworth

回到 SIZE=55，并注意到 idx + 55 - SIZE 现在等于 idx，因此我只需要两个索引。非常感谢！ - Fred Foo

Answer 3

您正在使用负索引访问值。例如：

-24 % 55 == -24

所以，你需要一些逻辑来包装到数组的末尾。C/C++不会为你做这个。

- chrisaycock