Набор Алгоритмов
В статье приведены разные алгоритмы генерации случайных (псевдослучайных) чисел с примерами на языке программирования C#. В статье рассмотрены наиболее известные алгоритмы генерации случайных чисел.
Алгоритмы - Генерация случайных чисел
1. Введение
В статье далее рассмотрены три алгоритма для генерации псевдослучайных чисел. Представлено два метода, основанные на математических и побитовых операциях: Метод генерации случайных чисел вычислением (Computational Methods) и Метод получения случайных чисел побитовыми операциями (XorShift). Последний третий алгорим показывает, как сгенирировать случайное число, если у Вас есть источник случайных байт (Виртуальный генератор (модель получения случайного байта) (System.Random)).
Все примеры/описания алгоритмов демонстрируются на генерации псевдослучайного числа типа long (64-битное целое). Метод для генерации настоящего числа называется protected override long Next().
Рассмотрим далее примеры реализации этого метода для всех трёх алгоритмов и дадим им объснение.
2. Алгоритмы генерации случайных чисел
2.1. Метод генерации случайных чисел вычислением (Computational Methods)
Алгоритм получения псевдослучайного числа с помощью вычислительных методов:
private long _a = 23456781;
private long _b = 12323456781;
private long _mod = 56472311456;
protected long _seed = 5123;
protected override long Next()
{
_seed = (_a * _seed + _b) % _mod;
return _seed;
}
Алгоритм 1. Метод генерации случайных чисел вычислением (Computational Methods).
Как видно из формулы _seed = (_a * _seed + _b) % _mod максимальное число не превышает _mod-1. Адаптируйте классы далее, чтобы генерировалось случайное число long с учётом этого факта, к примеру, генерируя его побайтово.
Для переменных _a, _b, _mod, _seed установлено ограничение, что 0 < _mod, 0 < _a < _mod, 0 < _b < _mod, _seed < _mod (заимствовано из https://ru.wikipedia.org/wiki/Генератор_псевдослучайных_чисел).
Дадим анимацию внутреннему состоянию переменных при генерации 10 псевдослучайных чисел:
Анимация 1. 10 проходов по методу генерации случайных чисел вычислением (Computational Methods).
2.2. Метод получения случайных чисел побитовыми операциями (XorShift)
Алгоитм получения псевдослучайного числа на основе побитовых операций:
private ulong _x = 123; // начальные значения могут быть другими
private ulong _y = 456;
private ulong _z = 789;
private ulong _w = 768;
protected long _seed = (long)_w;
protected override long Next()
{
ulong t = _x ^ (_x << 11);
_x = _y;
_y = _z;
_z = _w;
_w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8));
_seed = (long)_w;
return _seed;
}
Алгоритм 2. Метод получения случайных чисел побитовыми операциями (XorShift).
Данный алгоритм реализован на побитовых сдвигах и побитовом исключающем "или".
Дадим анимацию внутреннему состоянию переменных при генерации 10 псевдослучайных чисел:
Анимация 2. 10 проходов по методу получения случайных чисел побитовыми операциями (XorShift).
2.3. Виртуальный генератор (модель получения случайного байта) (System.Random)
Алгоитм получения псевдослучайного числа с помощью получения байт из случайного источника. Можно брать за алгоритм случайный доступ к оперативной памяти, но это не поддерживает C#, в алгоритме далее функция получения случайных байт заменена на получение псевдослучайных байт с помощью класса C# System.Random:
protected long _seed = 5123;
System.Random random = new System.Random(_seed);
protected override long Next()
{
byte[] rnd = new byte[sizeof(long)];
random.NextBytes(rnd);
long result = 0;
for(int i = sizeof(long) - 1; i >= 0; i--)
{
byte rndByte = rnd[i];
result = result ^ rndByte;
result <<= i * 8;
}
_seed = result;
return _seed;
}
Алгоритм 3. Виртуальный генератор (модель получения случайного байта)(System.Random).
Алгоритм основан на том, что случайный байт как-то можно получить.
3. Исходный код
Исходный код этих генераторов доступен на GitHub.com. Код псевдослучайных генераторов представлен далее и дополнен описанием того, что в нём представлено ранее.
3.1. Метод генерации случайных чисел вычислением (Computational Methods)
Исходный код для Метода генерации случайных чисел вычислением (Computational Methods):
namespace Blog_Random.Random
{
public class RandomComputationalMethods : Random
{
private long _a = 23456781;
private long _b = 12323456781;
private long _mod = 56472311456;
public RandomComputationalMethods(long seed)
{
_seed = seed;
}
protected override long Next()
{
_seed = (_a * _seed + _b) % _mod;
return _seed;
}
}
}
Исходный файл "RandomComputationalMethods.cs".
3.2. Метод получения случайных чисел побитовыми операциями (XorShift)
Исходный код для Метода получения случайных чисел побитовыми операциями (XorShift):
namespace Blog_Random.Random
{
public class RandomXorShift : Random
{
private ulong _x = 123; // начальные значения могут быть другими
private ulong _y = 456;
private ulong _z = 789;
private ulong _w = 768;
public RandomXorShift(ulong x, ulong y, ulong z, ulong w)
{
_x = x;
_y = y;
_z = z;
_w = w;
_seed = (long)_w;
}
public RandomXorShift() { _seed = (long)_w; }
protected override long Next()
{
ulong t = _x ^ (_x << 11);
_x = _y;
_y = _z;
_z = _w;
_w = (_w ^ (_w >> 19)) ^ (t ^ (t >> 8));
_seed = (long)_w;
return _seed;
}
}
}
Исходный файл "RandomXorShift.cs".
3.3. Виртуальный генератор (модель получения случайного байта) (System.Random)
Исходный код для Виртуального генератора (модели получения случайного байта)(System.Random):
namespace Blog_Random.Random
{
public class RandomFromSystem : Random
{
System.Random random;
public RandomFromSystem() { random = new System.Random(); _seed = Next(); }
public RandomFromSystem(int seed) { random = new System.Random(seed); _seed = Next(); }
protected override long Next()
{
byte[] rnd = new byte[sizeof(long)];
random.NextBytes(rnd);
long result = 0;
for(int i = sizeof(long) - 1; i >= 0; i--)
{
byte rndByte = rnd[i];
result = result ^ rndByte;
result <<= i * 8;
}
_seed = result;
return _seed;
}
}
}
Исходный файл "RandomFromSystem.cs".
3.4. Общие методы для всех генераторов
В данном разделе представлен абстакный класс, который является вспомогательным, если Вам нужен не только случайное число long, но и другие типы данных. Для его работы достаточно создать метод Next() в классе потомке, как в примерах исходного кода ранее.
Далее приведён класс, который реализует базовые необходимые методы для частовстречаемой генерации псевдослучайности.
using System;
namespace Blog_Random.Random
{
public abstract class Random
{
protected long _seed;
private byte _currentBytePosition = 8;
protected abstract long Next();
public long RandomLong() => Next();
public byte RandomByte()
{
if (_currentBytePosition == 8)
{
Next();
_currentBytePosition = 0;
}
byte randomByte = (byte)((_seed >> _currentBytePosition) & 0xFF);
_currentBytePosition++;
return randomByte;
}
public double RandomDouble()
{
return BitConverter.ToDouble(new byte[8] { RandomByte(), RandomByte(), RandomByte(), RandomByte(), RandomByte(), RandomByte(), RandomByte(), RandomByte() });
}
public double RandomDoubleBetweenOne()
{
return BitConverter.ToDouble(new byte[8] { RandomByte(), RandomByte(), RandomByte(), RandomByte(), RandomByte(), RandomByte(), (byte)(RandomByte() & 0b0001_1111), 0 }) / RandomDoubleBitOne();
}
private double RandomDoubleBitOne()
{
return BitConverter.ToDouble(new byte[8] { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0b0001_1111, 0 });
}
public long RandomLongBetweenInt(int min, int max)
{
return min + (long) Math.Round(((long)max - (long)min) * RandomDoubleBetweenOne(), 0);
}
}
}
Исходный файл "Random.cs".
Краткое описание членов класса:
- protected long _seed — "зерно" псевдослучайной последовательности.
- private byte _currentBytePosition — текущая позиция для генерации/получения случайного байта в "зерне".
- protected abstract long Next() — Абстактный метод для определения его потомками. Он предназначен для получения следующего псевдослучайного числа из последовательности.
- public long RandomLong() — Метод для получения псевдослучайного числа типа long.
- public byte RandomByte() — Метод для получения псевдослучайного числа типа byte.
- public double RandomDouble() — Метод для получения псевдослучайного числа типа double.
- public double RandomDoubleBetweenOne() — Метод для получения псевдослучайного числа типа double от нуля до единицы включительно.
- private double RandomDoubleBitOne() — Вспомогательный метод для метода RandomDoubleBetweenOne(), для приведения типа double к значениям от нуля до единицы.
- public long RandomLongBetweenInt(int min, int max) — Метод для получения псевдослучайного числа типа long из заданного диапазона типом данных int.
4. Заключение
Главное не копируйте приведенные здесь примеры в свой код, подберите свои коэффициенты алгоритмам, протестируйте их и переделайте. Приведённые в статье примеры даны для объяснения концепции генерации псевдослучайных чисел. Приведённая в статье реализация не является криптостойкой, она рассмотрена для того, чтобы Вы смогли получить свою реализацию GitHub.com или пользоваться готовыми генераторами случайных числел языка программирования.
Вы можете смело пользоваться генераторами псевдослучайных чисел, которые встроены в Ваш язык программирования. Данные алгоритмы помогут Вам, если вы пишите свои типы данных, в которых не возможно пользовать генерацией случайных чисел встроенных в язык программирования или это не удобно.
Если у Вас есть время или нечем занятся, то Вы можете поисследовать эти алгоритмы, проделать их руками, пройтись отладкой, написать тесты и визуализацию.
Также Вы можете придумать свои алгоритмы для генерации псевдослучайных значение, основанные на переполнении разрядной сетки, математических операциях, побитовых операциях, комбинаторикой переменных и т.д.