Генератор псевдослучайных чисел из правила 30

В одной из статей нашего блога мы уже рассказывали про одномерные клеточные автоматы автоматы, а также показали их простую реализацию. В процессе подготовки материала у нас были некоторые идеи относительно их применения. Одной из них была мысль об использовании правил автоматов в качестве генераторов псевдослучайных чисел. В этой статье мы вам покажем прототип нашего простейшего генератора псевдослучайных чисел на базе правила 30.

Генератор псевдослучайных чисел, мы реализовали на базе того же кода, что был приведен ранее в статье про клеточные автоматы, однако вместо массива нулей и единиц, мы взяли просто беззнаковое число с типом ulong. Такое решение позволяет реализовать генерацию 64-битных чисел, что позволит использовать такой генератор в некриптографических приложениях. Сразу оговорим тот момент, что данный вид генераторов не является надежным (хотя используется в некоторых математических пакетах, таких к примеру, как Mathematica) и не удовлетворяет некоторым статистическим тестам.

Поскольку в качестве хранилища состояния клеточного автомата у нас используется только одно число, то для чтения/записи его отдельных элементов использованы стандартные операции над битами: установка (s_nth), сброс (g_nth) и чтение битов (c_nth). Этот функционал реализован через приватные методы класса клеточного автомата, как и метод получения следующего состояния автомата (метод с наименованием stof).

Также, из-за использования 64-битного числа цикл который проходил по всем «клеткам» автомата, а также определение следующей и предыдущей клетки, были изменены с адаптацией к новым условиям: конец цикла уже известен (верхняя граница всегда 64), предыдущая и конечная клетка вычисляются с условием той же верхней границы. Все остальное почти не претерпело никаких изменений, за исключением того, что у класса теперь два публичных метода для чтения и установки внутреннего состояния — set и get, а конструктор теперь имеет необязательный параметр — начальное состояние автомата.

С учетом всего сказанного, код «клеточного» генератора случайных чисел выглядит так:

class Karand
{
	private {
		enum ulong CA = 30;
		ulong _prev, _next;

		ulong g_nth(ulong x, ulong n)
		{
			return (x >> (64 - n)) & 0x01;
		}

		ulong s_nth(ulong x, ulong n)
		{
			return  (0x01 << (64 - n)) | x;
		}

		ulong c_nth(ulong x, ulong n)
		{
			return (x & ~(0x01 << (64 - n)));
		}

		ulong stof(byte left, byte i, byte right)
		{
			return (g_nth(_prev, left) << 2) + (g_nth(_prev, i) << 1) + g_nth(_prev, right);
		}
	}

	void run()
	{
		_prev = _next;
		
		for (byte i = 0; i < 64; i++)
		{
			byte x0     = cast(byte) (i - 1);
			byte x1     = cast(byte) (i + 1);
			byte left   = (x0 <= 0) ? 63 : x0;
			byte right  = (x1 >= 63) ? 0 : x1;
			
			auto _s  = stof(left, i, right);
			auto _w  = (CA & (0x01 << _s)) >> _s;
			
			_next = _w ? s_nth(_next, i) : c_nth(_next, i);
		}
	}

	public {
		this(ulong next = 0x01UL)
		{
			this._next = next;
		}

		ulong get()
		{
			return _next;
		}

		void set(ulong next)
		{
			_next = next;
		}

		alias get this;
	}
}

Испытание можно провести просто сделав вывод состояния автомата на каждом шаге в виде нулей и единиц (бинарная репрезентация 64-битного числа):

import std.stdio;

void main()
{
	import std.format;

	Karand karand = new Karand(1UL << 32 | 1 << 30);
	
	foreach (i; 0..32)
	{
		auto repr = format(`%0.64b`, karand.get);
			
		repr.writeln;

		karand.run;
	}

}

Генератор является довольно примитивным и он не лишен недостатков: в частности мы не придумали как победить его главный недостаток — выдачу серий из значений левые части которых заполнены чисто единицами. Также насколько нам известно, такой генератор не проходит ряд тестов по статистическим критериям, но несмотря на это является достаточно надежным (если не применять подобное в криптографии) и довольно минималистичным.

Однако, мы подчеркнем, что тема клеточных автоматов в генерации разных последовательностей с интересными свойствами, является довольноо интересной и перспективной, поэтому будем благодарны тем, кто решит этим заняться и расскажет нам об этом…