Talk:Lehmer random number generator

Untitled

Question: Why would the seed X₀ need to be co-prime to n? I believe this is wrong. A Park-Miller random number generator should be a full period generating function according to test T₁ mentioned in the ACM Random Number Generators Good Ones Are Hard To Find paper. Quoted from the same paper, "Also, because f(z) = 6z mod 13 is a full period generating function, any initial seed between 1 and 12 could have been chosen without affecting the apparent randomness of the sequence. For example, if the initial seed is 2, the resulting sequence is ... 2, 12, 7, 3, 5, 4, 11, 1, 6, 10, 8, 9, 2... (2) which is nothing more than a circular shift of sequence (1)." Where sequence (1) is produced by f(z) 6z mod 13 with an initial seed value of 1, creating the sequence ... 1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1 .... Ttreverton (talk) 22:46, 19 February 2010 (UTC)

If g=gcd(X₀,n)>1 then all generated numbers are multiples of g (that we don't want for generator). Discussion of f(z) = 6z mod 13 is irrelevant to this question. Moreover, the case of prime modulus (such as 13 in this example) does not imply almost any restrictions - any integer from 1 to modulus-1 is co-prime to the modulus and can be used as the initial seed. Maxal (talk) 03:43, 20 February 2010 (UTC)

The paper mentions several times that n is a prime number. I see the wiki page says n can also be a power of a prime number, but this is mentioned nowhere in the paper as far as I can tell. Their acm paper says "In general, any multiplicative linear congruential generator with modulus m = 2^b is flawed in the sense that it can not have a full period; instead the maximum possible period is only 2^b-2 = m/4.

Furthermore, this wiki page says the Park–Miller random number generator is also known as the Lehmer random number generator, a variant of the linear congruential generator. Meanwhile, the page for Derrick Henry Lehmer says he developed the Linear congruential generator which is frequently referred to as a Lehmer random number generator. Question: Is the Lehmer random number generator a specific variant (Park-Miller) of a linear congruential generator, or is a Lehmer random generator ANY linear congruential generators? I believe it to be the latter and that this page puts more restrictions on the parameters than necessary for the generator to be considered a Lehmer random number generator, but not enough restrictions (i.e n MUST be prime) to be the actual generator Park and Miller spoke of.

Did Park and Miller have a more lax standard for RNGs than MINSTD before its creation, or did they come up with a more general RNG and name it the Park-Miller RNG? I have missed any references to Park and Miller defining a RNG besides the MINSTD. Are other people just taking elements of MINSTD changing it around and calling it a Park-Miller RNG, despite Park and Miller being against this? From what I understand, the Park-Miller RNG is the MINSTD and should be considered nothing else.

Also, this wiki page says: "In contrast to LCG, the maximum period of the Park–Miller RNG equals n−1 and it is such when n is prime and g is a primitive root modulo n." I don't see how this is in contrast to an LCG since they too can have a maximum period of n-1, just not necessary always. Perhaps this needs rewording. Ttreverton (talk) 07:05, 20 February 2010 (UTC)

I would suggest to put unrelated questions into separate sections, otherwise it becomes hard to follow them. Still, I'll try to answer your questions in order of appearance. First, the article in not based just on a single paper of Park and Miller, so it should not be taken as the only source of information (in particular, Park and Miller never called their discoveries as Park-Miller something - that was done later by other researchers). Second, the question about Lehmer RNG should be answered by looking at his original paper. I was able to trace that to his review MR0059617 and Payne-Rabung-Bogyo 1969 paper (cited in the article) from which it is clear that Lehmer RNG is a special case of LCG with c=0. This type of generators seem to be often referred as "Park-Miller RNG" that now is not just another name for MINSTD but for a whole class of similar RNGs. That's why Park-Miller RNG and Lehmer RNG are currently stated as synonyms with the leading role given to the former name. Maybe, for historical reasons we still should give the leading role to "Lehmer RNG" instead. Third, the maximum period for LCG equals its modulus, while for Park-Miller RNG, the maximum period does not exceed the modulus minus 1. Maxal (talk) 21:44, 21 February 2010 (UTC)

btw, the choice of modulus is also discussed in Lehmer's review cited above. Maxal (talk) 21:48, 21 February 2010 (UTC)

The original Lehmer publication seems to be

• Lehmer, D. H. (1949). "Mathematical methods in large-scale computing units". Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery: 141–146. MR 0044899. (conference version), journal version: Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951).

And here is yet another paper that discusses Lehmer RNG:

• Martin Greenberger (1961). "Notes on a New Pseudo-Random Number Generator". Journal of the ACM. 8 (2): 163–167. doi:10.1145/321062.321065.

Maxal (talk) 23:29, 21 February 2010 (UTC)

UL suffixes in C99 code unnecessary?

Are the UL suffixes in the C code even necessary? It seems that this is sufficient:

return ((uint64_t)a * 279470273) % 4294967291;

Even if the compiler chooses signed types for the constants, they will be converted to uint64_t anyway. —Preceding unsigned comment added by 72.48.91.169 (talk) 11:34, 7 August 2010 (UTC)

Park-Miller in 1988 is not original

They describe the "prime modulus multiplicative linear congruential generator" (PMMLCG) and then state that they prefer the simpler term "Lehmer generator". Further, they credit Lehmer in 1969 for the suggestion of using 7^5 as a multiplier and 2^31 - 1 as a modulus. They also credit L. Schrage with the innovation that allows a two-multiplication solution (plus the inevitable division) for target systems that didn't support more than 32 bits in a signed product or dividend.

There is no original research in the paper. Park and Miller are reporters, not innovators, in this regard.

