Random глючит...

← →
_vitek_ (2003-01-25 02:56) [0]

Может кто сталкивался с проблемой генерирования случайных чисел... у меня они какие-то не случайные получаются ...
Пишу random(x) ... далее в проге идёт всяческая обработка ...
при запуске программы повторно, чила, зависящие от random-a те же.. В чём может быть проблема?

← →
Чих-пых (2003-01-25 03:14) [1]

Randomize в начале пробовал вставлять?

← →
Johnmen (2003-01-25 03:16) [2]

Ну вот, еще один, не знающий про F1 !

(Да я уже стихами заговорил !!!!!!!!!!!)

← →
Юрий Зотов (2003-01-25 06:56) [3]

Главное, сразу "глючит". А подумать?

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

← →
Anatoly Podgoretsky (2003-01-25 07:57) [4]

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

← →
Думкин (2003-01-25 08:41) [5]

Если устроить рейтинг спрашивания, то подобный вопрос будет 3-м в списке, после
1) Как ...(ваши варианты)?
2) Почему ...(ваши варианты)?
...Эх, суббота.

← →
Art (2003-01-25 13:21) [6]

Вообщето вы зря на него накинулись, в дельфях рандом натурально гонимый и может давать одни и теже последовательности символов даже с Randomize, выход у тебя один - топать на королевство дельфи, там есть раздел посвященый багам в Дэльфях (линк не помню) и поискть. Там подробный разбор как да почему.

← →
Юрий Зотов (2003-01-25 13:36) [7]

> Art © (25.01.03 13:21)

> в дельфях рандом натурально гонимый

Смелое утверждение. А доказать можете? Ну хоть чуть-чуть?

> Там подробный разбор как да почему

Потому что "программист", который якобы обнаружил этот "баг", зачем-то запихал Randomize в цикл "из бредового желания получить числа послучайнее" (это его собственные слова). Абсолютно не понимая, что это такое, зачем оно нужно и как оно работает. А потом был очень удивлен результатом. И виновата, конечно, оказалась Delphi, а не ее "рационализатор".

Вот еще одна цитата (из обсуждения): "эту заметку нужно не в разряд "подводные камни", а в раздел "глупость программистская" положить".

Где она, собственно, и лежит - в подразделе "Программист". То есть там, где описаны кривые руки, а не баги.

← →
Palladin (2003-01-25 14:09) [8]

насколько я знаю random вычисляется по формуле, опираясь на какое либо число... естественно если число на которое random опирается все время одинаковое то и последовательность будет все время одна и та же...

← →
Palladin (2003-01-25 14:12) [9]

2 _vitek_

ужасно смелое заявление про глючность делфи в отношении random... :)
в basic и сях, я думаю, с ним такаяже ситуация.

← →
A2 (2003-01-25 19:29) [10]

Посмотри "Искуство программирования для ЭВМ" Д.Кнута, том2 - там очень доходчиво написано про то, как получить псевдослучайные последовательности с хорошими статистическими характеристиками. Кстати, с точки зрения Кнута, функции random большинства компиляторов реализованы плохо.

← →
Юрий Зотов (2003-01-25 20:20) [11]

> A2 (25.01.03 19:29)

Книга Кнута писалась несколько десятков лет тому назад. Конечно, переиздания дорабатывались. Конечно, она не перестала быть классикой. Тем более - очень слабо верится, что разработчики СОВРЕМЕННЫХ компиляторов и их библиотек не читали эту книгу. И не сделали из нее нужных выводов. И не использовали их.

← →
Art (2003-01-26 08:36) [12]

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

← →
Юрий Зотов (2003-01-26 11:47) [13]

> Art © (26.01.03 08:36)

Еще раз - это не от корявости, это сделано специально. Иначе некоторые алгоритмы было бы очень трудно (практически невозможно) отлаживать.

Для того и введена Randomize. Она инициализирует начальное число ДСЧ исходя, например, из текущего времени суток в миллисекундах. В итоге при каждом запуске программы получается разная последовательность случайных чисел с вероятностью ее повтора, равной 1/86400000 (число миллисекунд в сутках).

← →
Sha (2003-01-26 13:06) [14]

> Art © (26.01.03 08:36)
> Вообще рандом это такая проблема...

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

← →
SuperUmnik (2003-01-27 07:52) [15]

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

← →
Anatoly Podgoretsky (2003-01-27 08:04) [16]

Есть ли кто ниюудь, кто обнаружил глюк в Random, именно глюк а не свои кривые ручки?

← →
Юрий Зотов (2003-01-27 08:29) [17]

> SuperUmnik © (27.01.03 07:52)

Sorry, но это, IMHO, какие-то новое слово в теории Вы сказали.

> т.к. число псевдослучайное то распределение чисел на отрезке
> равномерное.

Разве одно следует из другого? Разве вид распределения определяется псевдо или не псевдослучайностью? До сих пор я полагал, что алгоритмом генерации.

> в то время как истинно случайная выборка чисел на отрезке
> распределяется по Гауссу.

То есть, равномерное, лог-нормальное и прочие распределения не являются истинно случайными? А какими тогда? Неистинными? А что такое истинная и неистинная случайность? И разве гауссовский ДСЧ не может быть точно таким же псевдослучайным?

> поэтому для игрушек и прочего рандомизе использовать можно.
> а вот для поведения различных серьезных статистических моделей
> эту разницу всегда надо учитывать.!

Учитывать, конечно, надо. Только причем здесь игрушки или неигрушки? Надо просто брать именно то распределение, которое требуется именно для ДАННОЙ задачи. Нужно равномерное - берем равномерное, нужен Гаусс - берем Гаусса, нужно бимодальное - берем бимодальное. И т.д. При чем тут игрушки и неигрушки? Разве в серьезных моделях не используется равномерное распределение? Да сколько угодно.

← →
Garry_Dorado (2003-01-28 10:51) [18]

А почему бы просто не реализовать этот самый random самому? Делается это на регистре сдвига с обратной связью через ИСКЛ. ИЛИ. В рез. получается ПСП период повторения которой зависит от длины регистра и количества обратных связей.

← →
uw (2003-01-28 10:59) [19]

>SuperUmnik © (27.01.03 07:52)
Берем кость и бросаем. На отрезке [1, 6] никакого гаусса.

← →
Dms (2003-01-28 11:33) [20]

Любая сгенерированная последовательность будет ПСЕВДОслучайной, для генерации АБСОЛЮТНО случайных величин используют приемник "белого шума". Все дело в количестве факторов, влияющих на последовательность, а в этом случае их почти бесконечное количество :) ...

← →
malkolinge (2003-01-28 12:08) [21]

> Юрий Зотов © (25.01.03 13:36)
> > Art © (25.01.03 13:21)
>
> > в дельфях рандом натурально гонимый
>
> Смелое утверждение. А доказать можете? Ну хоть чуть-чуть?

Я смогу, вот вырезка из Хелпа по рандому

Note: Because the implementation of the Random function may change between compiler versions, we do not recommend using Random for encryption or other purposes that require reproducible sequences of pseudo-random numbers.

А вообще-то про генераторы псевдослучайных чисел правильно сказанно, надо свой писать (длся серьезных задач) тот же регистр циклический регистр, желательно с суммированием по разрядам. Хотя для перестановки 3 вопросов в разном порядке городить ТАКОЕ на мой ИМХО не стоит :)

← →
Anatoly Podgoretsky (2003-01-28 12:12) [22]

Почему ты называешь это глюком?

← →
malkolinge (2003-01-28 12:37) [23]

> Anatoly Podgoretsky © (28.01.03 12:12)
> Почему ты называешь это глюком?

Тут согласен. Хорошо закоментированный баг, это не глюк а ФИЧА ! :)

← →
han_malign (2003-01-28 12:57) [24]

Хорошо закоментированный баг, это не глюк а ФИЧА ! :)
- дам примерный перевод выдержки из - хелпа: мы не рекомендуем использовать Random для кодирования и в других случаях, когда требуется воспроизводимая последовательность псевдо-случайных чисел.
То есть то, что от версии к версии Delphi может давать разные последовательности чисел, при одинаковом начальном RandSeed, вы считаете глюком?(предыдущий тезис:"при запуске программы повторно, чила, зависящие от random-a те же")
З.Ы. При этом алгоритм Random гарантирует, что при переборе всех значений диапазона(32 бита), каждое значение повторится один и только один раз...

← →
han_malign (2003-01-28 13:08) [25]

Не помню чья теорема: При суммировании N элементов случайной последовательности с равномерным распределением, при стремлении N к бесконечности, распределение последовательности сумм будет стремиться к нормальному.(естественно для плотного диапазона вещественных чисел)

← →
uw (2003-01-28 13:45) [26]

Смысл нормального распределения такой. Бросаем монету много раз. Если она не кривая, т.е. распределение равномерное, то примерно в половине случаев выпадет орел. Так вот отклонение количества отклонений от этой половины и подчиняется нормальному закону - чем больше отклонение, тем меньше вероятность наблюдения такого отклонения.
Точно так же, если мы бросаем предмет на отрезок с равновероятным распределением, то количество попаданий предмета на некоторую седьмую часть отрезка составит примерно одну седьмую часть бросков. Отклонение от этого количества опять подчинено нормальному закону.
Random плох в том смысле, что, как тут было сказано, во все отрезки интервала, соответсвующего 32 битам, он будет попадать строго одинаковое количество раз. Именно это не отвечает проявлениям реального мира.

← →
Юрий Зотов (2003-01-28 15:10) [27]

> malkolinge

Разные версии библиотеки компилятора реализуют разные алгоритмы Random. Ну и что здесь странного? Наоборот, было бы странно, если бы компилятор и его библиотека не совершенствовались.

При этом любая версия гарантирует, что Random дает псевдослучайное равномерно распределенное число, и что без использования Randomize последовательность этих чисел будет строго одна и та же, а с использованием Randomize вероятность ее повтора составляет мизерную величину.

И в чем же глюк?

