Почему rand () + rand () выдает отрицательные числа?

304

Я заметил, что rand()библиотечная функция, когда она вызывается только один раз в цикле, почти всегда выдает положительные числа.

for (i = 0; i < 100; i++) {
    printf("%d\n", rand());
}

Но когда я добавляю два rand()звонка, сгенерированные номера теперь имеют больше отрицательных чисел.

for (i = 0; i < 100; i++) {
    printf("%d = %d\n", rand(), (rand() + rand()));
}

Может кто-нибудь объяснить, почему я вижу отрицательные числа во втором случае?

PS: я инициализирую семя перед циклом как srand(time(NULL)).

badmad
источник
11
rand()не может быть отрицательным ...
twentylemon
293
rand () + rand () может owerflow
маскачовник
13
Что RAND_MAXдля вашего компилятора? Обычно вы можете найти его в stdlib.h. (Забавно: проверяю man 3 rand, оно содержит однострочное описание «плохой генератор случайных чисел».)
usr2564301
6
делай то, что делал бы каждый нормальный программист abs(rand()+rand()). Я предпочел бы иметь положительный UB, чем отрицательный! ;)
Виниций Камакура
11
@hexa: это не так для UB, так как уже происходит добавление. Вы не можете заставить UB стать определенным поведением . Здравомыслящий progrtammer бы избежать UB , как ад.
слишком честно для этого сайта

Ответы:

542

rand()определен для возврата целого числа между 0и RAND_MAX.

rand() + rand()

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

PP
источник
4
@JakubArnold: Как то, что поведение переполнения определяется каждым языком по-разному? У Python, например, нет (ну, вплоть до доступной памяти), так как int только растет.
слишком честно для этого сайта
2
@Olaf Это зависит от того, как язык решает представлять целые числа со знаком. В Java не было механизма для обнаружения целочисленного переполнения (до java 8), и он определил его для переноса, а Go использует только представление дополнения 2 и определяет его допустимым для целочисленных переполнений со знаком. C, очевидно, поддерживает более чем 2 дополнения.
PP
2
@EvanCarslake Нет, это не универсальное поведение. То, что вы говорите, о представлении дополнения 2. Но язык C допускает и другие представления. Спецификация языка C говорит, что целочисленное переполнение со знаком не определено . Таким образом, в общем, ни одна программа не должна полагаться на такое поведение и должна тщательно кодировать, чтобы не вызывать целочисленное переполнение со знаком. Но это не применимо для целых чисел без знака, так как они будут «оборачиваться» четко определенным образом (сокращение по модулю 2). [продолжение] ...
PP
12
Это цитата из стандарта C, связанная со переполнением целых чисел со знаком: если во время вычисления выражения возникает исключительное условие (то есть, если результат не определен математически или отсутствует в диапазоне представимых значений для его типа), поведение не определено
PP
3
@EvanCarslake немного отошел от вопроса, который используют компиляторы C, и для целых чисел со a + b > aзнаком они могут предположить, что если они это знают b > 0. Они также могут предположить, что если позднее будет выполнен оператор, a + 5то текущее значение будет ниже INT_MAX - 5. Таким образом, даже на процессоре / интерпретаторе дополнения 2 без ловушек программа может вести себя не так, как если бы ints была дополнением 2 без ловушек.
Мацей Пехотка
90

Проблема в дополнении. rand()возвращает intзначение 0...RAND_MAX. Итак, если вы добавите два из них, вы получите до RAND_MAX * 2. Если это превышает INT_MAX, результат сложения переполняет допустимый диапазон, который intможет содержать. Переполнение значений со знаком является неопределенным поведением и может привести к тому, что ваша клавиатура разговаривает с вами на иностранных языках.

