Генерация случайных чисел

[Alhimik]

Всеп прива!!! Кто нибудь знает как происходит генерация случайных чисел в Delphi? Я имею в виду физические процессы, происходящие при выполнении
...
randomize;
for i:=0 to N-1 do x[i]:= RandG (10, 5); // x : array [0..N-1] of real;
...?

Язык программирования: Delphi.
Одни говорят, что есть какой-то линейный генератор псевдослучайных чисел, другие - что таблица случайных чисел может храниться на компе со старту... Что в действительности происходит при выполнении этих строк?

[Chifu]

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

[venco]

Alhimik в сообщении #292087 писал(а):

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

99,(9)% - генератор псевдослучайных чисел, не обязательно линейный.

[GAA]

В Delphi, как и в TP, последовательность псевдослучайных чисел генерируется линейным конгруэнтным методом.
Исходный текст содержится в файле system.pas (искать в каталоге \source\RTL\sys). Delphi 5:

procedure       _RandInt;
asm
{     ->EAX     Range   }
{     <-EAX     Result  }
        IMUL    EDX, RandSeed, 08088405H
        INC     EDX
        MOV     RandSeed,EDX
        MUL     EDX
        MOV     EAX,EDX
end;

[Alhimik]

Да уж, попахивает, я бы даже сказал несёт, асемблером. Никогда его не любил. И всё же, где берётся исходная последовательность? Я так подозреваю, что должны происходить измерения какой-то физической величины, которая к тому же является случайной и распределенной по известному закону (нормальному или равномерному, например). Что в таком случае измеряется?

[venco]

Alhimik в сообщении #292275 писал(а):

Да уж, попахивает, я бы даже сказал несёт, асемблером. Никогда его не любил. И всё же, где берётся исходная последовательность? Я так подозреваю, что должны происходить измерения какой-то физической величины, которая к тому же является случайной и распределенной по известному закону (нормальному или равномерному, например). Что в таком случае измеряется?

Ничего не измеряется. Речь идёт о псевдослучайной последовательности. Такие последовательности на самом деле не случайные, а только выглядят такими.

[Alhimik]

И от куда они берутся? Можете коротко описать работу асембреровского кода, приведенного GAA. В смысле на русском языке.

[Chifu]

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

[Xey]

Chifu в сообщении #292437 писал(а):

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

А почему график "случайных" блужданий точки повторяется при запуске программки?

[Chifu]

Xey писал(а):

А почему график "случайных" блужданий точки повторяется при запуске программки?

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

[Xey]

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

[Xaositect]

Обычно есть две функции для использования генератора псевдослучайных чисел.
Первая - устанавливает состояние генератора (seed).
Вторая - выдает собственно случайное число, на основе определенного алгоритма.

Часто для установки seed'а используют текущее время (randomize в delphi вроде именно это и делает).

-- Пт фев 26, 2010 14:03:35 --

Alhimik в сообщении #292426 писал(а):

И от куда они берутся? Можете коротко описать работу асембреровского кода, приведенного GAA. В смысле на русском языке.

seed генератора на каждом шаге изменяется линейно со специально подобранными коэффициентами ($\mathtt{seed \leftarrow 0x08088405\cdot seed + 1}$) и обрезается, чтобы влезло в регистр, а затем на его основе генерируется число в диапазоне от 0 до range: $\mathtt{range}\cdot\frac{\mathtt{seed}}{2^{32}}$.

[Alhimik]

Прикольно. Дёшево и сердито.

[Yuri Gendelman]

Вся теория достаточно просто и понятно описана во 2-м томе Кнута.
Линейный конгруэнтный метод объясняется подробно, в т.ч. подбор коэффициентов, оценка качества генератора, распространенные ошибки, широко распространенные (на время написания книги) плохие генераторы ПСЧ.
Главный вывод: для генерации случайных чисел нельзя пользоваться случайным алгоритмом.