simple pseudo random generator 
Author Message
 simple pseudo random generator

I am searching for a simple PRGN for my Linux-Kernel 2.4.8. It nust be
simple because the PRGN should work in an soft interrupt handler
(dev.c). I tried out some PRGNs, but they all don't seem to work as
they do in the user space... .

Maybe someone can help me with some c-code, that is working under the
conditions of kernel irq's!

Thanks, ANDREAS



Fri, 11 Jun 2004 17:48:38 GMT  
 simple pseudo random generator

Quote:
Andreas writes:
> I am searching for a simple PRGN for my Linux-Kernel 2.4.8. It nust be
> simple because the PRGN should work in an soft interrupt handler
> (dev.c). I tried out some PRGNs, but they all don't seem to work as
> they do in the user space... .

> Maybe someone can help me with some c-code, that is working under the
> conditions of kernel irq's!

I don't understand the question or the problem.  But here is a link to code
that looks good to me.   It's about 80% of the way down the page.  I have
one of Ladd's books and I have no snide personal commentary in it.  As some
of my books do.

http://www.coyotegulch.com/algorithm/ac0003/TwistedRoad.html

-----=  Posted via Newsfeeds.Com, Uncensored Usenet News  =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
 Check out our new Unlimited Server. No Download or Time Limits!
-----==  Over 80,000 Newsgroups - 19 Different Servers!  ==-----



Fri, 11 Jun 2004 21:11:51 GMT  
 simple pseudo random generator

Quote:
Andreas writes:
> I am searching for a simple PRGN for my Linux-Kernel 2.4.8. It nust be
> simple because the PRGN should work in an soft interrupt handler
> (dev.c). I tried out some PRGNs, but they all don't seem to work as
> they do in the user space... .

> Maybe someone can help me with some c-code, that is working under the
> conditions of kernel irq's!

I don't understand the question or the problem.  But here is a link to code
that looks good to me.   It's about 80% of the way down the page.  I have
one of Ladd's books and I have no snide personal commentary in it.  As some
of my books do.

http://www.coyotegulch.com/algorithm/ac0003/TwistedRoad.html

-----=  Posted via Newsfeeds.Com, Uncensored Usenet News  =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
 Check out our new Unlimited Server. No Download or Time Limits!
-----==  Over 80,000 Newsgroups - 19 Different Servers!  ==-----



Fri, 11 Jun 2004 21:11:51 GMT  
 simple pseudo random generator


Quote:
> I am searching for a simple PRGN for my Linux-Kernel 2.4.8. It nust be
> simple because the PRGN should work in an soft interrupt handler
> (dev.c). I tried out some PRGNs, but they all don't seem to work as
> they do in the user space... .

