Random: Overview

Overview

From this overview it is clear there are better choices for the random function in Tiny Core.  Even the Xorshift-16 generator is a good choice for some applications (like a Blinky).

Algorithm Code Data Speed Quality Notes
Park-Miller 498  4 1.947 – 6
Xorshift 126  4 0.323 – 4 primary choice, normal quality
JKISS32 356 20 0.433 +1 high quality
CRC32 104  4 0.610 – 1 secondary choice, better quality
Xorshift-16  34  2 0.044 low use for ’13, maybe ‘2n

The Plan

The current plan is to use Xorshift as the default generator.  Of the generators evaluated, it isn’t the smallest nor the fastest nor the best quality.  It is small, fast, andgood quality so it is a very nice compromise.

The CRC32 generator will be an available option as a better quality smaller generator.

The JKISS32 generator will be an available option as a very high quality generator on all but the processors with the least memory (probably only excluding the ATtiny13).

The Xorshift-16 generator will be the default for the ATtiny13 processor and possibly the ATtiny25 and ATtiny24 processors.

Random: Xorshift-16

The last generator tested is a 16 bit Xorshift.  With such a short cycle length (64K) a 16 bit generator is not expected to perform well on any meaningful statistical tests like dieharder and this generator does not disappoint.  It consistently fails every dieharder test!

However, it does perform well on the ent tests.  Obviously, it is extremely fast and very small making it a good candidate for the Tiny Core.

Size

Xorshift-16 adds 34 bytes to the image which is significantly less than all the other generators.

Speed

On a 1 MHz ATtiny85 processor Xorshift-16 takes 0.044 milliseconds (44 microseconds) to generate the next value which is more the 44 times (!) faster than the Libc random function and significantly faster than all the other generators.

Quality

Xorshift-16 consistently fails all the dieharder tests.  It performs well on the ent tests.

Seeds

Valid seeds are in the range 1 to 216-1 (0xFFFF).  Zero is the only bad seed and is fatal.

References

Status

Matches Delphi.

Random: CRC32

The 32 bit CRC polynomial 0xEDB88320 is a good quality very small random number generator.  Unfortunately, the simple loop version is also very slow.

Size

CRC32 adds a very modest 104 bytes to the image which is significantly less than the 454 bytes added by the Libc random function.

Speed

On a 1 MHz ATtiny85 processor CRC32 takes 0.610 milliseconds to generate the next value which is significantly faster than the 1.947 milliseconds taken by the Libc random function.

Quality

On the dieharder tests, CRC32 always fails one test: diehard_rank_32x32.

References

Status

Matches Delphi.

Random: JKISS32

May 2010 David Jones published Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications.  Even though the article has “for Bioinformatics Applications” in the title the material applies to most applications that make use of pseudo-random number generators.  The article includes a generator (JKISS32) that may be of interest to Tiny Core users.  The generator uses considerably more SRAM than the other generators (20 bytes versus 4 bytes) but it is smaller, faster, and much higher quality than the Libc random function.

Size

JKISS32 adds 356 bytes to the image which is less than the 454 bytes added by the Libc random function.

Speed

On a 1 MHz ATtiny85 processor JKISS32 takes 0.433 milliseconds to generate the next value which is significantly faster than the 1.947 milliseconds taken by the Libc random function.

Quality

Outstanding.  Refer to the article for details.

References

Random: Xorshift

July 2003 George Marsaglia introduced the world to xorshift random number generators.  His claim that they “pass tests of randomness very well” is arguable.  His claim that they are “simple, extremely fast random number generators” is not.  They are definitely simple and extremely fast.  They also produce small code.  A perfect candidate for the Tiny Core!

All combinations of 32-bit triples and xorshift formulas were tested using dieharder.  Marsaglia’s “favorite” seems to perform better than the others.  However, it also produces slightly larger and slightly slower code.

Size

Marsaglia’s favorite adds 126 bytes to the image which is significantly less than the 454 bytes added by the Libc random function.

Speed

On a 1 MHz ATtiny85 processor Marsaglia’s favorite takes 0.323 milliseconds to generate the next value which is significantly faster than the 1.947 milliseconds taken by the Libc random function.

Quality

On the dieharder tests, Marsaglia’s favorite (and the other xorshift generators) always fails four tests including: diehard_rank_32x32, diehard_count_1s_str, rgb_bitdist, dab_monobit2.

Seeds

Valid seeds are in the range 1 to 232-1 (0xFFFFFFFF).  Zero is the only bad seed and is fatal.

References

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