best pseudo random number generator
Just a quick update, as the answers show their age: Today the Mersenne Twister is not really considered state of the art anymore (somewhat bloated, predictable given just 624 values, slow to seed, bad seeding possible, ...).
Normal PRNG
For normal applications, where good statistical properties and speed are important, consider
- O'Neill's PCG family,
- Vigna's xoroshiro family, say xoroshiro128+ (not a Japanese name btw, but "X-or, rotate, shift, rotate"), and
- D. E. Shaw's Random123 suite (which includes Philox and the nicely named ARS, a simplification of encrypting an infinite sequence of zeros with AES-CTR), though I'm not sure how much the Random123 PRNG have been scrutinised.
Cryptographically secure PRNG (CSPRNG)
For cryptographic applications, where non-predictability is important, consider a cryptographically secure PRNG, such as
- Bernstein's ChaCha20, RFC 7539. Alternatives would be
- Wu's HC-256,
- Jenkins's ISAAC64.
Note: In a previous version I stated that the Random123 algorithms are cryptographically secure, but they're not.
PRNG Testing
Similarly, for statistical tests of PRNG, nowadays the state of the art is probably
- L'Ecuyer's TestU01 (with SmallCrush, Crush, BigCrush),
- Doty-Humphrey's pracrand with its PractRand suite,
while these are historically important, but outdated:
- Marsaglia's DieHard, DieHarder,
- NIST 800-22 A.
Try MT's successor: SFMT ( http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html ). The acronym stands for SIMD-oriented Fast Mersenne Twister. It uses vector instructions, like SSE or AltiVec, to quick up random numbers generation.
Moreover it displays larger periods than the original MT: SFMT can be configured to use periods up to 2216091 -1.
Finally, MT had some problems when badly initialized: it tended to draw lots of 0, leading to bad quality random numbers. This problem could last up to 700000 draws before being compensated by the recurrence of the algorithm. As a consequence, SFMT has also been designed to leave this zero-excess state much quicker than its elder.
Check the link I've given at the beginning of this post to find the source code and the scientific publications describing this algorithm.
In order to definitely convince you, you can see here http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html a table comparing generation speeds of both MT and SFMT. In any case, SFMT is quicker while laying out better qualities than MT.
-- edit following commentaries --
More generally, when you're choosing a PRNG, you need to take into account the application you're developing. Indeed, some PRNGs fit better to some applications constraints. MT and WELL generators for instance aren't well suited for cryptographic applications, whereas they are the best choice when dealing with Monte Carlo Simulations.
In our case, WELL may seem ideal thanks to its better equidistribution properties than SFMT. Nonetheless, WELL is also far slower and he's not able to display periods as large as SFMT.
As a conclusion, a PRNG cannot be stated as best for all the applications, but for a particular domain and in particular circumstances withal.
If you look for an algorithm, that passes all statistical tests, but is still fast you could try the Xorshift-Algorithm. Compared with the random library in Java it is about 30% faster and provides better results. Its Period is not as long as the Mersenne Twister's but its still decent.
An implementation can be found here:
http://demesos.blogspot.com/2011/09/replacing-java-random-generator.html
Edit
It seems that new Variants of XORShift now even beat MerseneTwister and WELL in Quality (not in period though). They pass more empirical quality tests as can be seen in the PRNG Shootout.
They are impressive in performance as well. I did a Benchmark of different implementations in Java, source and results here: https://github.com/tobijdc/PRNG-Performance