Anonymous user
Talk:Linear congruential generator: Difference between revisions
→When modulus matches the first operand's sign: new section
(→On the task: Link to FreeBSD code.) |
(→When modulus matches the first operand's sign: new section) |
||
Line 34:
::::: 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) --[[User:Ledrug|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 .... --[[User:Dgamey|Dgamey]] 03:47, 12 July 2011 (UTC)
== When modulus matches the first operand's sign ==
When I wrote this task, I forgot that some languages have [[Arithmetic/Integer|a modulus operator that matches the sign of the first operand]]. With these languages, <code>formula (mod m)</code> might be negative and outside my expected range of 0 to m - 1. I added this <nowiki>{{needs-review}}</nowiki> note to the F# example:
{{alertbox|#ffffd8|These generators can yield negative numbers because the modulus operator of F# matches the sign of the first operand. The generators must only yield numbers from 0 to m - 1.
----
Negative numbers from lcg.bsd are congruential to the correct numbers: -740551042 is congruential to 1406932606. Negative numbers from lcg.ms are off by one, because the division truncated to the wrong direction: -11529 is congruential to 21239, but expected 21238.}}
I know of 2 workarounds: (1) use [[bitwise operations]] to clear the sign bit, or (2) check if <code>formula (mod) m</code> is negative, and if so, add <code>m</code>. We might want to clarify the task. --[[User:Kernigh|Kernigh]] 17:21, 1 August 2011 (UTC)
| |||