Nj Dl Number Generator
James Talbot
Part of what I do is study typical behavior of large combinatorial structures by looking at pseudorandom instances. But many commercially available pseudorandom number generators have known defects, which makes me wonder whether I should just use the digits (or bits) of $\pi$.
A colleague of mine says he "read somewhere" that the digits of $\pi$ don't make a good random number generator. Perhaps he's thinking of the article "A study on the randomness of the digits of $\pi$" by Shu-Ju Tu and Ephraim Fischbach. Does anyone know this article? Some of the press it got (see e.g. ) made it sound like $\pi$ wasn't such a good source of randomness, but the abstract for the article itself (see ) suggests the opposite.
If you are worried about the quality of random digits that you're getting, then you may want to use cryptographic random number generators. For example, finding a pattern in the Blum-Blum-Shub random number generator would probably yield a new algorithm for factoring large integers! Cryptographic random number generators will run more slowly than the "commercial" random number generators you're talking about but you can certainly find some that will generate digits faster than algorithms for computing $\pi$ will.
In a technical sense, no. A good pseudorandom number generator would be one that you can plug into any randomized algorithm and expect to see the same behavior that you would from an actual random number generator. One way of making a technical definition out of this is to say that the pseudorandom number generator cannot be distinguished from truly random (with probability bounded away from 1/2) by any polynomial time test.
For the same reason, no fully deterministic sequence can be a good random sequence. Instead, to fit this definition, you need to use a pseudorandom number generator that takes some number n of truly random bits as an input seed and generates from them a longer sequence (polynomial in n) of pseudorandom bits that cannot be distinguished from random by a polynomial time algorithm.
I'd say no if you are using the random numbers to generate cryptographic keys, then you immediately open yourself to attacks, because the attacker can probably mimic your random number generator, and thus you add one weak link into the chain.
But are the digits "as good as random"? The short answer is that, as far as anyone can tell, the answer seems to be empirically yes (See Marsaglia's On the Randomness of Pi and Other Decimal Expansions). That is, there are no known ways in which the digits of $\pi$ behave systematically unlike a random number.
There are several other answers here that I think are confusing on this point. Let me explain why some of the claims made by other answers (despite being technically correct and in certain ways very insightful) don't disprove the claim that the digits of $\pi$ are as good as random.
Cryptographic PRNG's are the gold standard since if you have a practical way to detect the slightest non-randomness in the output, that is considered a break against the generator, and a significant research result (in cryptanalysis) if the PRNG was considered any good (say if it was based on AES, the Advanced Encryption Standard, in some sensible way). It's easy to make them deterministic: for any key K, just take the encryptions E(0), E(1), E(2), ... where E is the encryption function.
Recent x86 computers have a hardware instruction for AES encryption, so it is very fast. It wouldn't surprise me if AES using the hardware instruction is faster than Mersenne Twister implemented in software.
Given all digits of a sequence S till a certain length say n ie di ( i = 1 to n) ; if the probability of any next block of digits B in next m digits ( m -> infinity ) can be ascertained as < 1/(b^w) where b is the base and w is the string length of the block , through an algorithm which is guaranteed to halt then S is NOT a random sequence.
Direction of analysis is also important. Suppose there is a civilization where constant Pi has not been discovered yet ( let alone its formula), here a only a reverse analysis would be possible and the probability of one chancing upon the spigot formula while analysing the digits of Pi cannot be ruled out though its remote. Other wise the equidistribution of digits would lead such a civilisation to take Pi sequence as random
A random number is a number chosen from a pool of limited or unlimited numbers that has no discernible pattern for prediction. The pool of numbers is almost always independent from each other. However, the pool of numbers may follow a specific distribution. For example, the height of the students in a school tends to follow a normal distribution around the median height. If the height of a student is picked at random, the picked number has a higher chance to be closer to the median height than being classified as very tall or very short. The random number generators above assume that the numbers generated are independent of each other, and will be evenly spread across the whole range of possible values.
A random number generator, like the ones above, is a device that can generate one or many random numbers within a defined scope. Random number generators can be hardware based or pseudo-random number generators. Hardware based random-number generators can involve the use of a dice, a coin for flipping, or many other devices.
A pseudo-random number generator is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. Computer based random number generators are almost always pseudo-random number generators. Yet, the numbers generated by pseudo-random number generators are not truly random. Likewise, our generators above are also pseudo-random number generators. The random numbers generated are sufficient for most applications yet they should not be used for cryptographic purposes. True random numbers are based on physical phenomena such as atmospheric noise, thermal noise, and other quantum phenomena. Methods that generate true random numbers also involve compensating for potential biases caused by the measurement process.
Let me be a little clearer on point 2: There is no way for players to cheat by knowing the random numbers. Period. I want it random enough that people (at least those who understand randomness) can't complain about it, but I'm not worried about predictions.
I've used this one all over the place. The only place it failed was when I was trying to produce random binary matrices. Past about 95x95 matrices, it starts generating too few or too many singular matrices (I forget which). It's been shown that this generator is equivalent to a linear shift feedback register. But unless you are doing cryptography or serious monte carlo work, this generator rocks.
There are much better choices than Mersenne Twister nowadays. Here is a RNG called WELL512, designed by the designers of Mersenne, developed 10 years later, and an all around better choice for games. The code is put in the public domain by Dr. Chris Lomont. He claims this implementation is 40% faster than Mersenne, does not suffer from poor diffusion and trapping when the state contains many 0 bits, and is clearly a lot simpler code. It has a period of 2^512; a PC takes over 10^100 years to cycle through the states, so it is large enough.
In .NET 6 (currently in preview) the implementation of System.Random has been changed to use xoshiro256**, but only for the parameterless constructor. The constructor that takes a seed uses the old PRNG in order to maintain backwards compatibility. For more info see Improve Random (performance, APIs, ...)
Buy a cheap webcamera, a ionizing smoke detector. Disassemble both of them, smoke detector contain little radioactive material - a source of gamma waves - which will result in firing photons at your webcamera. That's your source of true randomness :)
In most game applications speed is really the critical factor, since players are going to complain about low framerate a lot more than they will complain about the fact that there is a slight bias towards generating a 3 whenever it is preceded by a 7, 2, and 9 in that order.
Starting with Ivy Bridge architecture Intel added RdRand CPU instruction and AMD added it later in June 2015. So if you are targeting a processor that is new enough and don't mind using (inline) assembly, the fastest way to generate random numbers should be in calling RdRand CPU instruction to get a 16- or 32- or 64-bit random number as described here. Scroll to approximately the middle of the page for code examples. At that link there is also a code example for checking the current CPU for support of RdRand instruction, and see also the Wikipedia for an explanation of how to do this with the CPUID instruction.
Related question: Making use of sandy bridge's hardware true random number generator? (though according to Wikipedia, RdRand instruction first appeared in Ivy Bridge, but not Sandy Bridge architecture as that question says)
On that WELL page I linked you to, the number is the period of the algorithm. That is, you can get 2^N - 1 numbers before it needs reseeding, where N is: 512, 1024, 19937, or 44497. Mersenne Twister has a period of N = 19937, or 2^19937 - 1. You'll see this is a very large number :)
In a real-time game, there's no way for a player to determine the difference between a "good" generator and a "bad" one. In a turn-based game, you're right--some minority of zealots will complain. They'll even tell you stories, in excruciating detail, of how you ruined their lives with a bad random number generator.
IBAA (rc4?) is also one that is used by blizzard to prevent people from predicting the random number used for loot rolls.. I imagine something similar is done w/ diablo II when you are playing off of a battle.net server.
This approach will build a self contained random generator, and I found it to be a lot more random than rand()%x; over a few hundred thousand iterations. rand()% would never throw 16+ heads/tails in a row, when it should every other 65k attempts. This one not only does that, but it does it in a quarter of the time.
c80f0f1006