Problem Statement

Rule 30 is considered to be chaotic enough to generate good pseudo-random numbers. As a matter of fact, for a long time rule 30 was used by the Mathematica software for its default random number generator. Steven Wolfram's recommendation for random number generation from rule 30 consists in extracting successive bits in a fixed position in the array of cells, as the automaton changes state. The purpose of this task is to demonstrate this. With the code written in the parent task, which you don't need to re-write here, show the ten first bytes that emerge from this recommendation. To be precise, you will start with a state of all cells but one equal to zero, and you'll follow the evolution of the particular cell whose state was initially one. Then you'll regroup those bits by packets of eight, reconstituting bytes with the first bit being the most significant. You can pick which ever length you want for the initial array but it should be visible in the code so that your output can be reproduced with an other language. For extra-credits, you will make this algorithm run as fast as possible in your language, for instance with an extensive use of bitwise logic.

Let's start with the solution:

#include <bitset>
#include <stdio.h>

#define SIZE	           80
#define RULE               30
#define RULE_TEST(x)       (RULE & 1 << (7 & (x)))

void evolve(std::bitset<SIZE> &s) {
    int i;
    std::bitset<SIZE> t(0);
    t[SIZE-1] = RULE_TEST( s[0] << 2 | s[SIZE-1] << 1 | s[SIZE-2] );
    t[     0] = RULE_TEST( s[1] << 2 | s[     0] << 1 | s[SIZE-1] );
    for (i = 1; i < SIZE-1; i++)
	t[i] = RULE_TEST( s[i+1] << 2 | s[i] << 1 | s[i-1] );
    for (i = 0; i < SIZE; i++) s[i] = t[i];
}
void show(std::bitset<SIZE> s) {
    int i;
    for (i = SIZE; i--; ) printf("%c", s[i] ? '#' : ' ');
    printf("|\n");
}
unsigned char byte(std::bitset<SIZE> &s) {
    unsigned char b = 0;
    int i;
    for (i=8; i--; ) {
	b |= s[0] << i; 
	evolve(s);
    }
    return b;
}

int main() {
    int i;
    std::bitset<SIZE> state(1);
    for (i=10; i--; )
	printf("%u%c", byte(state), i ? ' ' : '\n');
    return 0;
}