Поскольку здесь нет никакого смысла в добавлении двух случайных результатов, простая идея - просто не делать этого. В качестве альтернативы вы можете разыграть каждый результат unsigned intдо сложения, если это может содержать сумму. Или используйте больший тип. Обратите внимание, что longэто не обязательно шире, чем intто же самое, long longесли оно intимеет размер не менее 64 бит!

Вывод: просто избегайте сложения. Это не обеспечивает больше «случайности». Если вам нужно больше битов, вы можете объединить значения sum = a + b * (RAND_MAX + 1), но для этого также, вероятно, требуется больший тип данных, чем int.

Поскольку ваша заявленная причина заключается в том, чтобы избежать нулевого результата: Этого нельзя избежать, сложив результаты двух rand()вызовов, так как оба могут быть нулевыми. Вместо этого вы можете просто увеличить. Если RAND_MAX == INT_MAXэто не может быть сделано в int. Тем не менее, (unsigned int)rand() + 1будет делать очень и очень вероятно. Вероятно (не окончательно), потому что это требует UINT_MAX > INT_MAX, что верно для всех реализаций, о которых я знаю (которые охватывают довольно много встроенных архитектур, DSP и всех настольных, мобильных и серверных платформ последних 30 лет).

Предупреждение:

Хотя здесь уже добавлены комментарии, обратите внимание, что при добавлении двух случайных значений не получается равномерное распределение, а треугольное распределение, например, бросание двух кубиков: чтобы получить 12(два кубика), нужно показать оба кубика 6. поскольку 11уже есть два возможных варианта: 6 + 5или 5 + 6и т. д.

Таким образом, дополнение также плохо с этой стороны.

Также обратите внимание, что rand()генерируемые результаты не являются независимыми друг от друга, так как они генерируются генератором псевдослучайных чисел . Отметим также, что в стандарте не указывается качество или равномерное распределение рассчитанных значений.

слишком честен для этого сайта
источник
14
@badmad: Так что, если оба вызова вернут 0?
слишком честно для этого сайта
3
@badmad: Мне просто интересно, UINT_MAX > INT_MAX != falseгарантируется ли стандарт. (Звучит вероятно, но не уверен, если требуется). Если это так, вы можете просто привести один результат и приращение (в таком порядке!).
слишком честно для этого сайта
3
Если вы хотите получить неравномерное распределение, есть смысл добавлять несколько случайных чисел: stackoverflow.com/questions/30492259/…
Cœur
6
чтобы избежать 0, просто "пока результат 0, перекатывайся"?
Оливье Дюлак
2
Не только добавление их является плохим способом избежать 0, но также приводит к неравномерному распределению. Вы получаете распределение, подобное результатам бросания костей: 7 в 6 раз чаще, чем 2 или 12.
Бармар
36

Это ответ на уточнение вопроса, сделанный в комментарии к этому ответу ,

причина, по которой я добавлял, состояла в том, чтобы избежать «0» как случайного числа в моем коде rand () + rand () было быстрым грязным решением, которое мне пришло в голову.

Проблема состояла в том, чтобы избежать 0. Есть (по крайней мере) две проблемы с предлагаемым решением. Один из них, как указывают другие ответы, rand()+rand()может вызывать неопределенное поведение. Лучший совет - никогда не вызывать неопределенное поведение. Другая проблема заключается в том, что нет никакой гарантии, что rand()0 не получится дважды подряд.

Следующее отклоняет ноль, избегает неопределенного поведения и в подавляющем большинстве случаев будет быстрее, чем два вызова rand():

int rnum;
for (rnum = rand(); rnum == 0; rnum = rand()) {}
// or do rnum = rand(); while (rnum == 0);
Дэвид Хаммен
источник
9
Как насчет rand() + 1?
Askvictor
3
@askvictor Это может переполниться (хотя это маловероятно).
геррит
3
@gerrit - зависит от MAX_INT и RAND_MAX
askvictor
3
@gerrit, я был бы удивлен, если бы они не были одинаковыми, но я полагаю, это место для педантов :)
askvictor
10
Если RAND_MAX == MAX_INT, rand () + 1 переполнится с той же вероятностью, что и значение rand (), равное 0, что делает это решение совершенно бессмысленным. Если вы готовы рискнуть и игнорировать возможность переполнения, вы можете также использовать rand () как есть и игнорировать возможность его возврата 0.
Эмиль Йержабек
3