Someone with (a) a flair for writing and (b) a copy of the Park-Miller paper, should rewrite this minimizing the Park-Miller contribution and giving full attribution where deserved. The paper itself does this and has a substantial bibliography.

I know from personal experience that the 7^5 mod 2^31-1 generator was implemented and actively used in the Fall of 1970. It was the generator used in IBM's APL\360 interpreter (XM6 version), which was fairly new but already running on a number of college campuses. Husoski (talk) 05:15, 6 September 2011 (UTC)

The popular pair in the C99-code

A "popular pair" is not mentioned above! And it is not obvious, for what this "pair" is "popular". A Google-Search for the combination (279470273 "popular pair") finds just 56 sites, of which about halve of them refere to this English Wikipedia article. I could not find any source, that distinguishes that "popular pair" positively from other "less popular pairs". In the contrary, the majority of sites list some pairs of established or dedicated or prominente constants in the first rank and afterwards introduce the constants of the C99-code as "another popular pair is...". It is not clear, which of those sites is the original and which are just copied and pasted and from what competences all the publications about the "popular pair" descend. By this uncertainties it is almost serious, that there are no quoted sources listed.

Additionally, to my consideration (I am doing C++ professionally) the displayed C99-code does not work as a random number generator without much more supporting code and global static data structures or further explanations, relativations, restrictions and commentaries. As displayed it is useless and the nicest statement about it is, that, as a two-line-code, it probably passes the compiler without direct syntax errors. To me, the complete paragragh "Sample C99 code" might be omitted...--46.115.19.28 (talk) 19:11, 20 December 2014 (UTC)

I like having an actual example, so I rewrote this section to include two.

The "popular pair" appears to be used by various packages, such as GNU Fortran:

  https://gcc.gnu.org/onlinedocs/gcc-4.9.1/gfortran/RANDOM_005fSEED.html

The modulus 4294967291 is 2^32 - 5, and this pair is listed as having a good figure of merit in: "Tables of linear congruential generators of different sizes and good lattice structure", by Pierre L’Ecuyer, Mathematics of Computation, Volume 68, Number 225, January 1999, Pages 249–260

In my testing, it appears to generate reasonable random numbers when its own output is fed back into its input, except of course for the special case of 0. Olawlor (talk) 04:11, 28 January 2015 (UTC)

Not used by ZX Spectrum

I’ve tested the algorithm on the Spectrum emulator, which uses a copy of the original ZX Spectrum ROM so should be accurate.

It does not match $X_{k+1}=g\cdot X_{k}~~{\bmod {~}}~n$. The rand numbers (times 65536) follow $X_{k+1}=75\cdot (1+X_{k})-1~~{\bmod {~}}~65537$, starting with 74. JDAWiseman (talk) 14:01, 1 August 2016 (UTC)

The − offset is required to make the result fit into 16 bits, and once that's accounted for, it is the algorithm as described. $X_{0}=1,\;X_{k+1}=75\cdot X_{k}{\bmod {6}}5537,$ and the return value is $X_{k}-1 \over 65536$. 74.119.146.16 (talk) 01:17, 21 September 2019 (UTC)

128 bit generator is neither C99 nor portable to the compilers it claims to be

The 128 bit example invokes undefined behaviour and even where it might happen to work it relies on endianness. I think it should either be fixed (for a mere example all that buggy seeding boilerplate code is probably unnecessary and removing it might work) or simply removed. Im not bold enough for that, so I mark my few words here :) PS: even if it were not so problematic, C99 has no __int128 data type, so it's just wrong on so many levels. 78.42.244.34 (talk) 02:33, 18 February 2018 (UTC)

Masochism: a=279470273, m=2³²−5, using the recursive Schrage's method

This is too useless to appear in the main article, and was written mainly to ensure that I understood what L'Ecuyer and Côté were talking about, but it is tested. Because the modulus is larger than 2³¹, most of the overflow checks are handling 32-bit overflow; only the last one deals with the modulus.

#include <stdint.h>
#include <assert.h>

#define D 5
#define M 0xfffffffb
#define A 279470273u
#define Q1 (M/A)	// 15
#define R1 (M%A)	// 102913196
#define Q2 (M/R1)	// 41
#define R2 (M%R1)	// 75526255
#define Q3 (M/R2)	// 56
#define R3 (M%R2)	// 65497011
#define Q4 (M/R3)	// 65
#define R4 (M%R3)	// 37661576
#define Q5 (M/R4)	// 114
#define R5 (M%R4)	// 1547627
#define Q6 (M/R5)	// 2775
// Q1 * Q2 * Q3 * Q4 * Q5 * Q6 = 708181110000 > M

uint32_t lcg_rand3(uint32_t x)
{
	uint32_t y = x % Q1 * A;
	uint32_t z;

	x /= Q1;
	z = y - x % Q2 * R1;
	if (z > y)	// Subtract overflowed 32 bits
		z += M;
	x /= Q2;
	y = z + x % Q3 * R2;
	if (y < z)	// Add overflowed 32 bits
		y -= M;
	x /= Q3;
	z = y - x % Q4 * R3;
	if (z > y)
		z += M;
	x /= Q4;
	y = z + x % Q5 * R4;
	if (y < z)
		y -= M;
	x /= Q5;
	// x < Q6 is guaranteed, so we may stop now
	assert(x < Q6);
	z = y - x * R5;
	if (z > y)
		z += M;
	if (z >= M)
		z -= M;

	return z;
}

Left here for people's amusement. 74.119.146.16 (talk) 01:33, 21 September 2019 (UTC)