Random: Park-Miller ala Arduino

With the macro-functions coded and tested I’ve decided to spend some time on the random functions.  Hard to believe the Park-Miller minimal standard is still in use almost 25 years after its introduction.  Well, it’s life with the Tiny Core is about to end.  It’s big, slow, and the quality can best be described as “OK”.  There are much smaller, much faster, slightly better quality choices available.  But first let’s take a closer look at the Park-Miller minimal standard generator ala Arduino.

Size

Arduino’s random function adds as much as 498 bytes to the image.  For a processor like the ATmega328, the baggage is essentially insignificant at 1.5% of the available Flash.  However, for an ATiny85 processor random consumes 6.1% of the available Flash; not devastating but a bit painful.  For the ATtiny13 random uses half of the available Flash.  Ouch!

Speed

On a 16 MHz Uno, the Libc random function takes 94.481 microseconds to generate the next value.  Fairly fast but the Tiny Core supports processors running at 1 MHz.  The Libc random function takes 1.947 milliseconds on a 1 MHz ATtiny85 processor.  On the same processor, the Arduino random function takes as much as 2.717 milliseconds to generate the next value.  That’s too long.

Quality

On the dieharder tests, Park-Miller always fails six or more tests including: diehard_dna, marsaglia_tsang_gcd, and rgb_minimum_distance.

Seeds

Valid seeds are in the range 1 to 2147483646.  Zero is fatal.

References

 

Macros are evil

After months of on-again off-again research I’ve reached the point where I can start coding in earnest.  The first problem to tackle are the macro-functions (min, abs, round).  They have undesirable side-effects; some details are available here.. http://arduino.cc/forum/index.php/topic,84364.0.html

The goal with Tiny Core Version 2 is “always choose tiny”.  When more than one implementation is available, choose the one that produces less code.

With abs the built-in functions produce less code so inline functions and overloading are the better choice.

round is the name of a Libc function.  Because of the name conflict, the old macro has caused problems… http://code.google.com/p/arduino-tiny/issues/detail?id=29  I have not been able to create a clean solution so round has been removed.

bperrybap provided the best solution for the remaining macro-functions… http://arduino.cc/forum/index.php/topic,84364.msg640438.html#msg640438