Cellular Automaton Knitting with Perl

[aisa0]

The finest meta-program in the history of anything:

Cellular Automaton Knitting with Perl.

Thank you, wikipedia.

ADDENDUM:

So that I also have something to contribute, here is rule 30 used as a random number generator, written by yours truly. (Though the idea of doing so certainly isn't mine.) Anyone care to suggest an optimization?



/*
* the number of bytes
* in the seed. must be
* a multiple of 20.
*/
#ifndef SEED
#define SEED 80
#endif

/*
* machine specific, the integer
* size of a pointer. Also known
* as size_t in modern code.
*/
typedef unsigned int uintptr;

static unsigned step();

/*
* populate |buf| using rule 30.
* |seed| is the initial line.
*/
void
rule30_random(seed, buf, size)
char *seed, *buf;
uintptr size;
{
unsigned n;
char tmp[SEED];

while(size--) {
n=step(seed, tmp);
n|=step(tmp, seed)<<1;
n|=step(seed, tmp)<<2;
n|=step(tmp, seed)<<3;
n|=step(seed, tmp)<<4;
n|=step(tmp, seed)<<5;
n|=step(seed, tmp)<<6;
n|=step(tmp, seed)<<7;

*buf++=(char)(unsigned char)n;
}
}

/*
* compute one generation and return
* the middle bit.
*
* the value of each cell in the new
* generation is determined by the
* three surrounding cells in the
* previous generation.
*/
static unsigned
step(old, new)
char *old, *new;
{
static unsigned rule[8U]={0U, 1U, 1U, 1U, 1U, 0U, 0U, 0U};
unsigned n, o, edge, bit[8U];
uintptr i;

edge=(unsigned)(unsigned char)(char)old[(uintptr)SEED-(uintptr)1U];
edge>>=7;

o=(unsigned)(unsigned char)(char)*old++;
bit[0]=o&0x1; o>>=1;
bit[1]=o&0x1; o>>=1;

n=rule[edge<<2|bit[0]<<1|bit[1]];
edge=bit[0];

i=(uintptr)0U;
for(;;) {
bit[2]=o&0x1; o>>=1;
bit[3]=o&0x1; o>>=1;
bit[4]=o&0x1; o>>=1;
bit[5]=o&0x1; o>>=1;
bit[6]=o&0x1; o>>=1;
bit[7]=o&0x1; o>>=1;

n|=rule[bit[0]<<2|bit[1]<<1|bit[2]]<<1;
n|=rule[bit[1]<<2|bit[2]<<1|bit[3]]<<2;
n|=rule[bit[2]<<2|bit[3]<<1|bit[4]]<<3;
n|=rule[bit[3]<<2|bit[4]<<1|bit[5]]<<4;
n|=rule[bit[4]<<2|bit[5]<<1|bit[6]]<<5;
n|=rule[bit[5]<<2|bit[6]<<1|bit[7]]<<6;

if((uintptr)SEED-(uintptr)1U==i++) break;

o=(unsigned)(unsigned char)(char)*old++;
bit[0]=o&0x1; o>>=1;
bit[1]=o&0x1; o>>=1;

n|=rule[bit[6]<<2|bit[7]<<1|bit[0]]<<7;
*new++=(char)(unsigned char)n;

n=rule[bit[7]<<2|bit[0]<<1|bit[1]];
}

n|=rule[bit[(uintptr)6U]<<2|bit[(uintptr)7U]<<1|edge]<<7;
*new++=(char)(unsigned char)n;
return (unsigned)(unsigned char)(char)*(new-(SEED/2U))&0x1;
}

For anyone who was every curious how computers generate random numbers, I will say that this is a slow and very complicated way of doing so; it isn't a good learning tool on the topic.