liz@ucscb.UCSC.EDU (Space Cadet) (11/14/89)
I am designing a shift register based psuedo-random number generator.
I have a list of feedback connections (from CMOS Cookbook) for lengths up
to 31, but may need a length up to 36 (no, 2G random numbers aren't enough
for me :-)
CMOS Cookbook does not describe how the feedback connections for an
optimal sequence are determined. If anyone knows, please post or mail me.
In lieu of that, if anyone has the feedback connections for lengths > 31,
I'd like to see them. Thanks.
John DuBois
spcecdt@ucscg.ucsc.eduwhit@blake.acs.washington.edu (John Whitmore) (11/22/89)
In article <5758@lindy.Stanford.EDU> liz@ucscb.UCSC.EDU (Space Cadet) writes: > > I am designing a shift register based psuedo-random number generator. >I have a list of feedback connections (from CMOS Cookbook) for lengths up >to 31, but may need a length up to 36 (no, 2G random numbers aren't enough >for me :-) > We did some fiddling here, a year or so ago, to determine what connections would make a good random number generator. The general scheme is this: make a computer program that simulates the shift register and the XOR gate (on the last SR bit and on one other SR bit, before the next-to-last) whose output feeds the SR input. Then put a number into the SR (one is a good number) and simulate the clocked shift. Repeat until the original number (one, as I suggested) shows up again. If this occurred at repetition # 2**N -1, your trial is a success. The scheme is guaranteed cyclic; if it is cyclic ONLY at the maximum number, 2**N-1, then it is also pseudorandom, in the sense that it went through ALMOST EVERY POSSIBLE combination exactly once before it repeated any of them. All zeros is not a possible combination for this scheme (all zeros into the XOR yields... all zeros, so repeats the first state on step #2), so 2**N is an unachievable goal. Some assembly language programming is to be suggested, here, as your 36-bit target will require a large number (seventy billion) of trials. Perhaps this is why the cookbook didn't go that high... ... I am known for my brilliance, John Whitmore by those who do not know me well.
ferguson@maitai.SRC.Honeywell.COM (Dennis Ferguson) (11/27/89)
In article <5758@lindy.Stanford.EDU> liz@ucscb.UCSC.EDU (Space Cadet) writes: > > I am designing a shift register based psuedo-random number generator. >I have a list of feedback connections (from CMOS Cookbook) for lengths up >to 31, but may need a length up to 36 (no, 2G random numbers aren't enough >for me :-) > Add the following to your list: # of FF Feedback Period 31 3,31 2,147,483,647 33 13,33 8,589,934,591 35 2,35 34,359,738,367 36 11,36 68,719,476,735 Most longer sequences are linear combinations of smaller sequences. The book by Samuel Golomb on "Shift Register Sequences" is considered the classic in this field. The mathematics in the book allows you to calculate sequences of larger registers and more importantly, how to generate very long sequences for a number of smaller registers. Dennis