Yet another pseudo-random number generator 
Author Message
 Yet another pseudo-random number generator

/*
 *  Generate random integers using the shift-register algorithm.
 *  Copyright Moshe Braner,  Nov. 1987.  All rights reserved.
 *  Permission granted for noncommercial usage.
 *
 *  The algorithm here is basically  x[i] = x[i-31]  EOR x[i-7].
 *  (Could possibly improve by using x[i] = x[i-127] EOR x[i-63]?)
 *  Each x[i] here is 32 bits wide, could also be 16 or whatever.
 */

/* "#define FRAND" to include the floating-point stuff */

static long gla[31];                    /* array of randoms to shift    */
static int  glf=1;                      /* seeding flag                 */
static long *glp, *glq, *gls, *glt;     /* pointers to shift register   */
#ifdef FRAND
static double glfm;
#endif

/*
 * Seed ran5 - always do this first.
 * The seed is any positive integer.
 */
void
sran5(seed)
        int seed;
{
        register int i;
        register long x;

        x = (long) seed;
        for(i=0; i<100; i++)
                x = 31821*x+1;
        for(i=0; i<31; i++) {
                x = 31821*x+1;
                gla[i] = x;
        }
        glf = 0;
        gls = &gla[0];
        glp = &gla[0];
        glq = &gla[24];
        glt = &gla[31];
#ifdef FRAND
        glfm = 1.0;
        for (i=0; i<31; i++)
                glfm *= 0.5;            /* EXACTLY 2^(-31) */
#endif

Quote:
}

/*
 * The basic ran5() generator, which returns
 * a long integer uniform between 0 and 2^31-1.
 */
long
ran5()
{
        register long x, y;

/* short form:

        x = ((*glp) ^ (*glq));
        if (++glp == glt)
                glp = gls;
        if (++glq == glt)
                glq = gls;
        return (x & 0x7FFFFFFF);

   safer form: */

        if (glf)
                sran5(0);
        y = x = ((*glp) ^ (*glq));      /* here fortran dies */
        x <<= 1;
        if (y < 0)
                x += 1;         /* wish C had a 'rotate' operation */
        *glp = x;
        if (++glp == glt)
                glp = gls;
        if (++glq == glt)
                glq = gls;
        return (y & 0x7FFFFFFF);

Quote:
}

#ifdef FRAND
/*
 * The floating-point ran5() generator.
 * Returns a double uniform on [0.0,1.0).
 */
double
fran5()
{
        return ((double)ran5() * glfm);
Quote:
}

#endif FRAND


Mon, 20 Jul 1992 20:58:00 GMT  
 Yet another pseudo-random number generator

Quote:
> /*
>  *  The algorithm here is basically  x[i] = x[i-31]  EOR x[i-7].
>  *  (Could possibly improve by using x[i] = x[i-127] EOR x[i-63]?)
>  *  Each x[i] here is 32 bits wide, could also be 16 or whatever.
>  */

Sounds to me like you're running 16 or 32 LCG's in parallel. This
means that:

1. Individual bits will have all the problems associated with a LCG.

2. Supposing all your seed values have bit 7 == 0. You'll never ever
        get a 1 bit in bit 7. A somwhat remote possibility, but it
        could occur.

Comments anyone?
--

                                                IHS     | +-+-+
        ....... !harvard!xait!lakart!dg                 +-+-+ |



Mon, 20 Jul 1992 20:58:00 GMT  
 Yet another pseudo-random number generator
Actually, CACM had an article on random number generators
a few months back (Nov or Dec) and gives the pseudocode for
some statistically PROVEN random generators.

--
Ray Tigg                          |  Cognos Incorporated
                                  |  P.O. Box 9707
(613) 738-1440 x5013              |  3755 Riverside Dr.
UUCP: uunet!mitel!sce!cognos!rayt |  Ottawa, Ontario CANADA K1G 3Z4



Mon, 20 Jul 1992 17:33:00 GMT  
 Yet another pseudo-random number generator

Quote:

>Actually, CACM had an article on random number generators
>a few months back (Nov or Dec) and gives the pseudocode for
>some statistically PROVEN random generators.

Virtually all PRNG schemes in common use have provable
statistical behavior.  That doesn't mean they're always
suitable.  In fact I'm not enthised about that CACM article.


Mon, 20 Jul 1992 17:21:00 GMT  
 Yet another pseudo-random number generator

Quote:
>Virtually all PRNG schemes in common use have provable
>statistical behavior.  That doesn't mean they're always
>suitable.  In fact I'm not enthised about that CACM article.

Didn't the article state that the generators they talked about
were to be considered a lower bound in quality?  In other words,
there is now no excuse to use a |worse| PRNG than the ones in the
article.
--



Mon, 20 Jul 1992 21:39:00 GMT  
 Yet another pseudo-random number generator

