int multiplication overflow in LCG

Question

The following is copied from one Opensource project's rand(), it use LCG

rand_next = rand_next * 1103515245L + 12345L;  //unsigned long rand_next

The classic LCG is:

Next = (Next * a + c) mod M

Obviously, here M is 2^32.

what make me confused is rand_next * 1103515245L, where I am pretty sure overflow will occur! I take a look several rand() implementations, all take this way except using different a and c.

Is that overflow harmful? if not why?

Thanks

Answer 1

This is fine. According to the C99 specification, for unsigned long operations, the result is the same but reduced modulo 2³² (§6.2.5):

A computation involving unsigned operands can never overflow, because a result 
that cannot be represented by the resulting unsigned integer type is reduced 
modulo the number that is one greater than the largest value that can be 
represented by the resulting type.

So this behaviour isn't actually "overflow", but I'll call it that for simplicity in this answer. Since for modular arithmetic we have

a1 ≡ b1 (mod m)
a2 ≡ b2 (mod m)

implies

a1 + a2 ≡ b1 + b2 (mod m)

We have

Next * a ≡ k (mod 2^32)

where k is Next * a with "overflow". So since M = 2^32,

Next * a + c ≡ k + c (mod M)

The result with "overflow" is equivalent to the one without "overflow" under modular arithmetic, so the formula is fine. Once we reduce modulo M = 2^32, it will give the same result.

Answer 2

You multiply a signed long with an unsigned long. So, both operands of * have the same integer conversion rank. In this case, the rule below (C++11, §5/9, item 5, sub-item 3) applies:

[...] if the operand that has unsigned integer type has rank greater than or equal to the rank of the type of the other operand, the operand with signed integer type shall be converted to the type of the operand with unsigned integer type.

So both operands are implicitly converted to unsigned long before the multiplication is evaluated. Hence you get unsigned arithmetic and an unsigned result, and the same rule applies again for the addition operation.

Integer overflow for unsigned is well-defined (see Zong Zhen Li's answer, which has just been expanded to cover this in detail), so there is no problem.

---

Regarding C (as opposed to C++), C11 has an identical rule in §6.3.1.8/1:

[...] if the operand that has unsigned integer type has rank greater or equal to the rank of the type of the other operand, then the operand with signed integer type is converted to the type of the operand with unsigned integer type.