Вопрос про random для больших чисел

← →
Дмитрий С © (2011-06-09 08:35) [0]

Пригодна ли функция random для генерации равномерно (или как там правильно) распределенных больших случайных чисел. К примеру до 10 миллионов.

← →
oldman © (2011-06-09 08:40) [1]

А в чем сомнения?

← →
TUser © (2011-06-09 08:53) [2]

> Пригодна ли

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

← →
Дмитрий С © (2011-06-09 08:54) [3]

> oldman © (09.06.11 08:40) [1]

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

← →
oldman © (2011-06-09 08:56) [4]

> Дмитрий С © (09.06.11 08:54) [3]

А множитель использовать?

← →
Дмитрий С © (2011-06-09 08:58) [5]

> oldman © (09.06.11 08:56) [4]
> > Дмитрий С © (09.06.11 08:54) [3]
> А множитель использовать?

Это как?

random(32768)*10 ?
или
for i:=0 to 10 do rand := rand + random(32768) ?

← →
Дмитрий Белькевич (2011-06-09 09:13) [6]

> Есть мнение, что эта функция не может нормально генерировать
> случайные числа больше 32768

Можно числа "склеить": 32768 + 32768 * 10000 + 32768 * 10000 * 10000 = 327683276832768.

← →
Дмитрий Белькевич (2011-06-09 09:14) [7]

Хотя, думаю, все это лишнее.

← →
MBo © (2011-06-09 09:18) [8]

>Откуда такое мнение я не помню
Оно неправильное

← →
oldman © (2011-06-09 09:18) [9]

> Дмитрий С © (09.06.11 08:58) [5]
> Это как?

random(30000)*random(30000)
вот тебе и 900000

← →
Дмитрий С © (2011-06-09 09:32) [10]

> Дмитрий Белькевич (09.06.11 09:14) [7]

> oldman © (09.06.11 09:18) [9]

Надо будет еще доказать, что оно равномерно распределенное получилось.

> MBo © (09.06.11 09:18) [8]
> >Откуда такое мнение я не помню
> Оно неправильное

т.е. можно спокойно использовать random(10000000) ?

← →
oldman © (2011-06-09 09:41) [11]

> Дмитрий С © (09.06.11 09:32) [10]
> т.е. можно спокойно использовать random(10000000) ?

А попробовать влом?

← →
Дмитрий С © (2011-06-09 09:44) [12]

> А попробовать влом?

А как вы себе проверку представляете?

← →
И. Павел © (2011-06-09 09:45) [13]

> random(30000)*random(30000)
> вот тебе и 900000

В таком случае значение 29999 * 29999 получится только при одной комбинации (когда оба рандома вернут максимум). А, например, число 1000 может получиться как 10 * 100 или 1 * 1000 или 100 * 10 и т.д. Т.е. деже если распределение рандома - равномерно, то распределение их произведения равномерным не будет.

← →
oldman © (2011-06-09 09:46) [14]

> Дмитрий С © (09.06.11 09:44) [12]

do while true
i:=random(10000000);
if i>35000 then Ура! Работает!!!;
end;

← →
Дмитрий С © (2011-06-09 09:48) [15]

> oldman © (09.06.11 09:46) [14]

так в этом то сомнений нет, вопрос в равномерности полученных случайных значений.

В общем я написал тест, который выдает приемлемые результаты. Видимо мои опасения были напрасными.

program Project3; {$APPTYPE CONSOLE} uses Classes, SysUtils; procedure Test; var I, J, V: Integer; S: String; SL:TStringList; begin Randomize; SL := TStringList.Create; try SL.Duplicates := dupIgnore; SL.CaseSensitive := True; SL.Sorted := True; for I := 1 to maxint do begin V := Random(10000000); if V <= 50 then begin S:= IntToHex(V, 8); if SL.Find(S, J) then SL.Objects[J] := Pointer(Integer(SL.Objects[J])+1) else SL.AddObject(S, nil); end; end; for I := 0 to 50 do if I < SL.Count then Writeln(SL[I], ": ", Integer(SL.Objects[I])); finally SL.Free; end; end; begin try Test; writeln("Complete."); readln; except on E: Exception do Writeln(E.ClassName, ": ", E.Message); end; end.

← →
MBo © (2011-06-09 09:58) [16]

>т.е. можно спокойно использовать random(10000000) ?
Да. Поверье про 32768 происходит либо с 16-разрядных времен, либо от сишников (у которых в системных библиотеках 32-разрядных компиляторов сохранялась функция с 16-разрядным ограничением)

← →
DiamondShark © (2011-06-09 10:19) [17]

> Дмитрий С ©

А вы с какой целью интересуетесь?
Может вам CryptGenRandom подойдёт?

← →
Dimka Maslov © (2011-06-09 11:48) [18]

для лучшего распределения случайных 32-битных чисел можно воспользоваться командой центрального процессора rtdsc и для полученного результа вычислить MD5, потом для всех четырех чисел MD5 сделать общий XOR.

← →
Rouse_ © (2011-06-09 12:13) [19]

CoCreateGuid даст тебе нормальное распределение

← →
Очень злой (2011-06-09 12:36) [20]

> for i:=0 to 10 do rand := rand + random(32768) ?

Так не получится нормальное распределение

← →
Ega23 © (2011-06-09 12:51) [21]

> CoCreateGuid даст тебе нормальное распределение

Равномерное он даст, а не нормальное. А нормальное - это "гауссиан", нафиг он тебе нужен?

← →
И. Павел © (2011-06-09 12:54) [22]

Если все же нужно комбинировать рандомы (для астрономических цифр, например), то для равномерного распределения, наверное, нужно делать как-то так: random(32768) * 32768 + random(32768). Т.е. чтобы области влияния рандомов не пересекались.

