Path: utzoo!attcan!uunet!aplcen!uakari.primate.wisc.edu!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!unmvax!ogccse!blake!whit
From: whit@blake.acs.washington.edu (John Whitmore)
Newsgroups: sci.electronics
Subject: Re: Shift register based psuedorandom # generators
Message-ID: <4590@blake.acs.washington.edu>
Date: 22 Nov 89 06:49:15 GMT
References: <5758@lindy.Stanford.EDU>
Reply-To: whit@blake.acs.washington.edu (John Whitmore III)
Distribution: na
Organization: University of Washington, Seattle
Lines: 28

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.