Anybody have a clever way of doing this? I have been using a maximal length
ring counter to create 65536 pseudo random steps, which is about all you can
expect, but I wonder if there is a more clever way. I don't want to get into
using noisy signals into analog inputs or similar foolishness.
What would be a good, lazy way to simulate dice, for instance, with true
Thanks in advance for your thoughts.
It depends on how often you need a random number and how large of a
spread. Use the internal clock and retrieve the data in milliseconds.
For large numbers, retrieve and store it several times then multiply.
According to Knuth and others, LFSRs are good at producing a random
sequence of bits, but they are not good at making random numbers by
combining successive bits into numbers. Depending on the need, they may
be good enough.
Somewhere in Knuth's "The Art of Computer Programming", Volume 2:
Seminumerical Algorithms, Chapter 3. It's not intuitive that a random
sequence of bits doesn't make a good set of random numbers. It is either
a "dirty little secret" or an "everybody knows" depending on who you
Have a look at
If multiplication is cheap, consider a linear congruential PRNG. If the
criteria aren't strict, it doesn't matter.
This is perhaps a poor idea, but others will tell.
when averaging a measurement scanned periodicaly
you remove the noise. So if you measure a noisy
but constant on average, signal and substract at
each scan time the average value, you should obtain
some random value.
In order to maximize this effect you could use an ADC with
as many bits as possible.
Did you intend to reply in this thread?
If the signal is constant but noisy, the improvement is proportional to
the square root of number of measurements averaged. Averaging 16
measurements increases accuracy by 4 times; two bits worth.
It depends on often you need the random numbers, and what else the CPU
Generating good quality pseudo random number is not quick, but
generating a quick and dirty system is very fast indeed, which sounds
what you have done.
You can always combine 16-bit registers to make a 32-bit one, or a
64-bit one. Here's a very good 64-bit one, given to me by one of the
experts in the field of pseudo random numbers. But it would take some
work to implement on 16 bits CPU, but it could be done. The question is
whether you need such quality.
/* Following a post to a few newsgroups (comp.sys.sun.admin,
comp.solaris and sci.crypt.random-numbers) on the 24th Aug 2002 on a
64-bit rng, George Marsaglia said this: */
A C version of a very very good 64-bit RNG is given below.
You should be able to adapt it to your particular needs.
It is based on the complimentary-multiple-with-carry
x(n)=a*x(n-4)+carry mod 2^64-1,
which works as follows:
Assume a certain multiplier 'a' and a base 'b'.
Given a current x value and a current carry 'c',
Then the new carry is c=floor(t/b)
and the new x value is x = b-1-(t mod b).
Ordinarily, for 32-bit mwc or cmwc sequences, the
value t=a*x+c can be formed in 64 bits, then the new c
is the top and the new x the bottom 32 bits (with a little
fiddling when b=2^32-1 and cmwc rather than mwc.)
To generate 64-bit x's, it is difficult to form
t=a*x+c in 128 bits then get the new c and new x
from the the top and bottom halves.
But if 'a' has a special form, for example,
a=2^62+2^47+2 and b=2^64-1, then the new c and
the new x can be formed with shifts, tests and +/-'s,
again with a little fiddling because b=2^64-1 rather
than 2^64. (The latter is not an optimal choice because,
being a square, it cannot be a primitive root of the
prime a*b^k+1, where 'k' is the 'lag':
x(n)=a*x(n-k)+carry mod b.)
But the multiplier a=2^62+2^47+2 makes a*b^4+1 a prime for
which b=2^64-1 is a primitive root, and getting the new x and
new c can be done with arithmetic on integers the size of x.
A C version of x(n)=a*x(n-4)+carry mod 2^64-1
follows, it is cmwc64( ), with a main program to test it.
static unsigned long long x=123456789,y,z,w,c;
/* default seeds y,z,w,c are all zero.
You should choose ANY 4 random 64-bit seeds x,y,z,w < 2^64-1
and a random seed c in 0 2^318
possible choices for seeds, the period of the RNG.
The default seeds x=123456789, y = z = w = c = 0 are OK for tests
(or for real one-time runs), but you should choose randomly
from set of P possible seeds.
unsigned long long cmwc64( )
unsigned long long t;