🚀 go-pugleaf

tgl+@cs.cmu.edu (Tom Lane) writes:
>What I need is a very very fast random number generator; it does NOT need to
>be cryptographically strong.  The application is in generating random noise
>for dithering a color image.  I need about 8 random bits on each call
>(randomness of the low order bits is less important than the higher).
>Ideally it would take, say, just a shift and XOR per value.  The code has to
>be portable C, so circular shifts and other non-C operations are out.

Sounds like what you want may be a PN generator.  I don't have any
references on them, but that's a start.  They're very fast, they're
_almost_ random by all the usual tests, they're just slick.  It's been
a while since I did them in software rather than hardware, but here's
the basic loop, I believe:

	unsigned int pn;

	if( pn & 1 == 1 ) {
	  pn = ( ( pn >>1 ) ^ mask ) | 0x8000;
	} else {
	  pn >>= 1;
	}

0x8000 assumes that it's a 16-bit PN register.  You can adjust this to
anything you want.  The mask is the crucial part.  The length of the
sequence depends on the value you use for the mask and the initial
value of pn.  Eventually the sequence will repeat again.  The number
of iterations before that happens is the PN sequence length.
Obviously you don't want a length that's too low.  Nor do you ever
want a value of 0 in your pn register, or it'll never change.

In most applications (hardware) you actually use the bottom bit of the
pn sequence as your random output.  There shouldn't be any problem,
however, with using, say, the lower 8 bits for your application.
Another method (though somewhat costly in software) is to xor all the
bits in the register together - again this produces a one bit serial
output.

Usually, the bigger the register the longer the sequences - my code
above is for the PC and assumes a 16-bit size.  If the computer you're
going to be running this on will do 32-bit just as easily or almost as
fast you might consider a 32-bit sequence, which should run from here
to eternity.  As to which sequence to use, I'm sure there's some
published, but I don't have any good ones handy.  May I suggest brute
force?  Just chug along until you find one that's sufficiently long
for your needs.  

For a 16-bit PN register, if you use a mask of 0xfff6 and a non-zero
starting value in the register with the above code you get a pn
sequence that runs through every possible value value in the pn
register (except 0)!  I believe there is such a mask for any size
register...  And now you also know an excellent way to do pixel by
pixel "random" fades from one picture to another.

-- 
What passes for woman's intuition is often nothing more than man's transparency