avr-libc random performance?

Looking at the code in avr-libc for generating random numbers, I notice a few things:

It’s an LCG…
It requires 3 longs of stack space
There’s 3 multiplies, a division, 3 modulos, and 4 multiplies, along with 2 pointer dereferences, which I hope are optimized out
For better quality randomness, they are using an LCG modulo 2^31, making the period 2^32-1, half what you should be able to get in 32 bits.

Just out of curiosity, what is going on here? I know 32-bit shifts are expensive without a barrel shifter, but it still seems like a marsaglia xorshift generator, which looks like y^=y<<2;y^=y>>7;y^=y<<7; should be faster.

I’ll do some tests tomorrow, but I’m kinda doubtful of the quality of any LCG. I’d imagine there was some good reason for using that particular RNG, but I don’t have a clue what it was, since imho 12 bytes of stack is unacceptable to generate one random number.

The xor shift could use as little as 1 byte of stack depending on how gcc handles it.

What do you guys think?

EternityForest:
I’ll do some tests tomorrow, but I’m kinda doubtful of the quality of any LCG.

Don’t bother. It has been tested to death…
https://www.google.com/search?q=park+miller+minimum

I know 32-bit shifts are expensive without a barrel shifter, but it still seems like a marsaglia xorshift generator, which looks like y^=y<<2;y^=y>>7;y^=y<<7; should be faster.

Be very very carefully about using a Marsaglia xorshift generator. The vast majority have flaws. Some serious.

For what it’s worth, the next version of Tiny Core will use a Marsaglia xorshift generator…
http://zygomorphic.com/arduino-tiny/?p=78
http://zygomorphic.com/arduino-tiny/?p=26

[quote author=Coding Badly link=topic=227481.msg1644678#msg1644678 date=1395424953] Be very very carefully about using a Marsaglia xorshift generator. The vast majority have flaws. Some serious. [/quote]

Good to know! I'm probably using totally the wrong one of the 50+ sets of constants.

It looks like park-miller has it's own set of statistical weaknesses though, but those could be caused by the fact that half of the possible numbers will never be produced, however, even when you only output the bottom 3 bytes it still fails a few tests.

I have a library that uses xorshift(2,2,7), and a loop that just adds a random value to a counter 10,000 times executes in 183132 uS on the leonardo, for about 18us per loop, and that includes some other stuff the library does when you call random.

For anything important you should NEVER use a library random number generator. There are plenty of examples of good PRNG's that cover the gamut of needed system resources, including some with a very light footprint. The built in library PRNG's are only good for student level exercises, and for learning the value of not making assumptions!

For what it’s worth, the next version of Tiny Core will use a Marsaglia xorshift generator (continued)…
http://code.google.com/p/arduino-tiny/source/browse/cores/tiny/tc_random_XorShift.cpp?repo=core2

It's amazing how difficult of a problem good random numbers are.

I think what I a

wanderson: For anything important you should NEVER use a library random number generator. There are plenty of examples of good PRNG's that cover the gamut of needed system resources, including some with a very light footprint. The built in library PRNG's are only good for student level exercises, and for learning the value of not making assumptions!

I think I'll go with your advice and just stay away from avr-libc's rng entirely. I'm having good results using xorshift to gather entropy from micros() unpredictability due to code branches and user input. If I add bytes 0 and 2 of the rng state to create each output byte the result seems to pass dieharder. Not in any way good enough for crypto but should be good enough for my applications.

Just goes to show how you always have to do your own research and not believe every function labeled "random"....

I still think xorshift or CRC32 would be a better choice than avr-libc has now just for speed and ram use but maybe it's six of one half dozen of the other and we should all just choose our own application-appropriate RNGs.

Good intro to the subject

GoodPracticeRandomNumberGenerator.pdf (601 KB)

@Wanderson,

interesting link, thanks