That code is indeed wrong, but the error consists in using "long" instead of "unsigned long".
The sizes of "unsigned long" and of "long" are unknown, but they are at least 32 bit.
Had "unsigned long" been used, modular arithmetic without overflow would have been used, which was the intention of the code.
Of course the condition of the test must also be changed for an "unsigned long".
As it is written here, it is completely wrong. If this program would be compiled with the correct "-fsanitize=undefined -fsanitize-undefined-trap-on-error" options, which should be always used for any C/C++ program, unless there are good reasons to do otherwise, then the program will be aborted at one of the the first invocations of the function.
Those compilation options did not make the program abort for me nor am I getting any warnings (at least not with -Wall -Wextra), even when changing all longs to ints in the above code, in order to investigate the case when sizeof (int) == sizeof (long) == 4. Setting *seed = 4294967295 has also no effect. What am I missing?
Well, looking now more carefully at the code, it is in fact correct.
The constants 16807 and 127773 are chosen so that their product is 2147480811, which is smaller enough than 2^31 to prevent overflows in the line:
s = 16807 * (s - k * 127773) - 2836 * k;
where s is known to be positive and less than 2^31, and (s - k * 127773) is the remainder from the division of s by 127773, and k is the quotient of that division.
Adding 2^31 - 1 to a negative 32-bit number cannot produce an overflow in:
if (s < 0) s += 2147483647;
So both the parent comment and my initial confirmation were wrong, the library code is correct. Initially I have replied too quickly, without reading the source. because most such congruential generators are written to use modular arithmetic, while this one has been carefully modified to obtain an equivalent result using integer arithmetic (which also makes it much slower than what can be done with modular arithmetic, so the reason for this is unclear).
The only thing that can be criticized is the lack of a comment emphasizing that those constants cannot be modified haphazardly, otherwise integer overflows are certain.
So your test has verified that the code is correct, so no overflows happened.
Your large seed becomes -1 after conversion to long on a 32-bit system, or it retains its value on a 64-bit system.
For different reasons, in both cases there are no overflows (on a 64-bit system, long is 64-bit, so overflows would have been avoided even with much wider allowable ranges for the constants; the constants are optimized for systems with 32-bit longs, where they are just below the limit for overflows).
Some other values that are either negative or larger than 2^31 may cause overflows, but they are illegal for this function.
Thank you for the explanation. This looks to be correct, e.g. by changing 16807 to 16808 and using the sanitize options, the program can indeed terminate with SIGILL depending on the value of seed.
> That code is indeed wrong, but the error consists in using "long" instead of "unsigned long".
Is this not what I was referring to? I would like to learn more, I think we have the same reasoning, but I am bad at explaining. It think perhaps it could be a good learning experience to HN if you could say exactly what lines you believe are wrong.
