simple pseudo random generator
Author |
Message |
Andre #1 / 7
|
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 |
|
|
osmiu #2 / 7
|
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 |
|
|
osmiu #3 / 7
|
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 |
|
|
George Marsagli #4 / 7
|
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 |
|
|
osmiu #5 / 7
|
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 |
|
|
Mal Ka #6 / 7
|
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 |
|
|
George Marsagli #7 / 7
|
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 |
|
|
|