В основном rand()производите числа между 0и RAND_MAX, и 2 RAND_MAX > INT_MAXв вашем случае.

Вы можете модулировать с максимальным значением вашего типа данных, чтобы предотвратить переполнение. Это конечно нарушит распределение случайных чисел, но randэто просто способ получить быстрые случайные числа.

#include <stdio.h>
#include <limits.h>

int main(void)
{
    int i=0;

    for (i=0; i<100; i++)
        printf(" %d : %d \n", rand(), ((rand() % (INT_MAX/2))+(rand() % (INT_MAX/2))));

    for (i=0; i<100; i++)
        printf(" %d : %ld \n", rand(), ((rand() % (LONG_MAX/2))+(rand() % (LONG_MAX/2))));

    return 0;
}
Khaled.K
источник
2

Возможно, вы могли бы попробовать довольно хитрый подход, убедившись, что значение, возвращаемое суммой 2 rand (), никогда не превышает значение RAND_MAX. Возможным подходом может быть sum = rand () / 2 + rand () / 2; Это гарантирует, что для 16-битного компилятора со значением RAND_MAX 32767, даже если оба rand возвращают 32767, даже тогда (32767/2 = 16383) 16383 + 16383 = 32766, таким образом, не будет получена отрицательная сумма.

Джибин Мэтью
источник
1
ОП хотела исключить 0 из результатов. Сложение также не обеспечивает равномерного распределения случайных значений.
слишком честно для этого сайта
@Olaf: нет никакой гарантии, что два последовательных вызова в rand()оба не приведут к нулю, поэтому желание избежать нуля не является хорошей причиной для добавления двух значений. С другой стороны, желание иметь неравномерное распределение было бы хорошей причиной для добавления двух случайных значений, если одно гарантирует, что переполнение не произойдет.
суперкат
1

причина, по которой я добавлял, состояла в том, чтобы избежать «0» как случайного числа в моем коде rand () + rand () было быстрым грязным решением, которое мне пришло в голову.

Простое решение (хорошо, назовите это «Hack»), которое никогда не приводит к нулевому результату и никогда не будет переполнено:

x=(rand()/2)+1    // using divide  -or-
x=(rand()>>1)+1   // using shift which may be faster
                  // compiler optimization may use shift in both cases

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

Кевин Феган
источник
1
Sidenote: Осторожно с правыми сдвигами знаковых переменных. Это только хорошо определено для неотрицательных значений, для отрицательных, это определено реализацией. (К счастью, rand()всегда возвращает неотрицательное значение). Однако я бы оставил здесь оптимизацию для компилятора.
слишком честно для этого сайта
@ Олаф: В общем, подписанное деление на два будет менее эффективным, чем смена. Если автор компилятора не приложил усилий к тому, чтобы сообщить компилятору, что randон будет неотрицательным, сдвиг будет более эффективным, чем деление на целое число со знаком 2. Деление на 2uможет работать, но если xэто intможет привести к предупреждению о неявном преобразовании из неподписанного подписать
суперкат
@supercat: Пожалуйста, прочитайте мой комментарий снова. Вы должны очень хорошо знать, что любой разумный компилятор будет использовать сдвиг в / 2любом случае (я видел это даже для чего-то вроде -O0, то есть без явно заданных оптимизаций). Это, пожалуй, самая тривиальная и наиболее устоявшаяся оптимизация кода на C. Точка деления хорошо определяется стандартом для всего целочисленного диапазона, а не только для неотрицательных значений. Опять же: оставьте жалобы компилятору, прежде всего напишите правильный и понятный код. Это даже более важно для начинающих.
слишком честно для этого сайта
@Olaf: Каждый протестированный мной компилятор генерирует более эффективный код при сдвиге rand()вправо на единицу или делении на, 2uчем при делении на 2, даже при использовании -O3. Можно было бы разумно сказать, что такая оптимизация вряд ли имеет значение, но выражение «оставить такие оптимизации для компилятора» будет означать, что компиляторы, скорее всего, их выполнят. Вы знаете какие-нибудь компиляторы, которые на самом деле будут?
суперкат
@supercat: Тогда вы должны использовать более современные компиляторы. GCC только что сгенерировал прекрасный код в последний раз, когда я проверял сгенерированный Ассемблер. Тем не менее, сколько бы я ни ценил эту гроуп, я бы предпочел не подвергаться преследованиям в той степени, в которой вы присутствовали в последний раз. Этим сообщениям уже много лет, мои комментарии абсолютно действительны. Спасибо.
слишком честно для этого сайта
1

