glibc中的`div()`代码存在缺陷吗?

8

如 "C++中带负数的整数除法舍入 "所述,在 C99 之前的 C 中(即在 C89 中)和在 C++11 之前的 C++ 中(即在 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;
}

正如您所看到的,大段注释后面有一个测试,其目的是在内置除法向负无穷截断而不是向零截断时“修正”结果。

现在问题来了:

那段代码中没有错误吗?

让我们先考虑示例调用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),这是不成立的,因此上述函数返回 -82,符合要求;
  • 如果 42 / -5 的结果是 -9,那么 42 % -5 的结果是 -3(因为 42 == -9 * -5 + -3),所以测试条件是 (42 >= 0 && -3 < 0),这是成立的,因此上述函数返回 "修正后的" -9 + 1-3 - -5,即 -82,符合要求。

现在让我们考虑调用 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),这是不正确的!上述函数返回 -93 而不是 -8-2
上面代码中的注释似乎是正确的,当它说需要纠正的情况是“REM与NUMER相反”的时候,但是它接着做出了一个“巨大的简化”:“这归结为:如果NUMER>= 0,但REM<0,则我们得到了错误的答案”,这对我来说似乎是错误(不完整),因为它省略了“如果NUMER<0,但REM>0”的情况(在前面的例子中是-42和3)。
我简直无法相信自1992年或1990年以来,这样的一个错误会一直被忽视(显然有人试图“修复”它,但似乎仍然不正确,因为div(-42, 5)可以返回-108)...可以说,大多数实现默认情况下都是向零截断的(并且所有实现都从C99和C++11开始要求这样做,所以在最新的标准中问题是“无关紧要的”1),因此这个错误不会在它们上面表现出来,但是...也许我错过了什么?谢谢你提供任何见解。

1 (编辑) 关于"C++11和C99(及更高版本)中的问题不再存在": 因此,在这些标准中,内置除法操作需要向零截断,因此我们永远不需要调整结果,但是这是否意味着当前的实现比所需更加复杂和低效?"大注释"已经过时,if测试也无用,所以该部分是否应完全删除?


取模运算符在有符号操作数下的实现依赖于具体情况。我认为这是问题的主要关键点。 - Jiminion
@Jim div 的目的正是为了封装依赖于实现的操作,以给出独立于实现的结果。@ouah 你的链接与我问题中的最后一个链接相同(http://minilib-c.googlecode.com/svn-history/r2/trunk/stdlib/div.c),并且如我所说,对于 num == -42denom == 5,如果你得到 r.quot = -9r.rem = 3,新的“修正” --r.quot r.rem += 5 将会给出 r.quot == -10r.rem == 8(而不是 r.quot == -8r.rem == -2)... - gx_
我认为他们从另一个角度看待了这个问题。他们精确地定义了div与%有关,而他们也承认这是依赖于实现的。(为什么要使用混合符号运算符进行模运算呢?我认为这不是一个经常涉及的领域,所以对一致性的担忧很少。) - Jiminion
@ouah 是的,至少它试图处理它 :) 添加的更正似乎更针对“-42/-5”,这可能会给出“9”和“3”,而不是欧几里得除法中的“8”和“-2”(但这几乎像是想象“42/5”会给出“9”和“-3”,而不是“8”和“2”(这在标准中是被禁止的))。 - gx_
2个回答

7
作为代码的原始作者,我必须承认:你是对的,它已经出现了问题。我们没有系统来测试“错误”的行为,我可能在一天的太晚(或者太早)才写了上面的内容。
我们可以通过新标准来解决这个问题,并且整个代码应该被清理掉,也许需要为pre-C99添加一个小的#ifdef(和修正的调整代码)。
(另外,我要注意的是,原始代码没有使用GNU风格的缩进 :-) )

Chris Torek!这就是你!非常感谢你的回答!我真的找不到比你更好的来源了 :) (至于缩进,也许原始代码更接近于这个div.c?)(此外,在此期间,我进行了更多的网络搜索,并发现了另一个“修复”(XOR似乎是合法的,但调整错误),特别是**1987年的代码**(!)它似乎可以正确处理42/-5和-42/5!) - gx_
2
是的,基本上这就是原始版本(K&R风格,“高Bosticity”缩进 :-) ...最终成为FreeBSD中style(9)的样式)。我以前从未见过Sprite版本,也没有见过Vrije Universiteit版本。使用普通(有符号)int进行异或运算似乎很冒险。static方法是有效的,但在所有情况下,需要运行时测试似乎有些混乱。即使我们不能依赖C99,也最好有一个特定于编译器的#define来描述整数除法行为,因为许多机器“按照C99的要求运行”。 - torek
确实。**我已经提交了glibc错误报告。(顺便说一下,自由大学的那个报告很接近,但是在一个总是向负无穷方向取整的机器上,div(-10, 5)会产生{-2, 0},但是这将被错误地“纠正”为{-1, -5}...) - gx_

0

有理由说明为什么它不能是实现定义的,以及必须是什么。

TLDR:余数符号必须与除法符号相匹配。

原因:
当恢复被除数时,知道除法结果、余数和除数,余数必须与除数-商的乘积相加。如果余数标志是实现特定的,那么将其求和的操作也应该是实现特定的,不是吗?或者至少有一段代码,在除法后,如果余数不正确,则会修复余数符号。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接