Talk:Pseudorandom number generator

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Top rated as Top-importance on the assessment scale

Contents

[edit] removed bad Math

Whoever added:

(Assuming one bit is produced every picosecond, a state of 64 bits would suffice as (1 picosecond)*264= over 142 million years.)

This is mistake. 1 picosecond)*264 = 18,446,744 seconds = 213 days. Well over the lifetime of a fruit fly. This is not a good example either, since generating a random number takes well over 1 picosecond, and supercomputer can generate hundreds of them or even thousands in parallel. I'd vote for removing this paragraph entirely, but I left it to be polite and discuss. I removed error, since it is so extremely misleading to anyone wanting to learn this material, I could not in good conscience leave it.

[edit] about Mersenne twister; good article is started

About Matsumoto's and Nishimura's Mersenne Twister I can say that it really works almost as Nature's randomness - believe it or not. This algorithm is already fully implemented on VOG a Russian server for board games. I've played there quite vast period of time on Backgammon arena and on Reversi one. The C function int rand (int) is not as good as PRNG based on Mersenne twister - that is for sure. Try it and feel it. Nice you've started a PRNG at last. We really needed this one. I was already thinking to do your job. Can you put some Knuth's work on this field too. About the simpliest PRNG and such.
XJam [2002.03.23] 6 Saturday (0)

[edit] dimensions?

> It has a colossal period of 219937-1 iterations, is proven to be equidistributed in 623 dimensions. Ostrich can you please explain a liitle bit more what herein dimensions means exactly? Otherwise everything else is explained as clear as can be.
XJam [2002.03.23] 6 Saturday (1st ed)


Statistical patterns in a sequence may appear in many ways. The dimensions noted are ways of examining the sequence for patterns. See Knuth Semi-numerical algorithms for more detail. Please note that this article needs serious revision, particularly with regard to CSPRNGs. It is not easy to build these and statements that 'one could' have one if one does this or that are dangerous. Someone might rely on them and get into considerable (insecure) trouble as a result. Indeed, many PRNGs are built with block cypher encryption algorithms operating in CTR mode. However, the description of CTR mode here is inadequate. Note that CSPRNGs not only must satisfy certain statistical properties, but also must not be predictable which is another kettle of bits altogether.

[edit] poor code formatting

For some reason my Delphi/Pascal code is not formated correctly with the <pre> tag. Suggestions? - Jim

[edit] Move Cryptography Material

I see that most of the material in Cryptographically secure pseudorandom number generators is repeated on its own page. Can we remove or summarize it here?

Sander123 13:13, 21 Jul 2004 (UTC)

Sander, The biggest use of RNGs is in crypto by now and so some (all?) of this coverage belongs here. Some RNGs suitable for other uses are not suitable for crypto use, so some attempt to bring out the different requirements is apposite.
As for duplication, much the same can be said for coverage of the material from a crypto perspective, so a redirect of one title to the other will probably cause difficulties. I too feel an urge to minimize duplicated content, but in this case have managed to restrain myself. I suspect we all should. ww 14:53, 21 Jul 2004 (UTC)
ww: "The biggest use of RNGs is in crypto" — are you sure? — Matt 23:16, 21 Jul 2004 (UTC)

[edit] rule of thumb

A general rule of thumb is to have only a summary paragraph about a subtopic, and include a prominent link to the subtopic article; I think we do this here, although the subtopic article (CSPRNG) is not as complete as it probably should be, and arguably the summary paragraph in PRNG is slightly too long as well. — Matt 23:16, 21 Jul 2004 (UTC)
I agree with Matt. The problem that I see is that repeating the material makes maintanace difficult. In fact I came across this because I wanted to add some material. And there is a lot of material that I want to add here--Make the requirements more explicit, say some more about the standards availlable, list designs that were broken and the problems they caused, etc, etc.
Eventually this could be quite a large topic. Should I add all that to the main page? I propose that I make sure that everthing on the main page is included in crypto page, and then summarize the main page. Everybody agree? Sander123 08:50, 23 Jul 2004 (UTC)
Seems like a sound refactoring to me, thanks. — Matt 17:00, 23 Jul 2004 (UTC)


[edit] author, author -- but no title...

In the citation to the von Neumann paper, several authors are given, but there is no title. Perhaps an editing glitch ate it? Can anyone suggest what it was before this supposed whale of an editor swallowed up our Jonah of a title? ww 08:52, 26 March 2006 (UTC)

[edit] Linked term: "random", the rap artist

The "random" link in the first paragraph goes to an article about some rap artist, named "Random." Can someone fix?

[edit] poor writing

This page hasn't been written by the world's most gifted writer. E.g.:

"Because any PRNG run on a deterministic computer (contrast quantum computer) is necessarily a deterministic algorithm" "The outputs of pseudorandom number generators only approximate some of the properties of random numbers" "Careful mathematical analysis is required to have any confidence the algorithm generates numbers that are sufficiently "random" to suit the intended use"

The whole article reads like a mathematical text book, not an article from an encyclopedia.

