[short cycle on rule30] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1

short cycle on rule30
(Click here to view the original thread with full colors/images)

Posted by: JoeC

Hi guys. I wanted to discuss the existence of short cycle seeds in bounded rule30 CA. As the system size gets larger, it quickly becomes non-feasable to measure the cycle length. However for sizes 8, 16, and 32, I've found that there exist some low-probability (circa 0.5 to 5%) keys that lead to abnormally short repete length. Wolfram shows the max cycle in his plot, where the max cycle length increases something like 2^(0.75n), where n is the automata bit-width.

Here's what I find:
bitsize___ most comon repete length___other repete lengths
8_____________ 40________________ 8, 1
16___________4144 & 6016__________40, 8
32_________ 842528 _______________2002272, 54984, 4414, 6016

these short cycles have periods on the order of 2^(0.25n), which is *much* shorter than the values indicated in NKS. In the encryption program I demonstrated in the "applied" forum, I use a large enough bit size such that even if a 2^(0.25) short cycle is encountered, it will still represent an enormous cycle length. I was wondering if Wolfram is aware of this issue with using Rule30 as a PRNG??

Another thing of interest...since the repete length appears to involve a small number of discrete values, it leads me to believe that there are only a few diferent cycles that exist...the difference between one particular seed and the next is simply where you "get on" the cycle...

I've included 2 programs with this post that might make my point more clear. The first one simply shows the first few cycles of the rule30 CA. You can change the indicated integer data-type to access the various native word-sizes that are available. The purpose is to simply demonstrate that the code indeed is rule30.

The second program seeds the automata with some data, then measures and outputs the cycle length and and the seed that was used. By running the second program with unsigned char, unsigned short, and unsigned long, you will understand where the numbers I posted above came from...

Sorry the code looks so bad...the forum software strips white-spaces from the code, so that indents are *eliminated*, which makes it difficult to read...

Here's the basic program I used to generate the automata:

code:
// simple show
#include<iostream>

using namespace std;

int main(){
   unsigned long a;          //change type to unsigned char, short, int, long, or long long
   int bits = CHAR_BIT * sizeof(a);
   a = 1 << (bits/2);
   
   for (int i = 0; i < bits/2; ++i){
      for (int j = 0; j < bits; ++j)
         cout << ((a & (1 << j)) >> j);
      cout << endl;    
      a = (((a << 1) | ( a >> (bits - 1))) ^ (a | ((a >> 1) | (a << (bits -1)))));
   }
    cin.get();
    return 0; 
}

And I used the following program to find the repete cycle:

code:
// simple find
#include<iostream>

using namespace std;

int main(){
   unsigned long a, hold, seed;   //change type to unsigned char, short, int, or long
   unsigned int count;
   int bits = CHAR_BIT * sizeof(a);
   while(1){
       seed = rand();
       a = seed;
       for (int i = 0; i < 2 << ((3*bits)/4); ++i)
          a = (((a << 1) | ( a >> (bits - 1))) ^ (a | ((a >> 1) | (a << (bits -1)))));
       hold = a;
       count = 0;
       do{
          a = (((a << 1) | ( a >> (bits - 1))) ^ (a | ((a >> 1) | (a << (bits -1)))));  
          ++count;
       }while (a!=hold);
       cout << "repete @ " << count << " For seed " << seed << endl; 
   }
}

edit: Thanks, Jason. The spacing looks much better with the code tags...if I post code here in the future, I'll be sure to make use of the tags. Cheers. BTW...not trying to flatter, but...reading some of your other posts...you write deliberately and well. SW hires well ;-)

Posted by: Jason Cawley

Better? I just added some "code" tags before and after the code portions of your post. That tells the forum software to leave your indents and such - which makes for a wider field on the screen but keeps the c readable. I hope it helps. If you can move your comments and "or"s down a line, it would keep the right table width too, I'd think.

Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings