Talk:Linear congruential generator
OK, What's the task
Not to be impatient but so far this is a nice explanation of LCRNG's but there is no task.
There are other tasks with LCRNGs like Random_number_generator_(included) which pertains to what is built in.
What do we need to do to solve this task? --Dgamey 01:06, 2 July 2011 (UTC)
- The task with built-in RNGs doesn't necessarily map. There's no guarantee that the built-in RNG is a linear congruential generator; that's just the most common implementation option. –Donal Fellows 15:42, 2 July 2011 (UTC)
- Still there is no task see "insert task here". It's basically encyclopedic. --Dgamey 02:29, 3 July 2011 (UTC)
On the task
I kinda remember something about not all seeds being good? a seed of zero for example? --Paddy3118 05:07, 7 July 2011 (UTC)
- Shouldn't be. Because of the coprimality between a and m, all values from 0 to m-1 will appear exactly once in a cycle, so any seed is as good as another. You may be thinking the situation where people choose predictable seeds, such as 0, current time, process id, etc while trying to use PRNG for sensitive work, giving an attacker a higher chance of success at finding the pseudo random sequence. --Ledrug 05:23, 7 July 2011 (UTC)
- Aha! Thanks Ledrug. I found what I was thinking of - I was thinking of LFSR's. --Paddy3118 06:52, 7 July 2011 (UTC)
- There is a class of linear congruential generators where c = 0: the formula is . If the seed was zero, then these generators would yield zero, zero, zero, zero.... Today, I found that FreeBSD rand() uses such a formula:
- If the program tries , then FreeBSD uses . --Kernigh 04:23, 15 July 2011 (UTC)
- Huh, how does that work? is a prime number, so no will ever produce a 0 return value.
RAND_MAX
presumably is ? Aren'trand()
supposed to return a value from 0 toRAND_MAX
inclusive? --Ledrug 07:52, 15 July 2011 (UTC)
- Huh, how does that work? is a prime number, so no will ever produce a 0 return value.
- Here is the FreeBSD code. Also, RAND_MAX is . --Kernigh 18:12, 15 July 2011 (UTC)
- There is a class of linear congruential generators where c = 0: the formula is . If the seed was zero, then these generators would yield zero, zero, zero, zero.... Today, I found that FreeBSD rand() uses such a formula:
- Aha! Thanks Ledrug. I found what I was thinking of - I was thinking of LFSR's. --Paddy3118 06:52, 7 July 2011 (UTC)
Example Sequences
It occurs to me that the BSD LCRNG can produce an overflow of 32 bit words. It would be nice to have a sequence that exercises this to ensure the behavior is reproduced. --Dgamey 04:58, 8 July 2011 (UTC)
- Overflow how? Intermediate results can be done with larger integer types. --Ledrug 06:18, 8 July 2011 (UTC)
- Sure, but in the historical implementations they probably were not done that way. In many similar systems the multiplication would exceed 2^31 and cause an integer overflow. It wouldn't produce an exception but you could suddenly be looking at a negative number. That may not yield the same sequence if you are working with large integers or 64 bit words. --Dgamey 12:28, 8 July 2011 (UTC)
- If the seed is 42, then the first 5 numbers from BSD rand() are 1250496027, 1116302264, 1000676753, 1668674806, 908095735.
- Overflow is not a problem, if you can do correct math mod 2**31. If you overflow a 32-bit integer, then the low 32 bits should be correct, so you can still take the low 31 bits as the random integer. If you overflow a 10-decimal-digit integer, then you would have a problem, because 10**10 is not a multiple of 2**31. --Kernigh 20:25, 8 July 2011 (UTC)
- That is sort of my point. If you do this with 32 bit signed ints you will get a different value that you will in larger ints. For example (BSD)
- (32 bits) 0, 12345, 1406932606
- (larger ints) 0, 12345, 1406938949
- Some implementations may need to address this. That's also why having a common example sequence (with an overflow) is needed. --Dgamey 03:13, 12 July 2011 (UTC)
- Are you sure? If your integer is at least 32 bit long (shorter obviously won't do), sign bit has an impact only on the sign of modulo operator. Using 64 bits, no overflow can occur and the sequence is 12345, 1406932606..., you did something wrong with your second series. Also, if you use 32 bit signed integer, 2**31 is going to be negative. If you use modulo operator you may get a negative random number which is pretty obviously wrong, but if your language convention always returns a positive one, then it's actually correct. Largely there's no subtle error in this method, overflow or not. (Should clarify: above is assuming fixed length, 2's compliment binary integer representation. It's clearly not a problem if you have arbitrary precision integers) --Ledrug 03:33, 12 July 2011 (UTC)
- Ooops, Seems I am cross-eyed. Had it in my head as 2^31-1 modulus (a couple of other historical LCRNG .... --Dgamey 03:47, 12 July 2011 (UTC)
- Are you sure? If your integer is at least 32 bit long (shorter obviously won't do), sign bit has an impact only on the sign of modulo operator. Using 64 bits, no overflow can occur and the sequence is 12345, 1406932606..., you did something wrong with your second series. Also, if you use 32 bit signed integer, 2**31 is going to be negative. If you use modulo operator you may get a negative random number which is pretty obviously wrong, but if your language convention always returns a positive one, then it's actually correct. Largely there's no subtle error in this method, overflow or not. (Should clarify: above is assuming fixed length, 2's compliment binary integer representation. It's clearly not a problem if you have arbitrary precision integers) --Ledrug 03:33, 12 July 2011 (UTC)
- That is sort of my point. If you do this with 32 bit signed ints you will get a different value that you will in larger ints. For example (BSD)
- Overflow is not a problem, if you can do correct math mod 2**31. If you overflow a 32-bit integer, then the low 32 bits should be correct, so you can still take the low 31 bits as the random integer. If you overflow a 10-decimal-digit integer, then you would have a problem, because 10**10 is not a multiple of 2**31. --Kernigh 20:25, 8 July 2011 (UTC)
When modulus matches the first operand's sign
When I wrote this task, I forgot that some languages have a modulus operator that matches the sign of the first operand. With these languages, formula (mod m)
might be negative and outside my expected range of 0 to m - 1. I added this {{needs-review}} note to the F# example:
I know of 2 workarounds: (1) use bitwise operations to clear the sign bit, or (2) check if formula (mod) m
is negative, and if so, add m
. We might want to clarify the task. --Kernigh 17:21, 1 August 2011 (UTC)
- And some languages have the denominator for the first operand, instead of the numerator. But I believe your objection is against languages where modulus takes on the sign of the numerator rather than that of the denominator. --Rdm 19:52, 1 August 2011 (UTC)
Should the vectorized variant of the X86 Assembly LCG be included?
I recently read the instructions on this page more thoroughly. I initially believed that it was only necessary to create an LCG, not to replicate an existing implementation. The example posted under "Second example using AVX instructions." does not produce identical output to the Microsoft rand(). Should this example be removed completely? For now, I will add a comment to the vectorized implementation explaining that its output will differ from Microsoft rand(). Emjay (talk) 21:38, 22 August 2015 (UTC)