ГСЧ и Псевдо-ГСЧ: что плохо.

Автор Starling, 03 июля 2009 г., 19:04:13

« назад - далее »

Starling

Вкратце (или полно, уж как получится) надо реинкарнировать старые темы.

Значится, есть ГСЧ (Генераторы случайных чисел).
И есть генераторы псевдо-случайных чисел.

Применительно к компьютерам и прчоей электронике, технически, ГСЧ - это отдельыне блоки.

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

Все программные "генераторы случайных чисел" - есть генераторы "псевдо-случайных чисел".

И об этом совершенно открыто написано в документации по функциям RND, RAND и тому подобным.

Поэтмоу, привызываемся мы к текущему времени, или нет - программно у нас генератора случайных чисел - быть не может.
А только псевдо-случайных.

Для генерации истинно случайных чисел требуется ввод информации со стороны.
Эту роль и выполняют специальыне модули.

А анализировтаь же ряды, полученыне с ГПСЧ - ну какой тут смысл...

---------------
чем плохи и чем характеризуются "псевдо":

1) у них может быть сколь угодно длинная серия (миллион случайных чисел подряд!), норано или поздно она закончится и... повторит саму себя.
и снова.
и снова....
хотя из-за того, что она такая длинная - ее трудно отличить от истинно случайной.
И для получения случайного числа для генерации хеша, например - она вполне годится.
(ну.. _почти_ годится : ))))

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

Ну не толкьо корень. Еще много чего делаем.
Но в любом случае это - ФОРМУЛА.
Потмоу что компьютер не может иначе. Как ему еще-то поулчить "случайное число" ????

3) есть "табличные варианты".
Тое тсь в программу зашит длинный ряд случайных чисел, который или выдается в чистом виде, или участвует в формуле.
Ну и шо... лучше от этого не становится.

4) псевдо-ГСЧ не подвержен внешним воздействиям (игрек-фактору) и для нас бесполезен.

5) этот ряд не может менять свою энтропию.
Он не может бытьс лучайным - или не случайным.
Он заранее определен, так как это - псевдо-случайный ряд.

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

А вот программу АНАЛИЗА рядов - написать очень даже можно.
Не путайте эти понятия: анализ ряда случайных числел, и собственно их генерация.

(сгенерирвоать что случайный ряд, что белый шум и т.д. - на практике, это вообще задача нетривиальная.)
Все в сад! - Скажите, а мы там будем петь?? - Вы там будете учить матчасть!!

Сергей Александров

Цитата: Starling от 03 июля 2009 г., 19:04:13
4) псевдо-ГСЧ не подвержен внешним воздействиям (игрек-фактору) и для нас бесполезен.

5) этот ряд не может менять свою энтропию.
Он не может бытьс лучайным - или не случайным.
Он заранее определен, так как это - псевдо-случайный ряд.
Почему?
Если КАКИЕ-ТО процессы (ну, нехай будет изменение энтропии...) влияют на работу аппаратного ГСЧ, почему они не могут повлиять на работу аппарата, реализующего программный ГПСЧ?
С.В. Александров
руководитель исследовательского отдела ОНИОО "Космопоиск".

Starling

Потому что истинный ГСЧ, ну, попросту говоря, сам не знает, какая у него будет следующая цифра.
И генерирует ее каждый раз заново.
Он высокоэнтропиен.

А псевдо - гсч - это хоть и сложная, но строгая формула.
В зависимости от значений А Б В Г получаем и Д.

И при одних и тех же начальных условиях - этот ряд можно повторить точь в точь.

Более лучше Псевдо-ГСЧ, как я и написал выше - устроены проще. У них забита таблиза заранее сгенерированных чисел.

Они чисто случайны... до тех пор, пока таблица не кончится, и не пойдет по второму кругу. Грубо говоря.

И конечно, последовательность этих чисел неизменна - просто считывается слездующая ячейка из заранее заготовленнйо таблицы.
Грубо говоря.
Все в сад! - Скажите, а мы там будем петь?? - Вы там будете учить матчасть!!

Starling

А вернее, можно сказать так:
может быть (подчеркиваю - может быть) на какие-то типа псевдо-гсч они и влияют.
А на какие-то - точно нет.

Выяснять это... чрезвычайно сложно.
И все-равно не будет уверенности до конца, так как алгоритмы псевдо-гсч меняются и т.д.
Все в сад! - Скажите, а мы там будем петь?? - Вы там будете учить матчасть!!

Дядя Миша

>Они чисто случайны...
К сожалению не совсем. Генераторы бывают разного качества. Чисто случайный процесс,
это когда корреляционная функция выборки  - чисто дельта-функция - палочка при нулевом временном интервале между значениями последовательности, при остальных значениях интервалов - функция равна нулю.
Идеальных алгоритмов-генераторов  не существует.

Может ли влиять аномальный физический процесс на псевдо-случайный генератор?
Ну если этот процесс может влиять так сильно на полупроводник кристалла процессора и оперативной памяти, что в ячейках памяти и арифметико-логических устройствах будут нули заменяться на единицы и наоборот.
Быть может (уж если человек в возмущенном состоянии может влиять на работу техники, в том числе и вычислительной). Тогда быть может в реккуретном алгоритме генератора изменится предыдущее значение,
следовательно будет другим и вычисленное последующее.
Но влюбом случае псевдо-случайный генератор не годится (анализ его статистических характеристик не даст желаемых результатов), в отличие от чувствительного ГСЧ.  

Starling

Мнда. но опять-таки: степень влияния.
Чтобы изменить значение в ячейке памяти - нужно приложить достаточно большую энергию ко многим процессам.
Чтобы получить статистически накопленные суммарные слабые изменения - значительно меньше.
Значит, это будет и точнее, и более слабые колебания можно фиксировать.
Все в сад! - Скажите, а мы там будем петь?? - Вы там будете учить матчасть!!

Uncle Mike

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

Петербург-Космопоиск