8 billion scrambles?

[Stefan]

(Sorry for hijacking the thread, but I think the original issue has its conclusion already)

Yeah, the history of the computational analysis is fascinating to me, too. There are lots of gems both in the old "cube lovers" mailing list and the new forum. Computer analysis as well as more mathematical theory. Reading all the old messages is one of my future goals. In my thesis I did try to cover what I consider the most important milestones that I know about and which fit my topic, but it's certainly not all there is.

 

[blgentry]

Definitely misunderstandings, I should have read the OP more closely to begin with. To my defense, I'm not the only one that misunderstood it, blgentry and I actually discussed it off forum before either of us replied and we both had the same misinterpretation.

What makes this worse for me is that I didn't "get it" until this morning when I was thinking about the problem. Up until then I thought your talk about the seed and the period of various PRNGs was off topic. I now get exactly what Kenneth was trying to say and understand the explanations offered by various posters here.

This is a very subtle and complex problem IMHO. As several others have pointed out, it doesn't have much of a practical impact on us human beings since the space of even a "limited" PRNG is so large.

I'm still interested in techniques that would guarantee the possibility of hitting every state of the cube though. It seems doing random jump-aheads with high period PRNGs would be a good approach, as Brunson said. Off to think about this some more.

Brian.

 

[brunson]

Not yo' mama's PRNG

So, here you go:

class CMWC4096( object ):
    longlong = (1L<<64) - 1
    seedqty = 4096

    def __init__( self, trueentropy=2 ):
        self.count = 0
        self.quantities = ( self.readseeds( trueentropy, '/dev/random' ) +
                            self.readseeds( self.seedqty - trueentropy, '/dev/urandom' ) )
        self.initial = self.readseeds( 1, '/dev/random' ) % 809430660
        self.carry = 18782L
        self.index = self.seedqty - 1
        self.radix = 0xfffffffeL

    def readseeds( self, count, source ):
        import struct
        l = list( struct.unpack( "q"*count, open( source ).read( count*8 ) ) )
        if count == 1:
            return l[0]
        else:
            return l

    def random( self ):
        self.index = (self.index+1) % 4095
        self.t = self.carry * self.quantities[self.index] + self.count
        self.count = (self.t>>32)
        x = self.t + self.count

        if x < self.count:
            x = (x+1) & self.longlong
            self.count = (self.count+1) % self.longlong

        if x + 1 == 0:
            self.count = (self.count+1) % self.longlong
            x = 0

        val = self.quantities[self.index] = self.radix - x
        return abs( val )

    def generate( self ):
        while True:
            yield self.random()


if __name__ == '__main__':
    g = CMWC4096(2)
    print g.random()
    for count, rand in zip( xrange(0,100),  g.generate() ):
        print rand

There you have a python class implementing Complementary Multiply With Carry, a cryptographically secure PRNG with a period of 10^39460. The code is adapted from a C implementation posted by the creator, George Marsaglia, to the comp.lang.c Usenet group in 2003.

The state machine is initialized using and array of 4096 64 bit seeds generated from a combination of inputs from /dev/urandom, a source of cryptographically secure pseudo random numbers available in Linux and many other POSIX operating systems, and /dev/random, a source of very high quality randomness derived from an entropy pool based on environmental inputs. The true random numbers are placed at the beginning of the seed pool, where they are used first. The initial pointer is also generated using true entropy from /dev/random.

This allows for a possibility of (2^64)^4096 * 809430660 (~10^78922) starting points. Random enough for ya? ;-)

I was worried that the performance would be poor being in pure python, but on my 2.2GHz Intel I am able to generate about 114,000 values per second. Using full psyco optimization that number goes up to almost 200,000 v/s.

Anyway, it was a fun discussion and caused me to finish something I've been meaning to complete for about two years.