Форум: "Прочее";
Текущий архив: 2011.10.02;
Скачать: [xml.tar.bz2];
ВнизВопрос про 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, внутри алгоритма, или снаружи - думаю, без разницы.
← →
Jeer © (2011-06-09 22:44) [28]
> Насколько я помню алгоритмом - то генерится именно последовательность
> псевдослучайных бит.
Это и есть главная и пока недостижимая задача.
← →
Дмитрий С © (2011-06-10 05:47) [29]
> MBo © (09.06.11 09:58) [16]
Спасибо за разъяснение, большое спасибо :)
> Может вам CryptGenRandom подойдёт?
Как тут в теме пишут - мне нужно не для криптографии, а для игрульки, поэтому сильная случайность не требуется.
> CoCreateGuid даст тебе нормальное распределение
нормальное? в смысле равномерное?
> Dimka Maslov © (09.06.11 11:48) [18]
>
> для лучшего распределения случайных 32-битных чисел можно
> воспользоваться командой центрального процессора rtdsc и
> для полученного результа вычислить MD5, потом для всех четырех
> чисел MD5 сделать общий XOR.
Доказать, что в результате получим равномерное распределение - unreal :(
← →
Дмитрий С © (2011-06-10 05:50) [30]
> И. Павел © (09.06.11 12:54) [22]
>
> Если все же нужно комбинировать рандомы (для астрономических
> цифр, например), то для равномерного распределения, наверное,
> нужно делать как-то так: random(32768) * 32768 + random(32768).
> Т.е. чтобы области влияния рандомов не пересекались.
Тут надо еще доказать, что если мы будем брать не каждый random, а через один - то получим равномерное распределение.
> еще randomrange() попробовать..
>
функция основана на обычном random
← →
Sha © (2011-06-10 08:41) [31]> Дмитрий С © (09.06.11 08:54) [3]
> Есть мнение...
Последовательность значений каждого отдельного бита Random - циклическая.
Чем старше бит, тем длиннее цикл.
← →
Mystic © (2011-06-10 12:40) [32]>>нужно делать как-то так: random(32768) * 32768 + random(32768).
> Тут надо еще доказать, что если мы будем брать не каждый
> random, а через один - то получим равномерное распределение.
Откуда там равномерное распределение? Очевидно, что некоторые значения мы просто никогда не сумеем получить при том генераторе псевдослучайных чисел, что находится в Delphi. Если предположить, что seed у нас 16 бит, то первое значение однозначно определяет все последующие.
Чтобы делать такой фокус, надо чтобы датчики были хотя бы независимыми. Например, выцепить код генерации случайного числа, и сделать копию :)
← →
Dimka Maslov © (2011-06-10 13:31) [33]
> Дмитрий С © (10.06.11 05:47) [29]
Надо просто построить кривую распределения
← →
SergeyIT © (2011-06-10 15:06) [34]
> Надо просто построить кривую распределения
С этого и надо начинать, а не на форуме тему открывать.
А дальше уже решать, подойдет ли Random или свой генератор городить.
← →
Dimka Maslov © (2011-06-10 17:06) [35]
> А дальше уже решать, подойдет ли Random или свой генератор
> городить.
На принятие решения может уйти много времени. Было время когда у меня в машине крутился один сидюшник с мп3, постоянно включенный на проигрывание случайного трека. Долго крутился. Но вдруг я стал замечать, что когда машина начинала требовать дозаправки играла одна и та же песня. А поскольку я практически всегда езжу одним маршрутом и заправляюсь через почти одинаковые промежутки времени, можно сделать вывод, что генератор случайных чисел в аудиосистеме просто и естественно привязан к таймеру. Или например одна радиостанция в время обеда (а он у нас ровно в 13.00 центральнороссийского времени) упорно передает Алуэтту (она же - "в мире животных") тоже, значит функция рандом у них в компе циклится.
← →
Jeer © (2011-06-10 17:51) [36]
> Dimka Maslov © (10.06.11 13:31) [33]
> Надо просто построить кривую распределения
> SergeyIT © (10.06.11 15:06) [34]
> С этого и надо начинать, а не на форуме тему открывать.
> А дальше уже решать, подойдет ли Random или свой генератор
> городить.
Вы оба предлагаете визуализировать кривую распределения и на основе визуальной субъективной человеческой оценки решать вопрос о принадлежности распределения к тому или иному классу ?
← →
SergeyIT © (2011-06-10 18:35) [37]
> Вы оба предлагаете визуализировать кривую распределения
А просчитать разве нельзя, так сказать, математически? На достаточно большой выборке.
← →
Dimka Maslov © (2011-06-10 18:42) [38]
> Вы оба предлагаете визуализировать кривую распределения
> и на основе визуальной субъективной человеческой оценки
> решать вопрос о принадлежности распределения к тому или
> иному классу
Имея кривую распределения можно описать его математической формулой, и если оно окажется y = const, мы имеем дело с равномерным распределением. Помнится ещё в прошлом веке, будучи студентом паровозной школы, я такое делал в рамках курса "высшая математика"
← →
Дмитрий С © (2011-06-11 16:34) [39]
> Dimka Maslov © (10.06.11 18:42) [38]
Так я в своем примере так и сделал, только брал не все числа, а первые 50 - для скорости, да и на всех памяти не хватит. Получил примерно одинаковые значения - меня устраивает. +100 к уверенности добавил МВо :)
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2011.10.02;
Скачать: [xml.tar.bz2];
Память: 0.55 MB
Время: 0.003 c