Ошибка в glibc `div ()` коде?

Как указано в «Целочисленное деление, округление с отрицаниями в C ++«, в C до C99 (то есть в C89) и в C ++ до C ++ 11 (т.е. в C ++ 98 и C ++ 03), для вычисления целочисленного деления, где любой операнд является отрицательным знаком остатка (или эквивалентно, направление округления частного) от реализации.

Затем идет стандартная функция std::div который указан для обрезать частное к нулю (т.е. остаток имеет тот же знак, что и дивиденд (числитель)) (см., например, ответ на вопрос «какова цель библиотечной функции div ()?»).

Вот код Glibc для div() (источник) (также цитируется вПолезна ли функция div (stdlib.h)?«):

(Заметка: div_t определяется как:

typedef struct
{
int quot;
int rem;
} div_t;

— примечание конца.)

/* Return the `div_t' representation of NUMER over DENOM.  */
div_t
div (numer, denom)
int numer, denom;
{
div_t result;

result.quot = numer / denom;
result.rem = numer % denom;

/* The ANSI standard says that |QUOT| <= |NUMER / DENOM|, where
NUMER / DENOM is to be computed in infinite precision.  In
other words, we should always truncate the quotient towards
zero, never -infinity.  Machine division and remainer may
work either way when one or both of NUMER or DENOM is
negative.  If only one is negative and QUOT has been
truncated towards -infinity, REM will have the same sign as
DENOM and the opposite sign of NUMER; if both are negative
and QUOT has been truncated towards -infinity, REM will be
positive (will have the opposite sign of NUMER).  These are
considered `wrong'.  If both are NUM and DENOM are positive,
RESULT will always be positive.  This all boils down to: if
NUMER >= 0, but REM < 0, we got the wrong answer.  In that
case, to get the right answer, add 1 to QUOT and subtract
DENOM from REM.  */

if (numer >= 0 && result.rem < 0)
{
++result.quot;
result.rem -= denom;
}

return result;
}

Как вы можете видеть, после большого блока комментариев есть тест, целью которого является «исправить» результат, если встроенное деление усекается до -infinity, а не до нуля.

Теперь вопрос:

Нет ли ошибки в этом коде?

Давайте сначала рассмотрим пример вызова div(42, -5), «В математике» 42 / -5 это точно -8,4, так теоретически в C89 и C ++ 03 42 / -5 может дать либо -8 (усеченный) или -9 (этаж) в зависимости от реализации. Чтение кода:

  • Если 42 / -5 доходность -8 затем 42 % -5 доходность 2 (как 42 == -8 * -5 + 2), так что тест (42 >= 0 && 2 < 0) что не соответствует действительности, и вышеуказанная функция возвращает -8 а также 2, как и хотел;
  • Если 42 / -5 доходность -9 затем 42 % -5 доходность -3 (как 42 == -9 * -5 + -3), так что тест (42 >= 0 && -3 < 0) который является истина, поэтому вышеприведенная функция возвращает «исправленный» -9 + 1 а также -3 - -5т.е. -8 а также 2, как и хотел.

Но теперь давайте рассмотрим вызов div(-42, 5) (знаки перевернуты):

  • Если -42 / 5 доходность -8 затем -42 % 5 доходность -2 (как -42 == -8 * 5 + -2), так что тест (-42 >= 0 && -2 < 0) что не соответствует действительности, и вышеуказанная функция возвращает -8 а также -2, как и хотел;
  • Если -42 / 5 доходность -9 затем -42 % 5 доходность 3 (как -42 == -9 * 5 + 3), так что тест (-42 >= 0 && 3 < 0) который не правда! и вышеуказанная функция возвращается -9 а также 3 вместо -8 а также -2!

Комментарий в приведенном выше коде сначала кажется правильным, когда говорится, что ситуация, требующая исправления, — это когда «REM имеет противоположный знак NUMER», но затем он делает огромное упрощение «Это все сводится к: если NUMER> = 0, но REM < 0, мы получили неправильный ответ «, что мне кажется неправильным (неполным), потому что это опускает случай «если номер < 0, но REM> 0 «(-42 а также 3 в предыдущем примере).

Я с трудом могу поверить, что такая ошибка осталась бы незамеченной с 1992 или 1990 года (очевидно, кто-то пытался это исправить но это все еще кажется неправильным, потому что div(-42, 5) мог вернуться -10 а также 8) … Возможно, большинство реализаций усекалось до нуля по умолчанию (и все должны делать это, начиная с C99 и C ++ 11, поэтому проблема в последних стандартах «спорная» 1) так что ошибка не проявляется на них, но все же … Может быть, я что-то здесь упускаю?

Спасибо за любые идеи.


1 (Редактировать) Что касается «проблема спорная в C ++ 11 и C99 (и новее)»: соответственно, в этих стандартах встроенное деление требуется для усечения до нуля, поэтому нам никогда не нужно корректировать результат, но это не так это означает, что настоящая реализация сложнее, чем нужно а также излишне неэффективный? «Большой комментарий» устарел и if тест бесполезен, так разве эта часть не должна быть полностью удалена?

7

Решение

Как первоначальный автор кода, я должен сказать: вы правы. Оно сломано. У нас не было систем, которые вели себя «неправильно» для тестирования, и я, вероятно, написал вышеупомянутое слишком поздно (или рано…) в тот же день или что-то в этом роде.

Мы спасены по новым стандартам, и все это должно быть очищено, возможно, с небольшим #ifdef (и исправленный код регулировки) для предварительного C99, если необходимо.

(Также отмечу, что оригинал не имел отступов в стиле GNU :-))

5

Другие решения

Но в этом случае Numer равно -42, (так что оно отрицательно), что сделало условие ложным автоматически. На самом деле, если вы попытаетесь выполнить простой код, который содержит функцию, вы увидите (отладку) оператор if:

// false in this case, numer = -42 and result.rem = -2
if(numer >= 0 && result.rem < 0)

Здесь вы можете увидеть скомпилированный результат:введите описание ссылки здесь

Я надеюсь, что ответ правильный и поможет вам понять ошибку.

-1

По вопросам рекламы [email protected]