← →
Anatoly Podgoretsky (2003-01-28 15:18) [28]

Глюк как всегда в голове

← →
Dms (2003-01-28 16:12) [29]

> Random плох в том смысле, что, как тут было сказано, во
> все отрезки интервала, соответсвующего 32 битам, он будет
> попадать строго одинаковое количество раз. Именно это не
> отвечает проявлениям реального мира.

по моему ты погорячился ...

← →
Юрий Зотов (2003-01-28 16:42) [30]

> Dms (28.01.03 16:12)
И даже, IMHO, довольно сильно погорячился.

1. При чем тут отрезок в 32 бита - лично я так и понял.
2. От Random требуется только одно - чтобы она давала ТОЧНО то, что сказано о ней в документации. Она именно это и делает.
3. А в документации сказано, что Random дает равномерное распределение. Она именно для этого и написана. Почему вдруг кто-то решил потребовать от нее чего-то другого - непонятно. Почему вдруг это стало каим-то недостатком - тоже непонятно. С таким же успехом можно возмущаться тем, что функция StrToInt не выключает монитор, а пароходы не летают по небу.

Для тех, кто не в курсе.

Во всех языках программирования основной ДСЧ - это именно равномерный ДСЧ. Потому что на его основе программист может сам получить числа с нужным ему распределением, алгоритмы для этого хорошо известны, обоснованы теоретически и пр. Но не наоборот.

Вот именно поэтому Random и сделана, как равномерный генератор. И свое дело она делает, уверяю Вас, очень даже неплохо. Но только СВОЕ, а не ЧУЖОЕ. И не надо требовать от нее того, чего она и не должна делать.

А кому нужен Гаусс - так в Delphi он тоже есть. Только при чем здесь Random - непонятно. Вы же не требуете от парохода, чтобы он по небу летал?

← →
Dms (2003-01-28 17:09) [31]

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

← →
uw (2003-01-29 14:15) [32]

>Юрий Зотов © (28.01.03 16:42)

>1. При чем тут отрезок в 32 бита - лично я так и понял

Хороший генератор псевдослучайных чисел и в самом деле дает равномерное распределение, кто против! Более того, если его рабочий регистр 32-битный, то он гарантирует нециклическую последовательность длиной примерно 2^31. Вот мы получили такую последовательность и видим, что в ней каждое число от 1 до 2^31 присутствует ровно 1 раз. Это и не соответствует никакой реальности.
В частности, если мы применим "не помню чью теорему" (han_malign © (28.01.03 13:08)), то выяснится, что для нашего генератора она не работает.
Только на это я и намекал в предыдущем своем эссе.

← →
Anatoly Podgoretsky (2003-01-29 14:20) [33]

Так тебе нужен генератор реальных случайных чисел, чего же ты требуешь этого от Random

← →
Anatoly Podgoretsky (2003-01-29 14:21) [34]

Но хотелось бы увидеть все таки пример глюка.

← →
Dms (2003-01-29 14:36) [35]

> Хороший генератор псевдослучайных чисел и в самом деле дает
> равномерное распределение

Это правильно.

> Более того, если его рабочий регистр 32-битный, то он гарантирует
> нециклическую последовательность длиной примерно 2^31.
> Вот мы получили такую последовательность и видим, что в
> ней каждое число от 1 до 2^31 присутствует ровно 1 раз

Полная охинея. Откуда такие утверждения ? Если последовательност нециклическая, это не означает, что в ней числа все разные. Да и вообще, на основании чего можно говорить, что RANDOM выдает неравномерное распределение, т.е. является ГЛЮЧНЫМ ?

← →
uw (2003-01-29 14:41) [36]

>Dms (29.01.03 14:36)
Это следует из того, что если мы начали с числа 75 и после него получили 12345, а потом где-то опять увидели 75, то будьте уверены, что после него будет 12345.
А Random выдает равномерное распределение.

← →
Dms (2003-01-29 14:54) [37]

> Это следует из того, что если мы начали с числа 75 и после
> него получили 12345, а потом где-то опять увидели 75, то
> будьте уверены, что после него будет 12345

Не буду уверен !!! Это полная неправда, можно проверить самому на практике, но нелепость видна и так. RANDOM никогда не выдаст циклическую последовательность, неважно какой у него там регистр !

← →
Digitman (2003-01-29 15:10) [38]

>Dms

Выдаст. Результирующий "белый шум" не имеет ничего общего с алгоритмом генерации, базирующемся на 64-разр. значениях

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

рано или поздно результирующая последовательность произведений в EDX:EAX повторится

← →
Dms (2003-01-29 15:16) [39]

Это понятно, иначе был бы идеальный вариант. Но было сказано, что после 75 всегда будет 12345. Это-то полный бред.

← →
han_malign (2003-01-29 15:17) [40]

>RANDOM никогда не выдаст циклическую последовательность, неважно какой у него там регистр !

У Random - 32 битный регистр и если раз в милисекунду брать его значение - то через 49.7... дней мы выйдем на второй круг циклической последовательности...

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

Random глючит... Найти похожие ветки