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。
(抱歉,我没有时间做出更详细/“正确”的回答。)