I’m looking at the RNG from K&R2 2.7 Type Conversions:

unsigned long int next = 1;

/* rand:  return pseudo-random integer on 0..32767 */
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

/* srand:  set seed for rand() */
void srand(unsigned int seed)
{
    next = seed;
}

Why is next divided by 65536 before it is type cast to unsigned int?

My first instinct was it had something to with int being 16-bit or RAND_MAX being 32767 at the time, but I still get the same results (https://oeis.org/A061364) on my current machine, with int at 32-bit and RAND_MAX at 2147483647.

And apologies if I’m missing something obvious and apologies to those who think K&R2 is outdated – the example still appears in the C standard, C17 7.22.2.2 The srand function, so I’m assuming my question is still valid nowadays.

>Solution :

Dividing before the cast is necessary when int is (or can be) 16-bit, and not when int is 32-bit.

The whole sequence of dividing by 65536 and taking the remainder by 32768 is a somewhat obfuscated way to extract bits 16 to (exclusive) 31 of next. Casting to a 16-bit type as the first step immediately discards the bits that we want, so that’s out. Casting to a 32-bit type doesn’t do any harm, the bits that we want are still there, doing the division as the second step works in that case.

If there was no division (or right shift) at all, neither before nor after the cast, then the result would be a worse PRNG: effectively that would change it from a "31-bit PRNG with 15-bit output" into a 15-bit PRNG (since the update formula has the property that information only flows "up" through the number, the higher bits never affect the lower bits, any truncation of it can be seen as a PRNG with fewer bits of state, and could be rewritten as such). As is typically for a linear congruential generator, the higher bits are "better", the lower bits have very small periods (the least significant bit is not random at all, it just alternates).