Re: BitBox PRNG

From: Michael Amling (nospam_at_nospam.com)
Date: 08/30/03 

Date: Sat, 30 Aug 2003 04:33:02 GMT

J. Campbell wrote:
> The BitBox PRNG:
>
> http://home.bellsouth.net/p/s/community.dll?ep=16&ext=1&groupid=142656&ck=
>
> bitbox16.zip
> -bitbox16_show (source & exe) demonstrates a bitbox
> -bitbox16_out (source & exe) outputs 12 MB of data extracted from
> bitbox as "bitbox16.bin" for "randomness" testing
> -bitbox16(diehard results).txt results of diehard test
>
>
> Here's a conceptually simple PRNG that passes all 15 of the "DieHard"
> battery of randomness tests, when seeded with as little as a single
> "1" bit.
>
> The basic idea of the bitbox is that it is a 2-D array of bits. The
> box is then "bounced" and "bumped" to mix the bits. If the box is
> simply "bumped" or "bounced" repeatedly, it will eventually get mixed,
> due to the cyclic boundary conditions, but by mixing in 2 dimensions
> the rate at which each bit influences each other bit increases
> dramatically.
>
> As an example, the 16 x 16 bit bitbox contains 256 bits. If it is
> simply bumped repeatedly, it will require 256 bumps before each bit
> has interacted with each other twice (ie it's "well mixed"). If the
> same bitbox is only bounced, it again will require 256 bounces to get
> well-mixed. However, if bumps and bounces are alternated, it takes
> just 16 bounce/bump cycles (to get the bits well mixed.
>
> Here's how it works. Consider a 4x4 array of bits:
> 0000
> 0000
> 0000
> 0000
>
> each array element may be given a unique label:
> abcd
> efgh
> ijkl
> mnop
>
> now...this array can be presented as:
>
> abcd efgh ijkl mnop -across
> or
> aeim bfjn cgko dhlp -down
>
> the mixing scheme I used is the oft-maligned rule30 1-D automata using
> cyclic boundary conditions.

   Does a rule30 1-D automaton admit of a brief description of its
effect on either abcd efgh ijkl mnop or aeim bfjn cgko dhlp?

--Mike Amling