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

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:

formatting link

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

formatting link
Melbourne Australia

Reply to
Robin Whittle
Loading thread data ...

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.