Памяти Соломона Голомба (1932-2016): автора регистра сдвига с линейной обратной связью максимальной длины и полиомино

[ittakir]

А функция random() в языках программирования тоже основана на этих же полиномах?

P.S. Слово «cell» применительно к сотовой связи переводится как «сота», а не «клетка».

[OsipovRoman]

Многие ГПСЧ так или иначе завязаны на регистры сдвига.

[mayorovp]

Но не все. Линейный конгруэнтный (используемый в libc!), к примеру, не завязан.

[Refridgerator]

Стивен где-то упоминал, что в Mathematica для генерации случайных чисел используется клеточный автомат с правилом 30.

[OsipovRoman]

Да, это было до недавнего времени основное правило.

Теперь встроен в систему ГПСЧ «ExtendedCA», использующий более сложный клеточный автомат, дающий более качественные псевдослучайные числа.

Генератор успешно прошел все самые сложные тесты, вроде BigCrush.

[AVI-crak]

Функция random() может использовать физически шумный пороговый элемент, если такой существует в системе. Но сборка выполняется циклическим сдвигом, как в стандартном программном рандоме. При этом операция xor применяется к биту на расстоянии простого числа —
13,17,19,23,29,31,37,41,43,47,53,59,61 — чем дальше бит операции, тем дольше цикл.

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

[lizarge]

Полиомино — писал программулину для решения задачи из 12 фигурок (вроде) в рамках практики после первого курса, помню как отец вырезал все фигурки из бумаги, посидел пару часов и сказал — это не возможно :)
Первая версия проги решала за 15 минут, вторая за 2:) Практику сдал вообщем, использовал самый банальный рекурсивный поиск с возвратом на C++ Builder (тот самый)

[andy_p]

Когда-то занимался этими регистрами сдвига.
Кто интересуется, может скачать с моей странички:

http://andyplekhanov.narod.ru/science/galua.htm

[andreishe]

Есть еще Линейка Голомба.

[Dimchansky]

Будучи энтузиастом, в течение последних нескольких десятилетий я пытался изучить всех предшественников моей работы над jlyjvthysvb клеточными автоматами.

jlyjvthysvb — что это за термин?

[OsipovRoman]

«одномерными». Исправлено.

[Dimchansky]

Я уж думал это аббревиатура такая. :)