Старая идея, но с тех пор я не мог найти какой-то достаточно хороший способ решить возникшую проблему. Поэтому я «изобрел» (см. Ниже) очень компактный и, на мой взгляд, достаточно хорошо работающий PRNG, но я не могу найти алгоритмы для создания подходящих начальных значений для него на больших битовых глубинах. Мое текущее решение - просто перебор, время его выполнения - O (n ^ 3).

Генератор

Моя идея пришла от XOR кранов (по сутиЛРСОС) некоторые старые 8-битные машины, используемые для генерации звука. Я возился с XOR в качестве базы на C64, пытался собрать коды операций и испытал результат. Окончательное рабочее решение выглядело так:

asl
adc #num1
eor #num2

Это 5 байтов на 6502. С правильно выбранными num1 и num2 в аккумуляторе он перебирает все 256 значений в кажущемся случайном порядке, то есть он выглядит достаточно случайным, когда используется для заполнения экрана (я написал немного 256b демо тогда). Для этого есть 40 подходящих пар num1 и num2, каждый из которых дает порядочно выглядящие последовательности.

Понятие может быть хорошо обобщено, если выражено в чистом C, это может выглядеть так (BITS битовая глубина последовательности):

r = (((r >> (BITS-1)) & 1U) + (r << 1) + num1) ^ num2;
r = r & ((1U<<BITS)-1U);

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

Для некоторого анализа производительности и сравнений, см. Ниже, после вопроса (ов).

Проблема / вопрос (ы)

Основная проблема с генератором заключается в поиске подходящих num1 и num2, которые заставили бы его выполнять итерацию по всей возможной последовательности заданной битовой глубины. В конце этого раздела я прилагаю свой код, который просто перебирает его. Он завершится в разумные сроки до 12 бит, вы можете подождать все 16 бит (кстати, для этого есть 5736 возможных пар, полученных с помощью полного ночного поиска некоторое время назад), и вы можете получить несколько 20 бит если вы терпеливы Но O (n ^ 3) действительно противный ...

(Кто найдет первую полную 32-битную последовательность?)

Другие интересные вопросы, которые возникают:

И для num1, и для num2 только нечетные значения могут создавать полные последовательности. Почему? Это может быть не сложно (я полагаю, простая логика), но я никогда не доказывал это разумно.

Существует свойство зеркального отображения вдоль num1 (добавляемое значение), то есть, если 'a' с данным 'b' num2 дает полную последовательность, то дополнение 2 к 'a' (в данной битовой глубине) с тем же num2 также полная последовательность. Я только наблюдал, как это происходит надежно со всеми полными поколениями, которые я рассчитал.

Третье интересное свойство состоит в том, что для всех пар num1 и num2 результирующие последовательности, по-видимому, образуют правильные окружности, то есть, по крайней мере, число ноль всегда является частью окружности. Без этого свойства мой поиск грубой силы умер бы в бесконечном цикле.

Бонус: Был ли этот PRNG уже известен раньше? (а я просто заново его изобрел)?

А вот код поиска грубой силы (C):

#define BITS 16

#include "stdio.h"
#include "stdlib.h"

int main(void)
{
 unsigned int r;
 unsigned int c;
 unsigned int num1;
 unsigned int num2;
 unsigned int mc=0U;

 num1=1U;  /* Only odd add values produce useful results */
 do{
  num2=1U; /* Only odd eor values produce useful results */
  do{
   r= 0U;
   c=~0U;
   do{
    r=(((r>>(BITS-1)) & 1U)+r+r+num1)^num2;
    r&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U); /* 32bit safe */
    c++;
   }while (r);
   if (c>=mc){
    mc=c;
    printf("Count-1: %08X, Num1(adc): %08X, Num2(eor): %08X\n", c, num1, num2);
   }
   num2+=2U;
   num2&=(1U<<(BITS-1)) | ((1U<<(BITS-1))-1U);
  }while(num2!=1U);
  num1+=2U;
  num1&=((1U<<(BITS-1))-1U); /* Do not check complements */
 }while(num1!=1U);

 return 0;
}

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

Охота на семена

Я сделал некоторые графики, касающиеся семян. Вот хорошее изображение, показывающее все длины 9-битной последовательности:

