31 bit pseudo-random number gen in C, C++ & dsPIC assembly code

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Most of heavy research on PRNGs (pseudo-random number generators) is
for cryptographic or simulation applications.  These generators are
generally too slow or use too much memory if all that is required is
a long sequence of random sounding numbers, such as for noise, dither
etc. in audio DSP.  Trying to find a reliable, fast, algorithm for
this purpose is tricky, since many linear congruential generators have
failings.

I have a new page:

  http://www.firstpr.com.au/dsp/rand31 /

which provides C, C++ and dsPIC assembly code for a fast, 32 bit
integer, no-division, implementation of the well-known Park Miller
(1988) "minimal standard" pseudo-random number generator.  This
follows the suggestion by David G. Carta in 1990 of how to implement
this algorithm without using division.  This generator produces 31
bit numbers, between 1 and (2^31-2) = 0x7FFFFFFE.

Park and Miller rejected Carta's work in 1993 - saying it didn't
work.  But it works fine!

I trace the history of this PRNG, look at some explanations, and give
an explanation of why Carta's approach works which is different to
and much simpler than Carta's explanation.

The dsPIC subroutine uses 18 CPU cycles, including the call and
return - so it can generate a million results a second at 20 to 30
MIPS (80 to 120 MHz).  With unoptimised C code, an 800 MHz Pentium
III can generate 13 million results a second.

 - Robin    http://www.firstpr.com.au Melbourne Australia


Site Timeline