Pages: [1]   Go Down
Author Topic: avr-libc random performance?  (Read 325 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 43
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Looking at the code in avr-libc for generating random numbers, I notice  a few things:
https://github.com/vancegroup-mirrors/avr-libc/blob/master/avr-libc/libc/stdlib/rand.c

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?
Logged

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 176
Posts: 12283
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Quote
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
« Last Edit: March 21, 2014, 03:52:09 pm by Coding Badly » Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 43
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

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.



Logged

Dallas, Texas
Offline Offline
God Member
*****
Karma: 3
Posts: 717
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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!
Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 0.7.2

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 176
Posts: 12283
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset


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
Logged

Offline Offline
Newbie
*
Karma: 0
Posts: 43
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

I think what I a
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.
Logged

Dallas, Texas
Offline Offline
God Member
*****
Karma: 3
Posts: 717
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Good intro to the subject

* GoodPracticeRandomNumberGenerator.pdf (600.8 KB - downloaded 9 times.)
Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 0.7.2

Global Moderator
Netherlands
Offline Offline
Shannon Member
*****
Karma: 168
Posts: 12428
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

@Wanderson,

interesting link, thanks
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Pages: [1]   Go Up
Jump to: