Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #27046

Re: LC53, a respectable random generator?

Show all headers | View raw

Andrew Haley wrote:

> Bernd Paysan <bernd.paysan@gmx.de> wrote:
>> 
>> LC53 is a maximum period linear congruent random number generator -
>> so far, so good.  It has the usual problems of LCGs, so it doesn't
>> pass any serious randomness test suite.  It is certainly not worse
>> than others,
> 
> Did you really mean to say that?  All we know is that it is not
> certainly worse.  I doubt very much that a generator chosen without
> any theoretical justification or testing is as good as any.  It's not
> impossible, but it would be a fantastic stroke of luck.

Not really, the likelyhood to find a prime root is ~O(log^6 n), so there are 
really very, very many prime roots if n is just 2^32.

> Despite all of the theoretical work that has been done, I think it's
> still true that the best way to find a "good" LC generator is to
> search for one using an automated test procedure.

The theoretical work reduces the search time.  Maximum period is just one 
condition a LC generator must pass.  This is not enough, e.g. 2 is a prime 
root of 2^32-5.  2 would be a very bad choice for g, though.

>> but it definitely is slower than the mod 2^cellbits ones.  It is
>> just a bit faster as the hash-based PRNG I use in Gforth-git now
>> (benchmarked on 64 bit machines), which does return 64 bit numbers
>> on a 64 bit machine, and so far passed all randomness tests I ran
>> from the TestU01 suite (I didn't run the very time consuming
>> DieHarder test).
> 
> Sure, any LCRNG that uses division isn't going to be fast.  A 64-bit
> computer can turn that modulo operation into a couple of
> multiplications, a shift, and a subtraction, but it's still not going
> to be fast.

Actually, even a 32 bit computer can turn *that* particular modulo operation 
into two multiplications by 5, and some addition/subtractions.  (a*2^32+b) 
mod 2^32-5 = (b + a*5) mod 2^32-5.

Thus you only need to iterate this until it's smaller than 2^32-5.  The 
multiplication by 5 itself is pretty cheap, especially on architectures like 
x86, where you can use lea for that (be aware that you also need the higher 
order part, so you need a shift right by 30, too, and keep track of your 
carry!).

> 2^31 - 1 is prime, so that's a much better choice for a
> modulus.

Yes, Mersenne primes are quicker, because you don't need any further 
multiplication for the addition above: a*2^n+b mod 2^n-1 = b+a mod 2^n-1.  
For 64 bit systems, 2^61-1 is a Mersenne prime, and 2^127-1 is also one; 
with a prime root that is just 64 bit, you could do with 2 um*s to produce a 
LCRNG with a 2^127-1 period.

It will still have the other problems of LCRNGs, so if you want a high-
quality PRNG, don't use that approach.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-23 16:25 +0000
  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-23 17:34 -0800
    Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-23 19:03 -0800
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 04:58 +0000
  Re: LC53, a respectable random generator? "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> - 2013-11-24 04:57 -0500
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 14:17 +0000
      Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-24 08:12 -0800
        Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 16:46 +0000
        Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-24 23:53 +0100
          Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-24 15:41 -0800
            Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 17:57 -0800
            Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-25 19:32 +0000
              Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 14:22 -0800
              Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-26 00:20 +0100
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 03:29 +0000
                Re: LC53, a respectable random generator? thomas.bartscher@gmail.com - 2013-11-25 23:08 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 05:06 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 14:03 +0000
                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-26 21:59 +0100
                Re: LC53, a respectable random generator? thomas.bartscher@gmail.com - 2013-11-28 01:32 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-25 19:43 -0800
              Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-25 19:31 -0800
              Re: LC53, a respectable random generator? "Elizabeth D. Rather" <erather@forth.com> - 2013-11-25 19:24 -1000
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 05:17 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 14:21 +0000
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:49 -0800
            Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 13:52 -0800
          Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 18:03 -0800
          Re: LC53, a respectable random generator? Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2013-11-25 13:41 +0100
            Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 10:23 -0800
              Re: LC53, a respectable random generator? Howerd <howerdo@yahoo.co.uk> - 2013-11-25 13:43 -0800
                Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 15:16 -0800
                Re: LC53, a respectable random generator? Howerd <howerdo@yahoo.co.uk> - 2013-11-26 13:38 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 20:42 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 11:46 +0000
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-27 18:35 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 21:41 -0800
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-27 03:21 -0600
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 15:37 +0000
                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-27 23:01 +0100
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 23:39 +0000
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 05:41 -0600
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-28 13:47 +0000
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 09:10 -0600
                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-28 16:22 +0100
                Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 09:34 -0600
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:39 -0800
                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 16:44 +0000
            Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-25 19:51 +0100
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 11:13 -0800
        Re: LC53, a respectable random generator? Hans Bezemer <the.beez.speaks@gmail.com> - 2013-11-25 09:52 +0100
  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 13:07 -0800
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-25 02:18 +0000
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 19:36 -0800
  Re: LC53, a respectable random generator? "Ed" <invalid@invalid.com> - 2013-11-26 12:57 +1100
    Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 21:25 -0800
    Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 15:48 +0000
  Re: LC53, a respectable random generator? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-11-27 01:10 -0800
    Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-27 03:29 -0600
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-27 19:49 -0800
        Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-28 15:57 +0100
          Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:14 -0800

csiph-web