Knuth的《计算机程序设计艺术》中的算法4.3.1D存在漏洞吗？

Question

您可以在本问题的附录中找到《计算机程序设计艺术》第二卷（第272-273页）D. Knuth所述的4.3.1D算法的解释。

似乎在步骤D.6中，预计qhat最多会有一个偏差。

假设基数为2^32（即我们使用无符号32位数字），让u = [238157824，2354839552，2143027200，0]和v = [3321757696，2254962688]。这个除法的期望输出是4081766756Link。

“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” 链接。

我们不需要计算步骤D.4和D.5就能看出这是一个问题。由于在D.6中qhat将减少一，因此算法的结果将为4081766758 - 1 = 4081766757，然而，结果应该是4081766756 链接。

我认为算法中存在错误，还是我的推理有误？

- yasar

---

抱歉，以下内容并不能帮助回答问题，只是一个注释：如《计算机程序设计艺术》第1卷第2页所述，在该书中，算法被赋予字母名称，并在本节内部以该字母进行引用，但其“正确”名称包括节名称。因此，在这种情况下，您指的是“算法4.3.1D”（第2卷第272-273页）（第4章算术，第4.3节多精度算术，第4.3.1节经典算法）。 - ShreevatsaR

关于“在步骤 D.6 中，似乎预期 qhat 最多会偏差一个” — 请注意算法之前给出的段落，其中提到“此算法在步骤 D3 中使用稍微改进的 q̂ 选择，保证 q = q̂ 或 q̂ − 1”。 - ShreevatsaR

你似乎漏掉了D3的最后一部分，它涉及到"如果r̂ < b，则重复此测试"（这将确保q̂减少两次，直到达到其正确值q）。我会花点时间写出一个答案（可能不会完成，所以如果我在几个小时内没有完成，请随意自己回答）。 - ShreevatsaR

坦白说，我觉得我没有时间写一个答案。但简单来说，D3中有一个循环，你执行了0次，而不是正确的次数。 - ShreevatsaR

请将以下与编程相关的内容从英文翻译成中文。只返回翻译后的文本：（顺便说一句，这是一个很清晰明了的问题，我不知道为什么有人投票关闭它，标记为“需要详细信息或澄清”！） - ShreevatsaR

Answer 1

没有 bug；你正在忽略步骤 D3 中的循环：

在您的示例中，由于此测试的结果，q̂ 的值被降低了两次，首先降至 4081766757，然后再降至 4081766756，然后才继续进行 D4 步骤。

（抱歉我没有时间提供更详细/“正式”的答案。）

- ShreevatsaR

---

他并没有忽略这个问题，原始版本中有一个拼写错误，应该是\qhat >= b，而不是简单的\qhat = b。你复制的是另一个来源的内容。 - archgoon

啊，抱歉，我刚才在处理另一个问题，然后注意到你的版本有所不同。不幸的是，将=修正为>=并不能解决这个问题。具体来说，我正在处理990/50的第一步。5可以整除前两位数字19次（而且5已经归一化，所以D.1中的d是1）。19被减少到18（这是正确的），但是qhat仍然在技术上太大了。我已经反复阅读这一部分好几遍了，但是我无法弄清楚我理解错了什么。 - archgoon

@archgoon 这就是第一步（D1，标准化）的作用 - 在这种情况下，给定990/50，你首先在左边引入新的数字位置0，将其变为0990/50，然后开始计算：5可以整除前两个数字1次，依此类推。 - ShreevatsaR

啊，谢谢，那就是我所缺少的部分；感觉有点傻，谢谢。 :) - archgoon

@archgoon 如果这能让你感觉好一点的话，昨天我花了相当多的时间阅读前面几页的文字并试图理解它，直到今天早上醒来才恍然大悟。:-) 我认为这是Knuth写作风格中被公认的一个“问题”，他似乎以轻松对话的方式写作，但实际上每个词都经过精心选择和重要，读者不能错过任何东西。（这使得《计算机程序设计艺术》很难略读；人们永远不知道从哪里开始阅读。） - ShreevatsaR