以无符号为模的数组环绕
我正在尝试实现一个滞后斐波那契伪随机数生成器，用于生成达到某个最大值的整数。它维护一个值数组
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++ 程序员都可以阅读它，因为它适用于两种语言。）
I'm trying to implement a lagged Fibonacci pseudo-random number generator for integers up to some maximum. It maintains an array of values
int values[SIZE] = { /* 55 seed values */ };
and uses the following function to return the next value
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;
}
In effect, values should be a simple ring buffer that is always full. The subtraction and modulo should wrap the index around to the end of the array. SIZE should always be at least 55, but I want to round up to 64 to speed up the modulo.
But apparently, I've got the modulo calculations wrong and I don't know how to fix them. Changing the index type to int doesn't improve things.
(PS.: Yes, static data is bad style, but I want this to be readable for both C and C++ programmers, since it pertains to both languages.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
让我们采用
idx = 0和SIZE = 64。(idx-24) % SIZE将是一个非常大的值（4294967272对于 32 位 int ），因为idx是无符号的，使得它无效的索引。要获得圆形效果，您应该在取模之前添加
SIZE：(idx-24+SIZE) % SIZE将为(0-24+64)%64，其计算结果为40。Lets take
idx = 0andSIZE = 64.(idx-24) % SIZEwill be a very large value (4294967272for a 32-bit int )asidxis unsigned, making it an invalid index.To get the circular effect you should add
SIZEbefore taking modulus:(idx-24+SIZE) % SIZEwill be(0-24+64)%64which evaluates to40.例如，如果
idx小于24，您将返回到unsigned int数字范围的另一端。 55 不是 2^32 等的约数，因此这不会给您正确的结果。我可以看到两个选项：
(idx - 24 + SIZE) % SIZE。实际上，我会选择第一个选项，并通过将增量重写为完全避免取模：
这可能比计算取模快得多。
If e.g.
idxis less than 24, you'll get wraparound to the other end of the number range ofunsigned int. 55 is not a divisor of e.g. 2^32, so this will not give you correct results.I can see two options:
idxvariables, offset by 24 and 55 respectively.(idx - 24 + SIZE) % SIZE.Actually, I would choose the first option, and avoid the modulo entirely by rewriting the increment as:
which will probably be way faster than calculating modulo.
您正在访问具有负索引的值。例如：
因此您需要一些逻辑来环绕到数组的末尾。 C/C++ 不会为你做这个。
You're accessing values with a negative index. For example:
So you'll need some logic to wrap around to the end of the array. C/C++ doesn't do this for you.