Re: pseudo-random generator -- save state

From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 11/14/05

  • Next message: karl malbrain: "T. Kwon's hash functions for AMP in IEEE P1363.2" 
    Date: 14 Nov 2005 22:43:02 GMT

    "Cristiano" <cristiano.pi@NSquipo.it> writes:

    >George Marsaglia wrote:
    >> The following C program generates the base-b 'digits"
    >> of 1/p for the prime p=18782*2^131072+1 in reverse order,
    >> with b=2^32-1.
    >>
    >> static unsigned long Q[4096],c=362436;
    >>
    >> unsigned long CMWC4096(void){
    >> unsigned long long t, a=18782LL,b=4294967295LL;
    >> static unsigned long i=4095;
    >> unsigned long x,r=b-1;
    >> i=(i+1)&4095;
    >> t=a*Q[i]+c;
    >> c=(t>>32); t=(t&b)+c; if(t>r) {c++; t=t-b;}
    >> return(Q[i]=r-t); }
    >>
    >[...]
    >> Fast and simple, it seems to pass tests of
    >> randomness very well.

    >Yes, but I would say that some kind of initialization (of the Q[] vector)
    >should be avoided.

    Here you say it should be avoided and then you say it should be done with a
    PRNG. But that would not give the digits of 1/p In fact that program seems
    to be pretty weird. For the first 4096 "digits" all you get are basically
    the initial values of Q[i]

    >For example, Q[i]= i * K, for any K gives bad results. Also Q[i]= (i * K) +
    >... + (i * K) is bad.
    >I would suggest to use at least a PRNG (even an LCG) to initialize the Q[]
    >vector. In that case, your generator seems very good, it never fails the
    >tests.

    And that is probably a statement about your initial initialisation of Q,
    rather than about this generator.

     And what tests?

    Note that this is not a cryptographically strong.
    Again, what does the OP want these for.

  • Next message: karl malbrain: "T. Kwon's hash functions for AMP in IEEE P1363.2"

    Relevant Pages

    • Re: pseudo-random generator -- save state
      ... > generator whose state can be saved and restored so it would pick up ... The following C program generates the base-b 'digits" ... "On the randomness of Pi and other decimal expansions", ...
      (sci.crypt)
    • Re: Simple random number generator?
      ... no need for fancy pyooter algorithms? ... Inneresting article on pi, randomness, chaos. ... Is it not the case that the digits of e, ...
      (sci.math)
    • Re: Good enough for crypto?
      ... to a few other hardware randomness generators that are ... > assess the quality of any sequence of bits. ... This type of analysis can only succeed if the generator ... > The autocorrelation function of a non-deterministic sequence will ...
      (sci.crypt)
    • New, state-of-the-art random number generator: simple, strong and fast
      ... small and high dimensions) is the decimals of Pi. ... character being superior to most algorithms currently implemented ... for a new random number generator, ... to use the digits of a number defined by formula, ...
      (sci.stat.math)
    • New, state-of-the-art random number generator: simple, strong and fast
      ... small and high dimensions) is the decimals of Pi. ... character being superior to most algorithms currently implemented ... for a new random number generator, ... to use the digits of a number defined by formula, ...
      (sci.math)