Knuth的TAOCP算法4.3.1D有缺陷吗？

Question

你可以找到算法4.3.1D的解释，如D. Knuth在本问题附录中所著的“计算机编程艺术”第2卷(第272-273页)所示。

看来，在D.6这一步中，预计qhat最多只会减少一个。

让我们假设基是2^32 (也就是说，我们使用的是无符号32位数字)。让u = [238157824, 2354839552, 2143027200, 0]和v = [3321757696, 2254962688]。这个部门的预期产量是4081766756 链接。

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

循环D.3通过D.7的第一次迭代不是op，因为第一次迭代中的qhat = floor((0 * b + 2143027200) / (2254962688)) = 0。

在循环的第二次迭代中，qhat = floor((2143027200 * b + 2354839552) / (2254962688)) = 4081766758 链接。

我们不需要计算步骤D.4和D.5来了解为什么这是一个问题。由于qhat在D.6中会减少1，所以算法的结果将是4081766758 - 1 = 4081766757，但是结果应该是4081766756 链接。

我认为算法中有错误，或者我的推理有谬误，这是正确的吗？

附录

​

​

Answer 1

没有bug；您忽略了步骤D3中的循环：

​

​

在您的示例中，由于这个测试的结果，q̂的值(最初设置为4081766758 )在开始步骤̂之前下降了两倍，第一次降到4081766757，然后下降到4081766756。

(对不起，我没有时间做一个更详细的/“正确的”回答。)