Given an initial 32-bit integer y, randomly selected from  the set
S={1,2,...,2^32-1} (unsigned long's),   application of
      y^=y<<13;  y^=y>>17;  y^=y<<5;
will produce a sequence of 2^32-1 different random integers,
each uniformly distributed over S.  They will not be independent
uniform choices from S, but will seem to behave as though
they were, satisfying all but the most demanding tests of randomness,
much better than do the more commonly used congruential RNG's.

George Marsaglia



Fri, 11 Jun 2004 19:47:02 GMT  
 simple pseudo random generator

Quote:
George Marsaglia writes:
> Given an initial 32-bit integer y, randomly selected from  the set
> S={1,2,...,2^32-1} (unsigned long's),   application of
>       y^=y<<13;  y^=y>>17;  y^=y<<5;
> will produce a sequence of 2^32-1 different random integers,
> each uniformly distributed over S.  They will not be independent
> uniform choices from S, but will seem to behave as though
> they were, satisfying all but the most demanding tests of randomness,
> much better than do the more commonly used congruential RNG's.

Does this method have a name?  I would like to explore it a bit but it's
pretty hard to do much exploring without some way of identifying it.  My
initial reaction is that I find it  interesting.  For example where do the
magic numbers come from?

-----=  Posted via Newsfeeds.Com, Uncensored Usenet News  =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
 Check out our new Unlimited Server. No Download or Time Limits!
-----==  Over 80,000 Newsgroups - 19 Different Servers!  ==-----



Fri, 11 Jun 2004 22:21:25 GMT  
 simple pseudo random generator

Quote:

> George Marsaglia writes:

> > Given an initial 32-bit integer y, randomly selected from  the set
> > S={1,2,...,2^32-1} (unsigned long's),   application of
> >       y^=y<<13;  y^=y>>17;  y^=y<<5;
> > will produce a sequence of 2^32-1 different random integers,
> > each uniformly distributed over S.  They will not be independent
> > uniform choices from S, but will seem to behave as though
> > they were, satisfying all but the most demanding tests of randomness,
> > much better than do the more commonly used congruential RNG's.

> Does this method have a name?  I would like to explore it a bit but it's
> pretty hard to do much exploring without some way of identifying it.  My
> initial reaction is that I find it  interesting.  For example where do the
> magic numbers come from?

Off topic but anyway:

It is an adaptation from (what in the past was) a hardware pseudo random
sequence generator comprising a 'n' stage shift register with input the
modulo
2 sum of the last stage output and one or more intermediate stages.
Apparently
there is no formula for determining which output combinations work; it
is a
matter of testing each combination. Either the sequnece will repeat in a
maximal pow(2,n)-1 shifts or degenerate into a number of different
possible shorter
sequences dependent on starting point. Of course one state must be
inhibited,
all zeros with an even number of stage outputs combined for next input,
or all ones with an odd number of stage outputs combined.



Fri, 11 Jun 2004 20:54:21 GMT  
 simple pseudo random generator

Quote:

> George Marsaglia writes:

> > Given an initial 32-bit integer y, randomly selected from  the set
> > S={1,2,...,2^32-1} (unsigned long's),   application of
> >       y^=y<<13;  y^=y>>17;  y^=y<<5;
> > will produce a sequence of 2^32-1 different random integers,
> > each uniformly distributed over S.  They will not be independent
> > uniform choices from S, but will seem to behave as though
> > they were, satisfying all but the most demanding tests of randomness,
> > much better than do the more commonly used congruential RNG's.

> Does this method have a name?  I would like to explore it a bit but it's
> pretty hard to do much exploring without some way of identifying it.  My
> initial reaction is that I find it  interesting.  For example where do the
> magic numbers come from?

I call this a 3-shift shift register RNG.
I have described it in various articles and
it is one of a number of good but easily implemented
RNG's that I posted in response to requests for RNG's in C,
two or so years ago.
Those posts are probably available on deja.news

Theory is based on binary vector spaces and
32x32 binary matrices of the form
     T=(I+L^a)(I+R^b)(I+L^c),
where L is the matrix that effects a left shift of 1,
and R, its transpose, effects a right shift of 1.
Thus if y is a 1x32 binary vector, (unsigned long),
the transformation yT on the binary vector space
may be implemented through
         y^=y<<a; y^=y>>b; y^=y<<c;
In  "Matrices and the structure of random number sequences"
{\it Linear Algebra and its Applications},
{\bf 67}, 147--156, (1985),
I proved that the sequence of y's will have
period 2^32-1 if and only if T has order 2^32-1
in the group of nonsingular 32x32 binary matrices.

To find all such T's, one may represent
matrices A and B as arrays of 32-bit integers,
say A[32],B[32].  Then, with elements of E[32] the rows
of the identity matrix, A*B=C may be found as follows:
  for(i=0;i<32;i++){ sum=0;
               for(j=0;j<32;j++) if(A[i]&E[j]) sum^=B[j];
         C[i]=sum; }
With such a fast method for evaluating matrix products,
and thus T^k for k=2^32-1 or k=(2^32-1)/p for each prime
divisor of 2^32-1,it takes only a few minutes to find all
possible T's, that is, triples a,b,c for which
          y^=y<<a; y^=y>>b; y^=y<<c;
will produce all 32-bit integers from an initial y!=0.
There are 160 such triples.   My favorite is 13,17,5.

For each of those choices, the transpose,
         y^=y>>a; y^=y<<b; y^=y>>c;
will also produce all possible non-zero binary vectors
(unsigned long's).

I found all such triples years ago using fortran.
In response to the increasing use of 64-bit integers,
I recently undertook to find all the 64-bit solutions.
Since Fortran doesn't seem to have been extended to
64 bit integers, I first turned to Maple, in which it
is easy to define and ask for the characteristic
polynomial of T, then see if that polynomial is
primitive mod 2.   But Maple took over 200 hours to
find all such 64x64 T's with primitive characteristic
polynomials, (on three desktops, 850,850,500 MHz and
one laptop 500MHz.  It burned out my laptop).

Finally, I turned to C, where I am a novice,
and wrote a program that found all such T's
by the fast matrix multiplication, in some 8 minutes.

Of the 250,047 possible triples a,b,c there are 550
for which
       y^=y<<a; y^=y>>b; y^=y<<c;
will generate all 2^64-1 non-zero long long's, and
another 550 based on the tranpose matrix T':
       y^=y>>a; y^=y<<b; y^=y>>c;

I will post them, (32 and 64 bits) if asked,
as well as invite suggestions on improvements
to my rather inelegant C program for finding them,
if anyone is interested.

George Marsaglia



Sat, 12 Jun 2004 00:48:50 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Pseudo random number generator

2. Help! Pseudo Random Function Generator in C

3. Yet another pseudo-random number generator

4. Pseudo-random number generators

5. Simple random # generator

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

7. Any good methods for generating pseudo random integer?

8. pseudo-random numbers

9. pseudo-random

10. Pseudo-Random Number Generater

11. More pseudo random numbers?

12. digits of pi useful as pseudo-random number generator?

 

 
Powered by phpBB® Forum Software