Здравствуйте.

Недавно на СОшке мне посоветовали делать не так:

а так

Где-то ещё встречал аналогичный совет.

Вопрос: посоветуйте, пожалуйста, где почитать про разницу, про то, почему второе лучше, и т.д.

Спасибо.

Второе равномернее.
В этом дурацком треде можно видеть разницу наглядно.

Static, Спасибо. Тред и правда немного дурацкий)) Но..
1) впечатлила эта картинка

2) то, что распределение менее равномерное при остатке от деления, я, в общем-то, догадывался, но вот почему - главный для меня вопрос - я пока не пойму.

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

> соответственно периодичность повторения значений младших битов выше, чем старших
Вот как-то для меня не "соответственно"...
Интуитивно мне понятно, что старшие биты "лучше", чем младшие, но почему (ключевое слово) - не понятно

Если на пальцах, иначе ничего не приходит в голову, то когда используется операция получения остатка, то старшие биты просто отсекаются. То есть вероятность получения псевдослучайного числа определяется делителем (например, если делитель равен 10, то вероятность получения любого из чисел в диапазоне от 0 до 9 будет 1/10).
Когда мы используем деление, то на результат влияет весь диапазон от 0 до RANDOM_MAX. Понятно, что дальше все это усекается, но согласитесь, что вероятность выпадения одного числа из, допустим, 32768 много меньше чем для одного из 10. Ну а чем меньше вероятность, тем выше случайность. Как-то так ...

В

при N, равном 10, вероятность получения любого целого числа от 0 до 9 будет также 1/10. Однако в случае остатка от деления распределение этой самой вероятности явно отличается от варианта с приведением к диапазону от 0 до 1, умножением на N и отбрасыванием дробной части. Вот откуда берётся отличие в распределении вероятности мне и не понятно.


при вычислении остатка от деления также используется деление)) Правда целочисленное, но всё же... Да и потом - вопрос, ессно, не в затратах процессора, а в разности полученных результатов

Это сообщение отредактировал(а) borisbn - 30.4.2014, 08:53

отсюда начался крестовый поход против rand(). Насколько я помню, Стефан объясняет в чем проблема.
Тут дискуссия. Ну и еще одна ссылка

vinter, спасибо. Крайне полезные ссылки. Но больше всего мне стало понятно из ответа господина dr jimbob на SO

Насколько я понял - проблема не в операции остатка от деления, а в конкретной реализации функции rand(). Правильно ?

borisbn, наоборот, проблема в манипуляциях над тем, что возвращает rand(). В нём самом нет проблемы. В видео объясняется, с примерами, почему существует проблема. К примеру, когда ты делишь(%) на 100 результат rand()  у тебя получается следующая ситуация. Некоторые числа более вероятны, т.к. 32767 не делится нацело на 100. Поэтому, к примеру, появление чисел от 67 до 99 имеет меньшую вероятность, чем от 0 до 67. Вроде так.

vinter, ещё раз спасибо. Я не посмотрел видео, а надо было. Насколько я понял если брать остаток от деления на 2^x, то распределение останется нормальным, т.к. максимальное число, возвращаемое rand'ом как раз является степенью двойки. Во всех остальных случаях распределение изменяется. Правильно?

borisbn, да, насколько я понимаю. По крайней мере я не вижу каких-либо проблем если использовать rand() mod 2^x

точнее не совсем. Всё таки небольшой минус даже в таком подходе есть. Т.к. нумерация начинается с 0, то RAND_MAX всё равно не будет делится на 2^x, а это даст небольшое преимущество некоторым числам.