BC's Random Number Generator
============================



Preface
=======

The Rockbox Random Number Generator (Marseinne Twister), is indeed quite an
impressive bit of code and produces an excellent spread of random numbers.

On the other hand it takes about 7K of memory and is INCREDIBLY slow (by
comparison).

You may enjoy reading my original notes from "The art of computer programming",
"Seminumerical algorithms Volume 2"

On the other hand you may just want a super-fast, memory efficient random
number generator.



Usage
=====

At the top of your code place:

    #include "lib/bc_rnd.h"


Before you request a random number, set the "seed" with:

    bc_seed(*rb->current_tick);


Request a NEW random number with:

    i = bc_rnd();


Request the LAST random number again with:

    i = bc_rndN();


Request the initial seed value with:

    i = bc_rndS();


...That's all folks!



Original Notes
==============

X <- (aX + c) mod m

X0 is arbitrary and known as the 'seed'.

A seed may be a given value - this way the same 'random' sequence may be
recreated, this is appropriate if you wish to reproduce the same set of results
twice - for instance in debugging.

Alternatively a 'random' seed may be chosen.  A few standard sources of seed
selection follow:
X0 = date + time
X0 = precise time between two keystrokes
X0 = CRC of an arbitrary file
X0 = sample from a microphone

m > 2^30

you may choose a precise power of two to coincide with the word size of your
computer (standardly 2^32).

If m is a precise power of two, choose a such that:
a mod 8 = 5

If m is a precise power of ten, choose a such that:
a mod 200 = 21

0.01m < a < 0.99m

This one's a bit wishy washy...
The binary and the decimal digits should offer no simple regular pattern.
...followed by...
One almost always obtains a reasonably good multipler.
...it all started well i suppose!

c is immaterial if a is a good multiplier, except c must have no factor in
common with m.  Thus we may choose c=1 or c=a.

The least significant digits of X will not be too random, and decisions based
on x should be influenced, primarily, by the most significant digits.
As such, it is best to consider X as a random fraction:
0<= X/m <1
Visualise X with a decimal point to its left.


0 < X < m-1
If you require a number in the range 0 < X < K-1, use:
K = K(X/m)

Alternatively, Algorithm S:
1. records-seleted-so-far: 		m = 0
   total-of-all-records-input-so-far:	t = 0
2. generate-random-number:		u = random
3. if (k-t)u >= n - m, goto (5)
4. m = m + 1
   t = t + 1
   if m < n, goto (2)
   else success, our chosen random number is u
5. t = t + 1
   goto (2)
to paraphrase... "at first this equation looks dodgy, but if you work it out
it's actually ok"

If you want to start applying "Euclids test" and "sprectral test" to advance
your generator to "monte carlo" standard I suggest you have a better grasp of
maths than me and go and buy:
-----------------------------------------------------------------------------
Seminumerical algorithms
The art of computer programming
Vol 2.
Addison Wesley
3822
isbn: 0-201-03822-6
-----------------------------------------------------------------------------
...this book also contains a whole host of other really interesting shit
(including: prime generation, factoring in to primes, polynomial analysis,
discreet fourier transforms, cyclic convolution etc.)

All information in this doument was pilfed from this book, and is in itself a
summary of the summary.