Hacker News Reader

Comment by ufo | Hacker News Reader

There is a seminar about PCG from its author available on youtube.

https://www.youtube.com/watch?v=45Oet5qjlms

Its a bit long but I highly recommend it. I learned a lot about RNGs from it.

Great talk! The video is also linked from the site, under 'Video' in the banner: http://www.pcg-random.org/posts/stanford-colloquium-talk.htm...

For those who didn’t bother poking around and are interested in random number generation and C++, the blog also great: http://www.pcg-random.org/blog/

All credits should go to George Marsaglia (who died in 2011).

He invented the XorShift method (2003), the LCG with good hyperplane behavior (1968), and the modern method of combining multiple poorly behaving RNGs (via function combination and output mapping) to create modern RNGs, not to mention the "diehard" tests he developed which are used to evaluate the performance of RNGs (1995).

This "PCG" algorithm, which is just xorshift(LCG), is just a typical implementation of his methods, which he even explicitly states in his papers.

Sadly Marsaglia home page with all his papers is no longer online, but they can be found scattered around the net.

https://en.wikipedia.org/wiki/George_Marsaglia

PCG is not simply Marsaglia's xorshift applied to an LCG. I'd recommend reading the paper on the site - it's quite good.

Its "she", btw.

https://en.wikipedia.org/wiki/Xorshift

Speaker mentions[0] that it is possible to get a different statistically random value every time you run the program, without any input to the program, apparently by using some tricks, but she refuses to elaborate for the camera. Can anyone explain how that works?

Has this something to do with address space randomization?

[0]:https://youtu.be/45Oet5qjlms?t=1h3m3s

> (This last one relies on the operating system placing myRNG at a different address every time the program is run. It's not as strong as the other techniques.)

from: http://www.pcg-random.org/useful-features.html#id2

Linux gives each process a 32 bit random seed, which is probably more useful (as is making a syscall). On an embedded system the address seed may well be useless anyway.

Probably not what she meant, but Linux has a RNG that extracts randomness from CPU execution time jitter: https://lwn.net/Articles/642166/

So good. I'm only about 20 minutes into it, but it addresses so many of the questions and ideas I've had about RNG.

Reply on news.ycombinator.com