Quote:

>Actually, CACM had an article on random number generators
>a few months back (Nov or Dec) and gives the pseudocode for
>some statistically PROVEN random generators.

The article was in the Oct 88 issue of CACM.  However, before you use the
algorithm I suggest you read the FEB 88 issue.  The letter on page 172
points out some problems.

    Marv Rubinstein



Mon, 20 Jul 1992 03:29:00 GMT  
 Yet another pseudo-random number generator

in response to my mention of the recent CACM article on random
generators, that:

"Virtually all PRNG schemes in common use have provable
 statistical behavior.  That doesn't mean they're always
 suitable.  In fact I'm not enthised about that CACM article."

Are you refering to the need to have skewed or otherwise non-normal
distributions? Also I'm interested in knowing what you found
wanting in the CACM article.

                                        Ray Tigg
--
Ray Tigg                          |  Cognos Incorporated
                                  |  P.O. Box 9707
(613) 738-1440 x5013              |  3755 Riverside Dr.
UUCP: uunet!mitel!sce!cognos!rayt |  Ottawa, Ontario CANADA K1G 3Z4



Mon, 20 Jul 1992 18:37:00 GMT  
 Yet another pseudo-random number generator
[David Goodenough pointed out some supposed problems with my PRNG]

My method (posted here recently) is NOT parallel LCGs, it is 16 or 32
parallel occurences of the (in)famous "shift register" algorithm.
While it is true that each bit position, taken alone, is not a very
good basis for PRNs, tests show that the 32 independent "registers"
provide pretty good 32-bit random long ints.  With my method there is
no actual shifting of the bits in each register, instead I just bump
a pointer to a position on a ring.  MUCH faster.  (To make merrier, I also
roll one column in the matrix of bits (around the OTHER axis than the
rows used for the "shift" of the registers) one bit per call.  But that
is not essential.)

For seeding, I take ONE seed int and generate 31 "random" seeds out of it
using a LCG (for the seeding only).  It is true that, with VERY small
probability, one bit position may be stuck at all 0's, but the extra rolling
mentioned above will destroy that state.

I still claim that this is a very fast generator with no deficiencies known
to me.  Anybody got their favorite killer PRNG tests ready to shoot?  :-)

- Moshe Braner

Cornell Theory Center, 265 Olin Hall,
Cornell University, Ithaca, NY 14853
(607) 255-9401  (Work)




Mon, 20 Jul 1992 22:05:00 GMT  
 Yet another pseudo-random number generator

Quote:


> in response to my mention of the recent CACM article on random
> generators, that:

> "Virtually all PRNG schemes in common use have provable
>  statistical behavior.  That doesn't mean they're always
>  suitable.  In fact I'm not enthised about that CACM article."

They have good uniformity of distribution.  But this by itself is
meaningless.  Suppose that the n-th PRN is n (modulo k).  Then the
distribution is uniform.  Or one can use quasi-random numbers, such
as the fractional part of n*2(.5).  These are provably more uniform
than random numbers.  If they are to be used for estimating the integral
of a "smooth" function, even in many dimensions, and are used one-at-
a-time, then multidimensional quasi-random numbers are likely to be
much better than random numbers.

But the problem is independence.  Suppose that one is using an acceptance-
rejection or acceptance-replacement scheme to generate exponential or
normal random variables.  Then there is interaction between the uniform
input at different places.  So independence becomes important.  The
only really good ones here are the "cryptographically strong" generators,
which are quite expensive.  Some of the procedures with long seeds, like

        x[n] = x[n-460] XOR x[n-607]

with a seed of 607 words of the longest type which could be used, are
probably fairly good.  Using any type of physical random numbers XORed
with the pseudo-random numbers is likely to improve the performance;
radioactive sources, using the parity of the number of counts in intervals,
are quite good and even improve with a quite considerable dead time.
If repeatability is needed, the physical random numbers should be stored.

Quote:
> Are you refering to the need to have skewed or otherwise non-normal
> distributions? Also I'm interested in knowing what you found
> wanting in the CACM article.

The type of non-uniform random variables wanted has little to do with
the problem.  Now sometimes good results can be obtained with quasi-
random numbers; in this case, one needs a QRNG, not a PRNG.  But the
circumstances in which QRNs work well are more restrictive.
--
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054



Mon, 20 Jul 1992 14:43:00 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. Pseudo random number generator

2. Pseudo-random number generators

3. simple pseudo random generator

4. Help! Pseudo Random Function Generator in C

5. random number generator random() questionable!!!?

6. BBS pseudorandom number generator

7. Pseudorandom Number Generator Information Needed

8. pseudo-random numbers

9. Pseudo-Random Number Generater

10. More pseudo random numbers?

11. a real random number generator?

12. Random number generator

 

 
Powered by phpBB® Forum Software