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
u 和 v 都已经标准化，如 D.1 中所述（v[1] > b / 2 和 u 为零填充）。
循环 D.3 到 D.7 的第一次迭代是空操作，因为 qhat = floor((0 * b + 2143027200) / (2254962688)) = 0 在第一个迭代。
在循环的第二次迭代中，qhat = floor((2143027200 * b + 2354839552) / (2254962688)) = 4081766758 Link.
我们不需要计算步骤 D.4 和 D.5 就可以看出为什么这是一个问题。由于qhat会在D.6中减一，算法的结果会是4081766758 - 1 = 4081766757，然而，结果应该是4081766756 Link.
我认为算法中存在错误是正确的，还是我的推理存在谬误？
附录
没有bug；您忽略了步骤 D3 中的循环：
在您的示例中，作为此测试的结果，最初设置为 4081766758 的 q̂ 的值减少了两次，首先是 4081766757，然后是 4081766756，然后继续执行步骤 D4。
（抱歉，我没有时间做出更详细/“正确”的回答。）
您可以找到算法 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
u 和 v 都已经标准化，如 D.1 中所述（v[1] > b / 2 和 u 为零填充）。
循环 D.3 到 D.7 的第一次迭代是空操作，因为 qhat = floor((0 * b + 2143027200) / (2254962688)) = 0 在第一个迭代。
在循环的第二次迭代中，qhat = floor((2143027200 * b + 2354839552) / (2254962688)) = 4081766758 Link.
我们不需要计算步骤 D.4 和 D.5 就可以看出为什么这是一个问题。由于qhat会在D.6中减一，算法的结果会是4081766758 - 1 = 4081766757，然而，结果应该是4081766756 Link.
我认为算法中存在错误是正确的，还是我的推理存在谬误？
附录
没有bug；您忽略了步骤 D3 中的循环：
在您的示例中，作为此测试的结果，最初设置为 4081766758 的 q̂ 的值减少了两次，首先是 4081766757，然后是 4081766756，然后继续执行步骤 D4。
（抱歉，我没有时间做出更详细/“正确”的回答。）