2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Генерация случайных чисел
Сообщение25.02.2010, 14:52 
Аватара пользователя
Скорее всего один из алгоритмов генератора псевдослучайных чисел инициируемый Randomize от датчика времени, а как в самом деле надо спрашивать у разработчиков компилятора.

 
 
 
 Re: Генерация случайных чисел
Сообщение25.02.2010, 15:40 
Alhimik в сообщении #292087 писал(а):
Одни говорят, что есть какой-то линейный генератор псевдослучайных чисел, другие - что таблица случайных чисел может храниться на компе со старту...
99,(9)% - генератор псевдослучайных чисел, не обязательно линейный.

 
 
 
 Re: Генерация случайных чисел
Сообщение25.02.2010, 16:00 
В 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;

 
 
 
 Re: Генерация случайных чисел
Сообщение25.02.2010, 20:49 
Аватара пользователя
Да уж, попахивает, я бы даже сказал несёт, асемблером. Никогда его не любил. И всё же, где берётся исходная последовательность? Я так подозреваю, что должны происходить измерения какой-то физической величины, которая к тому же является случайной и распределенной по известному закону (нормальному или равномерному, например). Что в таком случае измеряется?

 
 
 
 Re: Генерация случайных чисел
Сообщение25.02.2010, 21:10 
Alhimik в сообщении #292275 писал(а):
Да уж, попахивает, я бы даже сказал несёт, асемблером. Никогда его не любил. И всё же, где берётся исходная последовательность? Я так подозреваю, что должны происходить измерения какой-то физической величины, которая к тому же является случайной и распределенной по известному закону (нормальному или равномерному, например). Что в таком случае измеряется?
Ничего не измеряется. Речь идёт о псевдослучайной последовательности. Такие последовательности на самом деле не случайные, а только выглядят такими.

 
 
 
 Re: Генерация случайных чисел
Сообщение26.02.2010, 08:49 
Аватара пользователя
И от куда они берутся? Можете коротко описать работу асембреровского кода, приведенного GAA. В смысле на русском языке.

 
 
 
 Re: Генерация случайных чисел
Сообщение26.02.2010, 09:42 
Аватара пользователя
На некорых мавэбоард есть физический датчик дробового шума электронов для криптопрограмм от производителей, умеют ли сторонние программы юзать эти датчики понятия не имею. В программировании обычно используется простой алгоритм генерации псевдослучайной последовательности, т.е. последовательности с очень большим периодом и ненормированными характеристиками. Распределения и вероятное отсутствие корреляции дают более сложные программы.

 
 
 
 Re: Генерация случайных чисел
Сообщение26.02.2010, 11:20 
Chifu в сообщении #292437 писал(а):
На некорых мавэбоард есть физический датчик дробового шума электронов для криптопрограмм от производителей, .


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

 
 
 
 Re: Генерация случайных чисел
Сообщение26.02.2010, 11:24 
Аватара пользователя
Xey писал(а):
А почему график "случайных" блужданий точки повторяется при запуске программки?
Потому что используемый алгоритм генерации псевдослучайной последовательности детерминирован и с одной и той же инициализацией повторят одну и ту же последовательность. А как используется этот датчик случайных чисел в криптопрограммах я понятия не имею, хотя может там и не дробовый шум электронов, просто это один из физических методов получения случайных чисел.

 
 
 
 Re: Генерация случайных чисел
Сообщение26.02.2010, 11:52 
Я считал, что при отладке , до компиляции, последовательность одна и та же (так удобнее), а после компиляции должны быть разные последовательности.
Но, почему то рисует одну и ту же кривую.

 
 
 
 Re: Генерация случайных чисел
Сообщение26.02.2010, 13:42 
Аватара пользователя
Обычно есть две функции для использования генератора псевдослучайных чисел.
Первая - устанавливает состояние генератора (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}}$.

 
 
 
 Re: Генерация случайных чисел
Сообщение26.02.2010, 15:22 
Аватара пользователя
Прикольно. Дёшево и сердито.

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

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group