Компилируется с gcc c99, а не с ideone c99.Целочисленное переполнение - PullRequest
Новая
       9

Компилируется с gcc c99, а не с ideone c99.Целочисленное переполнение

0 голосов
/ 11 октября 2011 
int rng(int min, int max){
    int result = min + ( ( (max - (min - 1) ) * rand() ) / (RAND_MAX + 1) );
    return result;
}

Это не скомпилируется с ideone в режиме c99, но происходит, когда я использую gcc на CodeBlocks, когда на -std=c99.Я подумал, что использование long int поможет, но, видимо, не так.Я использую ideone, когда пробую что-то в школе, потому что у них просто VC ++, а я делаю C C99.Я бы не хотел не использовать эту функцию, когда она мне нужна, и поэтому здесь я спрашиваю, что не так.

Ответы [ 4 ]

2 голосов
/ 11 октября 2011

Проверьте это в ideone. 

#include <stdlib.h>
#include <stdio.h>
int main(void) { printf("%x\n", RAND_MAX); return 0; }

Вы заметите, что он печатает 7fffffff, что, вероятно, также MAX_INT.Что происходит, когда вы вычисляете MAX_INT + 1?Вычисление MAX_INT + 1 является неправильным, независимо от того, получаете ли вы ошибку.

Есть много способов записать равномерный генератор случайных чисел с заданным равномерным ГСЧ с другим диапазоном, но сделать это правильно немного сложнее.

Это должно работать всякий раз, когда max - min <= RAND_MAX и max > min ... 

int rng(int min, int max)
{
    int range = max - min + 1;
    int factor = ((unsigned) RAND_MAX + 1) / range;
    int x;
    do {
        x = rand() / factor;
    } while (x >= range);
    return x + min;
}

Это должно быть одинаковым и давать относительно высокое качество (известно, что использование % вызывает серьезныепроблемы качества с некоторыми PRNG и определенными диапазонами).

2 голосов
/ 11 октября 2011

На самом деле, на моем компиляторе это выдает warning: integer overflow in expression [-Woverflow].

Проблема вызвана RAND_MAX + 1.RAND_MAX часто совпадает с INT_MAX.Добавление 1 к INT_MAX, конечно, приводит к неопределенному поведению (за исключением того, что компилятор ловит во время компиляции и заменяет код чем-то другим).

Если вы хотите увидеть в действии, почему это плохо, сделайте следующее:

scanf("%d", &dummy); /* So the compiler won't catch it. */
dummy += INT_MAX;

gcc -ftrapv -Wall -Wextra # ftrapv is the key point
1 голос
/ 11 октября 2011

Без фактического текста ошибки трудно сказать, но наличие "переполнения целых чисел" в заголовке указывает на ... ну, целочисленное переполнение: -)

Наиболее вероятный виновник - ваш бит RAND_MAX +1, если RAND_MAX фактически совпадает с INT_MAX.

Если вы хотите отказаться от идеального распределения ваших случайных чисел (a) , вы можете выбрать что-то вроде: 

int rng (int minVal, int maxVal) {
    int result = min + (rand() % (maxVal + 1 - minVal));
    return result;
}

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

0 голосов
/ 11 октября 2011

Это действительно может привести к целочисленному переполнению, если (max - min + 1) * RAND_MAX > INT_MAX.У вас есть несколько способов избежать этого:

  • приведите промежуточные значения к типу, который может хранить их без переполнения, например uint64_t или double, или
  • используйте вместо этого оператор модуля %, например: 
int rng ( int min, int max ) {
    return min + rand() % (max - min + 1);
}

Обратите внимание, что использование % имеет несколько недостатков: если max - min + 1 не является степенью двойки, он будетслегка сместить результаты в сторону нижнего предела диапазона (потому что он не разделит RAND_MAX+1 равномерно);и если оно равно степени двух, это может уменьшить период и качество потока случайных чисел (поскольку младшие биты LCRNG менее случайны, чем старшие биты).

Существуют способы избежать этих проблем путем тщательного кодирования.Для примера посмотрите стандартную реализацию Random.nextInt() в Java, которая может быть довольно просто переведена на C: 

int rng (int min, int max) {
    int n = max - min + 1;
    int bits, val;

    if ((n & -n) == n)  // i.e., n is a power of 2
        return min + (int)((n * (uint64_t)rand()) / ((uint64_t)RAND_MAX + 1));

    do {
        bits = rand();
        val = bits % n;
    } while(bits - val > RAND_MAX - (n-1));

    return min + val;
}

(я думаю этот перевод долженработать как задумано. Это оказалось немного хитрее, чем я, хотя, поскольку исходный код Java опирается, в сущности, на допущение, что INT_MAX = RAND_MAX = (1<<31)-1, что может не выполняться в C.)

...