Белые точки - это последовательности полной длины, ось X - для num1 (сложение), ось Y - для num2 (xor), чем ярче точка, тем длиннее последовательность. Другая битовая глубина очень похожа по шаблону: все они, похоже, разбиты на шестнадцать основных плиток с двумя рисунками, повторяющимися с зеркальным отображением. Сходство плиток не является полным, например, если четко видна диагональ от верхнего левого угла до правого нижнего угла, в то время как ее противоположность отсутствует, но для последовательностей полной длины это свойство представляется надежным.

Полагаясь на это, можно сократить работу даже больше, чем в соответствии с предыдущими предположениями, но это все равно O (n ^ 3) ...

Анализ производительности

На данный момент самая длинная последовательность, которую можно сгенерировать, составляет 24 бита: на моем компьютере это занимает около 5 часов, чтобы перебрать полную 24-битную последовательность для этого. Это все еще так себе для реальных тестов PRNG, таких какЖивучи, так что на данный момент я предпочел собственный подход.

Во-первых, важно понять роль генератора. Это ни в коем случае не было бы очень хорошим генератором для его простоты, его цель скорее состоит в том, чтобы быстро производить приличные цифры. В этом регионе не нужны операции умножения / деления,Галуа ЛФСР может производить аналогичную производительность. Так что мой генератор будет полезен, если он способен превзойти этот.

Все мои 16-битные генераторы были выполнены. Я выбрал эту глубину, поскольку она дает полезную длину последовательности, в то время как числа все еще могут быть разбиты на две 8-битные части, что позволяет представлять различные точные графики для визуального анализа.

Суть тестов заключалась в поиске корреляций по предыдущим и сгенерированным в настоящее время числам. Для этого я использовал графики X: Y, где предыдущим поколением был Y, текущий X, оба разбиты на низкие / высокие части, как упомянуто выше для двух графиков. Я создал программу, способную отображать эти ступени в режиме реального времени, чтобы также можно было приблизительно изучить, как числа следуют друг за другом, как заполняются графики. Здесь, очевидно, показаны только конечные результаты, поскольку генераторы прошли свой полный цикл 2 ^ 16 или 2 ^ 16-1 (Галуа).

Объяснение полей:

Изображения состоят из 8x2 256x256 графиков, что дает общий размер изображения 2048x512 (отметьте их в оригинальном размере).

Верхний левый график только подтверждает, что на самом деле была построена полная последовательность, это простоX = r % 256; Y = r / 256; участок.

Нижний левый график показывает каждое второе число, нанесенное таким же образом, как и верхний, просто подтверждая, что числа встречаются достаточно случайно.

На втором графике в верхнем ряду находятся графики старших байтов. Первый из них использует предыдущее поколение, следующий пропускает один номер (поэтому использует 2-е предыдущее поколение) и так далее до 7-го предыдущего поколения.

Со второго нижнего ряда находятся младшие байтовые корреляционные графики, организованные так же, как и выше.

Генератор Галуа, комплект крана 0xB400

Это генератор, найденный вПример Википедии Галуа, Его производительность не самая плохая, но она определенно не очень хорошая.

Генератор Галуа, комплект крана 0xA55A

Один из приличных галуа "семечек" я нашел. Обратите внимание, что младшая часть 16-битных чисел выглядит намного лучше, чем выше, однако я не смог найти никакого «семени» Галуа, которое бы запутало старший байт.

Мой генератор, 0x7F25 (АЦП), 0x00DB (EOR) семян

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

Мой генератор, 0x778B (АЦП), 0x4A8B (EOR) семян

Это один из семян очень хорошего качества по моим меркам.

Чтобы найти семена с хорошей корреляцией, я создал небольшую программу, которая в некоторой степени проанализировала бы их, точно так же, как для Галуа и моей. Примеры «хорошего качества» были точно определены этой программой, а затем я протестировал несколько из них и выбрал один из них.

Некоторые выводы:

Генератор Галуа кажется более жестким, чем мой. На всех графиках корреляции наблюдаются определенные геометрические узоры (некоторые семена дают «шахматные» узоры, не показанные здесь), даже если они не состоят из линий. Мой генератор также показывает шаблоны, но с увеличением количества поколений они становятся менее определенными.

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

Генератору Галуа не хватает нуля (максимальный период равен 2 ^ 16-1).

На данный момент невозможно сгенерировать хороший набор семян для моего генератора выше 20 бит.

Позже я мог бы углубиться в эту тему, пытаясь протестировать генератор с Diehard, но на данный момент отсутствие способности генерировать достаточно большие семена для этого делает невозможным.