Блог

Главная - Вопросы по программированию - Компиляция с помощью gcc c99, а не с ideone c99. Переполнение целых чисел

Компиляция с помощью gcc c99, а не с ideone c99. Переполнение целых чисел

#c #c99

#c #c99

Вопрос:

 int rng(int min, int max){
    int result = min   ( ( (max - (min - 1) ) * rand() ) / (RAND_MAX   1) );
    return resu<
}

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

Комментарии:

1. Пожалуйста, опубликуйте фактические ошибки компиляции

Ответ №1:

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

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

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

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

gcc -ftrapv -Wall -Wextra # ftrapv is the key point

Ответ №2:

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

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

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

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

Это должно работать всякий 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 и определенных диапазонов).

Комментарии:

1. Что происходит, когда min == max … (и я думаю, что вам не хватает a min в вашем возвращаемом значении).

2. @caf: исправлено. Обратите внимание, что предварительные условия max > min . Я просто хочу проиллюстрировать суть, а не писать полный, проверенный фрагмент производственного кода.

Ответ №3:

Без фактического текста ошибки трудно сказать, но наличие «целочисленного переполнения» в заголовке указывает на …, ну, целочисленное переполнение 🙂

Наиболее вероятным виновником является ваш RAND_MAX 1 бит, если RAND_MAX на самом деле он такой же, как INT_MAX .

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

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

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

Ответ №4:

Это действительно может привести к переполнению целых чисел, если (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 amp; -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.)

Комментарии:

1. Вам следует включить приведение RAND_MAX , если вы используете его таким образом.