Just wonder what methods do you prefer for generation of pseudo random numbers for applications like simulation or dithering. VLV
Random numbers
Started by ●October 13, 2012
Reply by ●October 14, 20122012-10-14
On 10/13/12 10:38 PM, Vladimir Vassilevsky wrote:> Just wonder what methods do you prefer for generation of pseudo random > numbers for applications like simulation or dithering.i've used some modulo-(2^N) linear congruence in the past. i don't remember the multiplicative or additive constants (maybe i got them from Num Recipes) for a 24 or 32-bit word. for 16-bit, i thought it was x[n+1] = 0x3FFD*x[n] + 1 ; maybe for 24 and 32-bits, it was 0x3FFFFD and 0x3FFFFFFD, but i don't remember. i never really understood a theory of linear congruence RN method and what made for good constants except they were both odd so that x[n] would alternate even/odd. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●October 14, 20122012-10-14
"robert bristow-johnson" <rbj@audioimagination.com> wrote:> On 10/13/12 10:38 PM, Vladimir Vassilevsky wrote: >> Just wonder what methods do you prefer for generation of pseudo random >> numbers for applications like simulation or dithering. > > i've used some modulo-(2^N) linear congruence in the past.Linear congruental method is blaimed for many sins.> remember the multiplicative or additive constants (maybe i got them from > Num Recipes) for a 24 or 32-bit word. for 16-bit, i thought it wasThe 16 bit period is too short even for audio applications. An LCG of reasonable quality would require 64 bit math or so. Xorshift algorithm looks fast and elegant: http://en.wikipedia.org/wiki/Xorshift VLV
Reply by ●October 14, 20122012-10-14
Am 14.10.12 07:44, schrieb Vladimir Vassilevsky:> "robert bristow-johnson" <rbj@audioimagination.com> wrote: >> On 10/13/12 10:38 PM, Vladimir Vassilevsky wrote: >>> Just wonder what methods do you prefer for generation of pseudo random >>> numbers for applications like simulation or dithering. >> >> i've used some modulo-(2^N) linear congruence in the past. > > Linear congruental method is blaimed for many sins. > >> remember the multiplicative or additive constants (maybe i got them from >> Num Recipes) for a 24 or 32-bit word. for 16-bit, i thought it was > > The 16 bit period is too short even for audio applications. > An LCG of reasonable quality would require 64 bit math or so. > > Xorshift algorithm looks fast and elegant: > http://en.wikipedia.org/wiki/XorshiftIf you don't care about complexity but want high quality random number, suitable for large simulations, the gold standard is the Mersenne Twister http://en.wikipedia.org/wiki/Mersenne_twister Another proposal that passes many randomness tests is KISS from George Marsalia http://programmingpraxis.com/2010/10/05/george-marsaglias-random-number-generators/ The key point is that it is provided as very compact C code, has long period, passes randomness tests (die hard) and is easy to seed. In contrast, for seeding the Mersenne Twister you need a separate generator, and possibly draw 10^6 numbers or so to get it started. Christian
Reply by ●October 14, 20122012-10-14
On Sunday, October 14, 2012 4:38:40 AM UTC+2, Vladimir Vassilevsky wrote:> Just wonder what methods do you prefer for generation of pseudo random > > numbers for applications like simulation or dithering. > > > > VLVI trusted numerical recipes 3rd ed on this, wanting not to spend one week on the topic browsing tons of papers. Maybe will do one day (browsing papers about it).
Reply by ●October 14, 20122012-10-14
On Sun, 14 Oct 2012 10:43:13 +0200, Christian Gollwitzer wrote:> Am 14.10.12 07:44, schrieb Vladimir Vassilevsky: >> "robert bristow-johnson" <rbj@audioimagination.com> wrote: >>> On 10/13/12 10:38 PM, Vladimir Vassilevsky wrote: >>>> Just wonder what methods do you prefer for generation of pseudo >>>> random numbers for applications like simulation or dithering. >>> >>> i've used some modulo-(2^N) linear congruence in the past. >> >> Linear congruental method is blaimed for many sins. >> >>> remember the multiplicative or additive constants (maybe i got them >>> from Num Recipes) for a 24 or 32-bit word. for 16-bit, i thought it >>> was >> >> The 16 bit period is too short even for audio applications. An LCG of >> reasonable quality would require 64 bit math or so. >> >> Xorshift algorithm looks fast and elegant: >> http://en.wikipedia.org/wiki/Xorshift > > If you don't care about complexity but want high quality random number, > suitable for large simulations, the gold standard is the Mersenne > Twister > > http://en.wikipedia.org/wiki/Mersenne_twisterDespite having a huge state, the Mersenne Twister is not good enough to be used for crypto. If it's not good enough for some applications, why are you using it at all? (Ok, I can answer that: catchy name, it's included in many libraries, gives reasonable performance for non-critical applications.) I'm guessing Vlad is using a recent x86 processor for simulations. Recent x86 processors have AES acceleration instructions which means they can do crypto-quality PRNGs quickly. By quickly, I mean you should be able to get some Gb/s of PRNG out of a desktop class processor. There are numerous ways to turn a block cipher such as AES into a PRNG; I recommend CTR mode. See http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation for details of CTR (and other modes). CTR mode uses 128 bits of state. Each call to rand() increments the state as a binary counter, then returns 128 bits of counter encrypted with the key (seed). Regards, Allan
Reply by ●October 14, 20122012-10-14
Am 14.10.12 14:09, schrieb Allan Herriman:> On Sun, 14 Oct 2012 10:43:13 +0200, Christian Gollwitzer wrote: > >> Am 14.10.12 07:44, schrieb Vladimir Vassilevsky: >>> "robert bristow-johnson" <rbj@audioimagination.com> wrote: >>>> On 10/13/12 10:38 PM, Vladimir Vassilevsky wrote: >>>>> Just wonder what methods do you prefer for generation of pseudo >>>>> random numbers for applications like simulation or dithering. >> If you don't care about complexity but want high quality random number, >> suitable for large simulations, the gold standard is the Mersenne >> Twister >> >> http://en.wikipedia.org/wiki/Mersenne_twister > > > Despite having a huge state, the Mersenne Twister is not good enough to > be used for crypto. If it's not good enough for some applications, why > are you using it at all? (Ok, I can answer that: catchy name, it's > included in many libraries, gives reasonable performance for non-critical > applications.)Vlad was asking for a PRNG for simulation and dithering, and the Mersenne Twister is a standard choice in the world of physical simulations. Yes, I know it is not suitable for cryptography, but that is a different requirement than simulation. Christian
Reply by ●October 14, 20122012-10-14
"Allan Herriman" <allanherriman@hotmail.com> wrote in message news:507aab8c$0$1566$c3e8da3$76491128@news.astraweb.com...> On Sun, 14 Oct 2012 10:43:13 +0200, Christian Gollwitzer wrote: > >> Am 14.10.12 07:44, schrieb Vladimir Vassilevsky: >>> "robert bristow-johnson" <rbj@audioimagination.com> wrote: >>>> On 10/13/12 10:38 PM, Vladimir Vassilevsky wrote: >>>>> Just wonder what methods do you prefer for generation of pseudo >>>>> random numbers for applications like simulation or dithering. >>>> >>>> i've used some modulo-(2^N) linear congruence in the past. >>> >>> Linear congruental method is blaimed for many sins. >>> >>>> remember the multiplicative or additive constants (maybe i got them >>>> from Num Recipes) for a 24 or 32-bit word. for 16-bit, i thought it >>>> was >>> >>> The 16 bit period is too short even for audio applications. An LCG of >>> reasonable quality would require 64 bit math or so. >>> >>> Xorshift algorithm looks fast and elegant: >>> http://en.wikipedia.org/wiki/Xorshift >> >> If you don't care about complexity but want high quality random number, >> suitable for large simulations, the gold standard is the Mersenne Twister >> >> http://en.wikipedia.org/wiki/Mersenne_twisterMT is overly complicated and slow. Similar results could be obtained by combining several simpler PRNGs in one way or another.> Despite having a huge state, the Mersenne Twister is not good enough to > be used for crypto. If it's not good enough for some applications, why > are you using it at all?This is a valid point, too.> There are numerous ways to turn a block cipher such as AES into a PRNG; I > recommend CTR mode.My preference would be RC4 or XTEA rather then AES. Vladimir Vassilevsky DSP and Mixed Signal Consultant www.abvolt.com
Reply by ●October 14, 20122012-10-14
On 14 Oct 2012 12:09:48 GMT, Allan Herriman <allanherriman@hotmail.com> wrote:>On Sun, 14 Oct 2012 10:43:13 +0200, Christian Gollwitzer wrote: > >> Am 14.10.12 07:44, schrieb Vladimir Vassilevsky: >>> "robert bristow-johnson" <rbj@audioimagination.com> wrote: >>>> On 10/13/12 10:38 PM, Vladimir Vassilevsky wrote: >>>>> Just wonder what methods do you prefer for generation of pseudo >>>>> random numbers for applications like simulation or dithering. >>>> >>>> i've used some modulo-(2^N) linear congruence in the past. >>> >>> Linear congruental method is blaimed for many sins. >>> >>>> remember the multiplicative or additive constants (maybe i got them >>>> from Num Recipes) for a 24 or 32-bit word. for 16-bit, i thought it >>>> was >>> >>> The 16 bit period is too short even for audio applications. An LCG of >>> reasonable quality would require 64 bit math or so. >>> >>> Xorshift algorithm looks fast and elegant: >>> http://en.wikipedia.org/wiki/Xorshift >> >> If you don't care about complexity but want high quality random number, >> suitable for large simulations, the gold standard is the Mersenne >> Twister >> >> http://en.wikipedia.org/wiki/Mersenne_twister > > >Despite having a huge state, the Mersenne Twister is not good enough to >be used for crypto. If it's not good enough for some applications, why >are you using it at all? (Ok, I can answer that: catchy name, it's >included in many libraries, gives reasonable performance for non-critical >applications.)Many applications don't have stringent requirements for the "quality" of the noise generation. Most comm simulations at reasonable SNRs get by fine with the usual common PRNG methods. Sims at very, very low SNR or that are very sensitive to long patterns may need something better, and, of course, crypto has unique constraints.>I'm guessing Vlad is using a recent x86 processor for simulations. >Recent x86 processors have AES acceleration instructions which means they >can do crypto-quality PRNGs quickly. By quickly, I mean you should be >able to get some Gb/s of PRNG out of a desktop class processor.The best random number generator in the new Intel processors isnn't even PRNG, it's a true entropic random generator. You can't get much better than that other than to buy a noise diode and amplifier from NoiseCom or something like that.>There are numerous ways to turn a block cipher such as AES into a PRNG; I >recommend CTR mode. See >http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation >for details of CTR (and other modes). >CTR mode uses 128 bits of state. Each call to rand() increments the >state as a binary counter, then returns 128 bits of counter encrypted >with the key (seed). > >Regards, >AllanEric Jacobsen Anchor Hill Communications www.anchorhill.com
Reply by ●October 14, 20122012-10-14
"Christian Gollwitzer" <auriocus@gmx.de> wrote:> Vlad was asking for a PRNG for simulation and dithering, and the Mersenne > Twister is a standard choice in the world of physical simulations. Yes, I > know it is not suitable for cryptography, but that is a different > requirement than simulation.Hm, Mersenne Twister is somewhat big for dithering, too :-) While ago I made LCGs with multiplier of 2^n +/- 1. That is, no multiplication, only shift and add. Some combinations make super fast PRNGs with reasonable quality; good for dithering purpose. The quality could be improved by larger state. On related subject: how do you make Gaussian distribution from uniform random numbers? I know Muller's box and central limit sum; both are rather slow and questionable, especially if you need an accurate approximation beyond 5-6 sigma. Vladimir Vassilevsky DSP and Mixed Signal Consultant www.abvolt.com
