How to resolve the algorithm Elementary cellular automaton/Random number generator step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Elementary cellular automaton/Random number generator step by step in the C programming language

Table of Contents

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:

Step by Step solution about How to resolve the algorithm Elementary cellular automaton/Random number generator step by step in the C programming language

This C code simulates the evolution of a cellular automaton, specifically Rule 30, using bit manipulation and loops.

Cellular Automaton:

A cellular automaton is a system of cells arranged in a regular grid, each with a state (usually 0 or 1). The state of each cell at the next time step is determined by the states of its neighboring cells according to a specified rule.

Code Explanation:

1. Includes and Definitions:

  • Includes <stdio.h> for input/output functions and <limits.h> for constants like CHAR_BIT.
  • Defines some constants:
    • N: Size of an unsigned long long (64 bits on most systems).
    • B(x): A macro to create a bitmask with the bit at position x set to 1.

2. evolve Function:

  • This function simulates the evolution of a cellular automaton for 10 time steps.

  • It takes two arguments:

    • state: The initial state of the automaton, represented as an unsigned long long.
    • rule: The rule number (30 in this case) that defines how the automaton evolves.
  • Inside the function:

    • It iterates through 10 time steps.
    • For each time step, it iterates through each bit position (0 to 63).
    • For each bit position, it checks if the rule number has a bit set at the corresponding bit pattern (using bit masking and logical operations).
    • If the rule has a bit set, it sets the corresponding bit in the state.
    • It prints the current bit pattern as a decimal number.

3. main Function:

  • Calls the evolve function with an initial state of 1 and Rule 30.

Output:

The code will print the evolution of Rule 30 cellular automaton for 10 time steps. The output will be a sequence of decimal numbers representing the current bit patterns.

For example, for Rule 30:

32 50 69 89 105 123 146 173 204 239

Source code in the c programming language

#include <stdio.h>
#include <limits.h>

typedef unsigned long long ull;
#define N (sizeof(ull) * CHAR_BIT)
#define B(x) (1ULL << (x))

void evolve(ull state, int rule)
{
	int i, p, q, b;

	for (p = 0; p < 10; p++) {
		for (b = 0, q = 8; q--; ) {
			ull st = state;
			b |= (st&1) << q;

			for (state = i = 0; i < N; i++)
				if (rule & B(7 & (st>>(i-1) | st<<(N+1-i))))
					state |= B(i);
		}
		printf(" %d", b);
	}
	putchar('\n');
	return;
}

int main(void)
{
	evolve(1, 30);
	return 0;
}


  

You may also check:How to resolve the algorithm Determine if a string is numeric step by step in the Apex programming language
You may also check:How to resolve the algorithm Integer overflow step by step in the Ksh programming language
You may also check:How to resolve the algorithm Compare length of two strings step by step in the Quackery programming language
You may also check:How to resolve the algorithm Y combinator step by step in the Klingphix programming language
You may also check:How to resolve the algorithm Arithmetic/Integer step by step in the Swift programming language