Anonymous user
Talk:Linear congruential generator: Difference between revisions
→Should the vectorized variant of the X86 Assembly LCG be included?
| (7 intermediate revisions by 3 users not shown) | |||
Line 18:
:::If the program tries <math>r_0 = 0</math>, then FreeBSD uses <math>r_0 = 123459876</math>. --[[User:Kernigh|Kernigh]] 04:23, 15 July 2011 (UTC)
::::Huh, how does that work? <math>2^{31}-1</math> is a prime number, so no <math>r_n</math> will ever produce a 0 return value. <code>RAND_MAX</code> presumably is <math>2^{31}-2</math>? Aren't <code>rand()</code> supposed to return a value from 0 to <code>RAND_MAX</code> inclusive? --[[User:Ledrug|Ledrug]] 07:52, 15 July 2011 (UTC)
:::[http://svnweb.freebsd.org/base/head/lib/libc/stdlib/rand.c?revision=174541&view=markup Here is the FreeBSD code.] Also, [http://svnweb.freebsd.org/base/head/include/stdlib.h?revision=206997&view=markup RAND_MAX is <math>2^{31} - 1</math>]. --[[User:Kernigh|Kernigh]] 18:12, 15 July 2011 (UTC)
== Example Sequences==
Line 33 ⟶ 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 <s>congruential</s> congruent to the correct numbers: -740551042 is <s>congruential</s> congruent to 1406932606. Negative numbers from lcg.ms are off by one, because the division truncated to the wrong direction: -11529 is <s>congruential</s> congruent 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)
: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. --[[User:Rdm|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(). [[User:Emjay|Emjay]] ([[User talk:Emjay|talk]]) 21:38, 22 August 2015 (UTC)
: I would mark it as incorrect, maybe someone can fix it. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 00:22, 23 August 2015 (UTC)
:: I did what you suggested, and am curious to see what the solution might be, as my understanding of mathematics is very limited. Thank you for the input, please feel free to offer any other suggestions; I am new to this site, and wiki editing in general. [[User:Emjay|Emjay]] ([[User talk:Emjay|talk]]) 18:27, 23 August 2015 (UTC)
| |||