(Untitled)

[_winnie]

Невозможно 2147483648 конфет раздать поровну миллиарду детишек: у кого-то будет две, у кого-то три.
Будьте осторожны с rand()%N

Ссылки:
Как правильно делать в C++11: http://dobrokot.ru/pics/i2014-06-27__02-01-24_55kb.png (из этой презентации, видео), спасибо bik_top

Comments

[realsupport]

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

[_winnie]

"раздать случайно" это "вероятности одинаковые". Когда делаем rand()%N - они получаются не одинаковые. Для небольших N чуть-чуть неодинаковые, а для больших - уже заметно.

Связанная задача: Имея честную монетку, научиться эмулировать честный игральный кубик с шестью гранями.

[realsupport]

Ах, вот ты о чем.
Только не просто для больших/небольших, а связанных с RAND_MAX:
Тут более-менее толково написано:
http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator

[ahaxopet]

Просто эмулировать кубик легко - кидаем монетку три раза подряд, генерируем число от нуля до семи. Если получилось 6 или 7 - результат отбрасываем, повторяем упражнение.

А вот как эмулировать эффективно - это уже интереснее..

[dewfy]

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

[axc]

rand() обещал, вроде, равномерное?

[dewfy]

математики любят поднимать тост: "Все нормально" - что в переводе означает, что по теореме Ляпунова любое распределение стремится к нормальному.

Кста, а где обещали? я тут открыл парочку аффторитетных ссылок и нигде не обещают. Только cplusplus.com упомянули такое: "Notice though that this modulo operation does not generate uniformly distributed random numbers in the span (since in most cases this operation makes lower numbers slightly more likely)."

[_winnie]

1) Это про суммирование большого числа случайных величин. Фраза "распределение стремится к нормальному распределению' довольно бессмыслена, примерно так же как "любое число стремится к бесконечности".

К rand() это не относится.

2) У теоремы Ляпунова есть довольно сильные ограничения (i.i.d. и ограничение дисперсий).

[archaicos]

Знамо дело.

[jakobz]

Так вроде везде есть overload, который Rand(3)? Или он также работает?

[_winnie]

Это Кресты. Работает правильно, но замучаешься подробно рассказывать библиотеке, какие детальки с какими соединить. http://dobrokot.ru/pics/i2014-06-27__02-01-24_55kb.png

( из презентации https://onedrive.live.com/view.aspx?resid=E66E02DC83EFB165!312&cid=e66e02dc83efb165&app=PowerPoint )

[major_m]

Интересно, это где-то критично? Особенно при условии, что rand сам по себе возвращает _псевдо_-случайные значения.

[_winnie]

Я на это напоролся, когда статистический тест показал, что количество коллизий в хеш-таблице в два раза больше теоретического.
Так как я пытался из 20-битного хеша получить "случайный" индекс в 700'000-элементном массиве.

Вообще можно представить себе фейл в любом месте, где использутся rand() и надеются на равномерность его результата

[realsupport]

"Где неправильно пользуются rand()", извините. (с) Слонёнок
Так же можно представить себе фейл в любом месте, где пользуются острым ножиком.
Индустрия уже перешагнула этап полного детерминизма и программы просто работают "в большинстве случаев", а если ошибок в каком-то сценарии стало слишком много - выпускается патч.
Написание программ, свободных от ошибок - удел сильно больных на голову одиночек :)
Попытка написания программ, свободных от ошибок - удел слегка больных на голову одиночек :)

[_winnie]

> Написание программ, свободных от ошибок - удел сильно больных на голову одиночек :)
http://wizzard0.livejournal.com/440212.html#comments