Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

PCG, A Family of Better Random Number Generators

pcg-random.org

Post reply on HN
Print view View original

41–50 of 57 posts

Re: PCG, A Family of Better Random Number Generators

#41

Post by justincormack »

echaozh wrote: post #40
vtsrh wrote: post #28

Earlier quoted context omitted.

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.

Re: PCG, A Family of Better Random Number Generators

#42

Post by pcrng »

jacobolus wrote: post #33
ufo wrote: post #5

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

Re: PCG, A Family of Better Random Number Generators

#43

Post by yoklov »

vtsrh wrote: post #34

This is great, but everything so far is overly positive. Can we get some negative criticism as well. Anyone qualified?

I'm not really qualified to speak as to its statistical properties, but I've used this generator a couple times.

The biggest downside I ran into is that it requires 64 bit numbers even for the 32 bit RNG, which means its very simple code becomes more complex on a platform with only 32 bit numbers, or in a scripting language. Also, it's not a CSPRNG, if this matters to you.

This is minor though, and I would use it again. It's flexibility for seeding and easy serialization outweigh this IMO (and it's still simple compared to e.g. mtrand)

Re: PCG, A Family of Better Random Number Generators

#44

Post by [deleted] »

pcrng wrote: post #42
jacobolus wrote: post #33

Earlier quoted context omitted.

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…

[deleted]

Re: PCG, A Family of Better Random Number Generators

#45

Post by dminor »

pcrng wrote: post #42
jacobolus wrote: post #33

Earlier quoted context omitted.

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…

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

Re: PCG, A Family of Better Random Number Generators

#46

Post by dhekir »

vtsrh wrote: post #34

This is great, but everything so far is overly positive. Can we get some negative criticism as well. Anyone qualified?

I must have done something wrong, but I tried the basic C implementation (https://github.com/imneme/pcg-c-basic) on a quick Diehard-like test and it failed. I'm still trying to understand why. Probably not its fault, just that the code is not as forgiving and ready-to-consume as I had expected.

Re: PCG, A Family of Better Random Number Generators

#47

Post by vtsrh »

dhekir wrote: post #46
vtsrh wrote: post #34

This is great, but everything so far is overly positive. Can we get some negative criticism as well. Anyone qualified?

I must have done something wrong, but I tried the basic C implementation ( https://github.com/imneme/pcg-c-basic ) on a quick Diehard-like test and it failed. I'm still trying to understand why. Probably not its fault, just that the code is not as forgiving and ready-to-consume as I had expected.

It passed for me. Where did you get the diehard test? If you compiled it directly from http://www.stat.fsu.edu/pub/diehard/ then it is because that source is broken.

Re: PCG, A Family of Better Random Number Generators

#48

Post by ufo »

pcrng wrote: post #42
jacobolus wrote: post #33

Earlier quoted context omitted.

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…

Its "she", btw.

Re: PCG, A Family of Better Random Number Generators

#49

Post by pdw »

vtsrh wrote: post #28
ufo wrote: post #5

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.

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

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