anon poster, It's a tricky topic and more than many, preciosn of language -- at the expense of kludgey phrasing -- is hard to avoid. Please, suggest improvements which do not do damage to the meaning (including this precision, at least where we've amanaged it). It is not easy to do. And if it is for you, have I got some articles for you to look at... ww 06:40, 19 July 2006 (UTC)
Absolutely correct: encyclopedias are meant to be informative, not a reference book for mathematical computer science geniuses. It should be informative to the uninformed and it should do so without phrases like: "computer (contrast quantum computer) is necessarily a deterministic algorithm"" which is absolutely meaningless for someone like me. The trick is to be informative without being sloppy in your language. THe problem is, is that I am too ignorant on the topic to make the required changes, which is why SOMEONE who knows better should take that initiative.--ToyotaPanasonic 02:40, 21 February 2007 (UTC)
I made pass at cleaning the article up. It is still not as clear as it could be, but I hope it is less convoluted. I also took out the 1/q generator which does not seem terribly practical and I am not aware of it's being widely used. --agr 04:16, 21 February 2007 (UTC)

[edit] Mersenne Twister Linearity

The article claims that, "However, it is possible to efficiently analyze the output of the Mersenne Twister algorithm and to detect that it is non-random (as with the Berlekamp-Massey algorithm or an extension of it, such as the Reed-Sloane algorithm)."

I've actually done the experiment with the Berlkamp-Massey algorithm and the Mersenne Twister. The Mersenne Twister is not linear.

At the risk of being pedantic, let me discuss Berlkamp-Massey. This agorithm will determine the shortest linear feedback shift register that can produce a given bit sequence. This length is the sequence's linear complexity. The algorithm is used to verify that a PRNG isn't linear (in the strict sense of being equivalent to a linear feedback shift register) and to examine its linear complexity profile.

The Mersenne Twister is not equivalent to any linear feedback shift register. The Berlkmap-Massey algorithm doesn't reveal any bias or predicatability in the output of the Mersenne Twister. That does not imply that no bias or predictablity exists. Predictability always exists if the PRNG algorithm and the internal state of the PRNG is known or can be inferred.

I'm very curious about the author's source for the claim quoted above.

[edit] More about the Mersenne Twister

I have recently experimented with the Mersenne Twister, in particular by analyzing its output with the Berlkamp-Massey algorithm. My recent changes to this page are motivated by what I discovered. For details, search the sci.crypt.random-numbers newsgroup for Mersenne Twister Linearity. I am still very interested in any actual numerical analysis of the output of this (and other!) generator's output.

[edit] Microsoft RAND function

The RAND function included in current Microsoft operating systems has only 15 bits of state and thus repeats after generating 32768 bytes.

That's a little hard to believe... do we have a source for that? --Tgr 15:35, 26 October 2006 (UTC)

In Visual Studio 2005, the default rand() produces values in 0..0x7fff. This C program: :int main() { int i,j,k; j=(rand()<<15)|rand(); for (i=0; i<0xffffffff; ++i) { k=((k<<15)|rand())&0x3fffffff; if (j==k) printf("%.8x\n", i); }} reports repeats at 0x18932e78, 0x37c97143, 0x7fffffff, 0x98932e78, 0xb7c97143. So it has a cycle length of 2^^31 values, not 2^^15 values. That implies an internal state of at least 31 bits. (The 0x1e932e78 alone doesn't indicate a cycle, it just happened those two values appeared sequentially again. PRNGs are allowed ... are SUPPOSED ... to do that occasionally.) Though, the original comment might have been referring to some other rand() shipped by Microsoft.

I've removed that line for the time being. A generator with a cycle length of 2^^31 values is still awfully bad in my book, but unfortunately not exceptionally bad. 2^^15 would be exceptionally bad. (I also rearranged the quotes at the top of the page: Jon Von Neumann's "state of sin" quote is about the distinction between random and pseudorandom numbers, not the difficulty of generating adequate pseudorandom numbers.)

[edit] R P Brent's algorithm?

R P Brent's algorithm can be used to determine the period length of deterministic PRNGs; (...)

This intriguing statement is a little isolated within the article. Could someone elaborate or provide a source or link? GdB 15:29, 3 January 2007 (UTC)

[edit] Non-uniform generators

A lot of practical uses of random numbers involves non-uniform distributions; which are often produced via a non-linear function upon a uniform random number generator: e.g. tan(x) for Gaussian pseudo-random. I've started a section.

Good luck with this subject, where can we see your efforts? This page says: A simple approximation is to use the tan(x) as the inverse cumulative gaussian and a uniform distribution from -pi to pi non-inclusive. but I don't see how that works. Ziggurat algorithm is workable and fast. Please sign your posts. Cuddlyable3 08:15, 20 July 2007 (UTC)

[edit] Knuth and Marsaglia

How can you have an article about RNG's without discussing Knuth's work on statistical testing and Marsaglia's extensive work on inventing and testing random number generators. It is naive to focus so much attention on the Twister algorithm, which in fact is far too slow and complicated for many numerical applications. There should be some discussion of the extremely efficient multiply-with-carry generators, which pass statistical testing and only emply a few machine instructions. The article needs work. DonPMitchell 04:53, 31 October 2007 (UTC)