Чтобы избежать 0, попробуйте это:

int rnumb = rand()%(INT_MAX-1)+1;

Вы должны включить limits.h.

Doni
источник
4
Это удвоит вероятность получить 1. Это в основном то же самое (но, возможно, медленнее), чем условное добавление 1, если rand()приводит к 0.
говоря, для этого сайта
Да, ты прав, Олаф. Если rand () = 0 или INT_MAX -1, число будет равно 1.
Дони
Еще хуже, когда я думаю об этом. Это фактически удвоит пригодность для 1и 2(все предполагается RAND_MAX == INT_MAX). Я забыл о - 1.
слишком честно для этого сайта
1
-1Здесь не служит никакой ценности. rand()%INT_MAX+1; будет по-прежнему генерировать только значения в диапазоне [1 ... INT_MAX].
chux - Восстановить Монику
-2

Хотя то, что все остальные говорили о вероятном переполнении, вполне может быть причиной негатива, даже если вы используете целые числа без знака. Реальная проблема на самом деле заключается в использовании функции времени / даты в качестве начального числа. Если вы действительно познакомились с этой функциональностью, вы точно поймете, почему я так говорю. То, что он на самом деле делает, это дает расстояние (прошедшее время) с данной даты / времени. Хотя использование функции даты / времени в качестве семени для rand () является очень распространенной практикой, на самом деле это не лучший вариант. Вы должны искать лучшие альтернативы, так как по этой теме существует множество теорий, и я не смог бы рассмотреть все из них. Вы добавляете в это уравнение возможность переполнения, и этот подход был обречен с самого начала.

Те, кто разместил rand () + 1, используют решение, которое используется чаще всего, чтобы гарантировать, что они не получат отрицательное число. Но такой подход тоже не самый лучший.

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

Потратив дополнительное время и усилия на изучение, изучение и правильную реализацию функциональности rand (), стоит своих усилий и времени. Просто мои два цента. Удачи в ваших начинаниях ...

Марк Круг
источник
2
rand()не указывает, какое семя использовать. Стандарт делает указание его использовать псевдослучайный генератор, а не отношение к любому времени. В нем также не говорится о качестве генератора. На самом деле проблема явно в переполнении. Обратите внимание, что rand()+1используется, чтобы избежать 0; rand()не возвращает отрицательное значение. Извините, но вы упустили момент здесь. Речь идет не о качестве PRNG. ...
слишком честно для этого сайта
... Хорошей практикой в ​​GNU / Linux является его посев /dev/randomи последующее использование хорошего PRNG (не уверенного в качестве rand()от glibc) или продолжение использования устройства - рискуя тем, что ваше приложение блокируется, если энтропии недостаточно. Попытка внести энтропию в приложение вполне может быть уязвимостью, так как ее легче атаковать. И теперь дело доходит до ужесточения - не здесь
слишком честно для этого сайта