Array wraparound with modulo of unsigned

Question

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.)

Answer 1

If e.g. idx is less than 24, you'll get wraparound to the other end of the number range of unsigned int. 55 is not a divisor of e.g. 2^32, so this will not give you correct results.

I can see two options:

• Maintain three separate idx variables, offset by 24 and 55 respectively.
• Do e.g. (idx - 24 + SIZE) % SIZE.

Actually, I would choose the first option, and avoid the modulo entirely by rewriting the increment as:

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

which will probably be way faster than calculating modulo.

Answer 2

Lets take idx = 0 and SIZE = 64.

(idx-24) % SIZE will be a very large value (4294967272 for a 32-bit int )as idx is unsigned, making it an invalid index.

To get the circular effect you should add SIZE before taking modulus:

(idx-24+SIZE) % SIZE will be (0-24+64)%64 which evaluates to 40.

Answer 3

You're accessing values with a negative index. For example:

-24 % 55 == -24

So you'll need some logic to wrap around to the end of the array. C/C++ doesn't do this for you.