1) впечатлила эта картинка
2) то, что распределение менее равномерное при остатке от деления, я, в общем-то, догадывался, но вот почему - главный для меня вопрос - я пока не пойму.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > random и остаток от деления |
| Автор: borisbn 29.4.2014, 14:38 | ||||
| Здравствуйте. Недавно на СОшке мне посоветовали делать не так:
а так
Где-то ещё встречал аналогичный совет. Вопрос: посоветуйте, пожалуйста, где почитать про разницу, про то, почему второе лучше, и т.д. Спасибо. |
| Автор: Static 29.4.2014, 16:48 |
| Второе равномернее. В этом http://www.gamedev.ru/flame/forum/?id=168177&page=4 можно видеть разницу наглядно. |
| Автор: borisbn 29.4.2014, 17:29 |
| Static, Спасибо. Тред и правда немного дурацкий)) Но.. 1) впечатлила эта картинка 2) то, что распределение менее равномерное при остатке от деления, я, в общем-то, догадывался, но вот почему - главный для меня вопрос - я пока не пойму. |
| Автор: baldman88 29.4.2014, 18:58 |
| Насколько мне помниться из разъяснений преподавателя, то генераторы псевдослучайных чисел работают по определенному алгоритму (ну это понятно), и соответственно периодичность повторения значений младших битов выше, чем старших. Остаток от деления как раз и берет значения этих младших битов. В противовес операция деления, которая хоть и более ресурсоемка, вследствии использования чисел с плавающей точкой, но зависит от значения старших битов. Как следствие более высокая, так сказать, псевдослучайность. На полноту ответа не претендую, но суть, думаю, уловить можно. |
| Автор: borisbn 29.4.2014, 22:34 |
| > соответственно периодичность повторения значений младших битов выше, чем старших Вот как-то для меня не "соответственно"... Интуитивно мне понятно, что старшие биты "лучше", чем младшие, но почему (ключевое слово) - не понятно |
| Автор: baldman88 29.4.2014, 23:19 |
| Если на пальцах, иначе ничего не приходит в голову, то когда используется операция получения остатка, то старшие биты просто отсекаются. То есть вероятность получения псевдослучайного числа определяется делителем (например, если делитель равен 10, то вероятность получения любого из чисел в диапазоне от 0 до 9 будет 1/10). Когда мы используем деление, то на результат влияет весь диапазон от 0 до RANDOM_MAX. Понятно, что дальше все это усекается, но согласитесь, что вероятность выпадения одного числа из, допустим, 32768 много меньше чем для одного из 10. Ну а чем меньше вероятность, тем выше случайность. Как-то так ... |
| Автор: borisbn 30.4.2014, 08:51 | ||||||
В
при N, равном 10, вероятность получения любого целого числа от 0 до 9 будет также 1/10. Однако в случае остатка от деления распределение этой самой вероятности явно отличается от варианта с приведением к диапазону от 0 до 1, умножением на N и отбрасыванием дробной части. Вот откуда берётся отличие в распределении вероятности мне и не понятно.
при вычислении остатка от деления также используется деление)) Правда целочисленное, но всё же... Да и потом - вопрос, ессно, не в затратах процессора, а в разности полученных результатов |
| Автор: vinter 30.4.2014, 15:57 |
| http://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful начался крестовый поход против rand(). Насколько я помню, Стефан объясняет в чем проблема. http://www.reddit.com/r/programming/comments/1rnudl/quite_interesting_why_cs_rand_is_considered/ дискуссия. Ну и еще одна http://eternallyconfuzzled.com/arts/jsw_art_rand.aspx |
| Автор: borisbn 2.5.2014, 11:13 | ||
vinter, спасибо. Крайне полезные ссылки. Но больше всего мне стало понятно из http://stackoverflow.com/a/4195994
Насколько я понял - проблема не в операции остатка от деления, а в конкретной реализации функции rand(). Правильно ? |
| Автор: vinter 2.5.2014, 12:00 |
| borisbn, наоборот, проблема в манипуляциях над тем, что возвращает rand(). В нём самом нет проблемы. В видео объясняется, с примерами, почему существует проблема. К примеру, когда ты делишь(%) на 100 результат rand() у тебя получается следующая ситуация. Некоторые числа более вероятны, т.к. 32767 не делится нацело на 100. Поэтому, к примеру, появление чисел от 67 до 99 имеет меньшую вероятность, чем от 0 до 67. Вроде так. |
| Автор: borisbn 3.5.2014, 08:49 |
| vinter, ещё раз спасибо. Я не посмотрел видео, а надо было. Насколько я понял если брать остаток от деления на 2^x, то распределение останется нормальным, т.к. максимальное число, возвращаемое rand'ом как раз является степенью двойки. Во всех остальных случаях распределение изменяется. Правильно? |
| Автор: vinter 3.5.2014, 11:07 |
| borisbn, да, насколько я понимаю. По крайней мере я не вижу каких-либо проблем если использовать rand() mod 2^x |
| Автор: vinter 3.5.2014, 11:38 |
| точнее не совсем. Всё таки небольшой минус даже в таком подходе есть. Т.к. нумерация начинается с 0, то RAND_MAX всё равно не будет делится на 2^x, а это даст небольшое преимущество некоторым числам. |