← →
Mystic © (2011-06-09 13:15) [23]

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

← →
Rouse_ © (2011-06-09 13:43) [24]

> Ega23 © (09.06.11 12:51) [21]
> Равномерное он даст, а не нормальное.

Еслиб я писал про распределение Гаусса, то слово нормальное заключил бы в кавычки :)

← →
MonoLife © (2011-06-09 14:07) [25]

еще randomrange() попробовать..

← →
Jeer © (2011-06-09 14:41) [26]

> Дмитрий С © (09.06.11 09:48) [15]
>
> В общем я написал тест, который выдает приемлемые результаты.
>

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

← →
Дмитрий Белькевич (2011-06-09 19:23) [27]

> Если все же нужно комбинировать рандомы (для астрономических
> цифр, например), то для равномерного распределения, наверное,
> нужно делать как-то так: random(32768) * 32768 + random(32768).
> Т.е. чтобы области влияния рандомов не пересекались.

Точнее - да - множить на максимум диапазона, а не на 10000. Доказать? Математически - не возьмусь. На пальцах - думается, что если каждый бит полученного числа будет равномерно случайно распределен, то и всё число вместе будет равномерно распределено. Ну а так как число-результат составлено из нескольких кусков-наборов равномерно распределенных бит, то и всё оно будет равномерно распределено. Как-то так.

Но - без разницы - рандом и так нормально должен отдавать результат. Насколько я помню алгоритмом - то генерится именно последовательность псевдослучайных бит. А как их уже упаковать - по 8, по 16 или по 32, внутри алгоритма, или снаружи - думаю, без разницы.

> Насколько я помню алгоритмом - то генерится именно последовательность
> псевдослучайных бит.

Это и есть главная и пока недостижимая задача.

> MBo © (09.06.11 09:58) [16]

Спасибо за разъяснение, большое спасибо :)

> Может вам CryptGenRandom подойдёт?

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

> CoCreateGuid даст тебе нормальное распределение

нормальное? в смысле равномерное?

> Dimka Maslov © (09.06.11 11:48) [18]
>
> для лучшего распределения случайных 32-битных чисел можно
> воспользоваться командой центрального процессора rtdsc и
> для полученного результа вычислить MD5, потом для всех четырех
> чисел MD5 сделать общий XOR.

Доказать, что в результате получим равномерное распределение - unreal :(

> И. Павел © (09.06.11 12:54) [22]
>
> Если все же нужно комбинировать рандомы (для астрономических
> цифр, например), то для равномерного распределения, наверное,
> нужно делать как-то так: random(32768) * 32768 + random(32768).
> Т.е. чтобы области влияния рандомов не пересекались.

Тут надо еще доказать, что если мы будем брать не каждый random, а через один - то получим равномерное распределение.

> еще randomrange() попробовать..
>

функция основана на обычном random

> Дмитрий С © (09.06.11 08:54) [3]
> Есть мнение...

Последовательность значений каждого отдельного бита Random - циклическая.
Чем старше бит, тем длиннее цикл.

>>нужно делать как-то так: random(32768) * 32768 + random(32768).

> Тут надо еще доказать, что если мы будем брать не каждый
> random, а через один - то получим равномерное распределение.

Откуда там равномерное распределение? Очевидно, что некоторые значения мы просто никогда не сумеем получить при том генераторе псевдослучайных чисел, что находится в Delphi. Если предположить, что seed у нас 16 бит, то первое значение однозначно определяет все последующие.

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

> Надо просто построить кривую распределения

С этого и надо начинать, а не на форуме тему открывать.
А дальше уже решать, подойдет ли Random или свой генератор городить.

> А дальше уже решать, подойдет ли Random или свой генератор
> городить.

На принятие решения может уйти много времени. Было время когда у меня в машине крутился один сидюшник с мп3, постоянно включенный на проигрывание случайного трека. Долго крутился. Но вдруг я стал замечать, что когда машина начинала требовать дозаправки играла одна и та же песня. А поскольку я практически всегда езжу одним маршрутом и заправляюсь через почти одинаковые промежутки времени, можно сделать вывод, что генератор случайных чисел в аудиосистеме просто и естественно привязан к таймеру. Или например одна радиостанция в время обеда (а он у нас ровно в 13.00 центральнороссийского времени) упорно передает Алуэтту (она же - "в мире животных") тоже, значит функция рандом у них в компе циклится.

> Dimka Maslov © (10.06.11 13:31) [33]
> Надо просто построить кривую распределения

> SergeyIT © (10.06.11 15:06) [34]
> С этого и надо начинать, а не на форуме тему открывать.
> А дальше уже решать, подойдет ли Random или свой генератор
> городить.

Вы оба предлагаете визуализировать кривую распределения и на основе визуальной субъективной человеческой оценки решать вопрос о принадлежности распределения к тому или иному классу ?

> Вы оба предлагаете визуализировать кривую распределения

А просчитать разве нельзя, так сказать, математически? На достаточно большой выборке.

> Вы оба предлагаете визуализировать кривую распределения
> и на основе визуальной субъективной человеческой оценки
> решать вопрос о принадлежности распределения к тому или
> иному классу

Имея кривую распределения можно описать его математической формулой, и если оно окажется y = const, мы имеем дело с равномерным распределением. Помнится ещё в прошлом веке, будучи студентом паровозной школы, я такое делал в рамках курса "высшая математика"

> Dimka Maslov © (10.06.11 18:42) [38]

Так я в своем примере так и сделал, только брал не все числа, а первые 50 - для скорости, да и на всех памяти не хватит. Получил примерно одинаковые значения - меня устраивает. +100 к уверенности добавил МВо :)

Вопрос про random для больших чисел Найти похожие ветки