Knuth 的 TAOCP 算法 4.3.1D 中是否存在错误?

Is there a bug in Algorithm 4.3.1D of Knuth's TAOCP?

您可以找到算法 4.3.1D 的解释,因为它出现在 Art of The Computer Programming Vol. 书中。 2(第 272-273 页)作者 D. Knuth 在此问题的附录中。

看来,在步骤D.6中,qhat预计最多会差一个。

让我们假设基数是 2^32(即我们正在使用无符号的 32 位数字)。让u = [238157824, 2354839552, 2143027200, 0]v = [3321757696, 2254962688]。该部门的预期输出是 4081766756 Link

uv 都已经标准化,如 D.1 中所述(v[1] > b / 2u 为零填充)。

循环 D.3D.7 的第一次迭代是空操作,因为 qhat = floor((0 * b + 2143027200) / (2254962688)) = 0 在第一个迭代。

在循环的第二次迭代中,qhat = floor((2143027200 * b + 2354839552) / (2254962688)) = 4081766758 Link.

我们不需要计算步骤 D.4D.5 就可以看出为什么这是一个问题。由于qhat会在D.6中减一,算法的结果会是4081766758 - 1 = 4081766757,然而,结果应该是4081766756 Link.

我认为算法中存在错误是正确的,还是我的推理存在谬误?

附录

没有bug;您忽略了步骤 D3 中的循环:

在您的示例中,作为此测试的结果,最初设置为 4081766758 的 q̂ 的值减少了两次,首先是 4081766757,然后是 4081766756,然后继续执行步骤 D4。

(抱歉,我没有时间做出更详细/“正确”的回答。)