Knuth 算法 D (TAOCP 4.3.1) 标准化步骤中存在错误？

Question

Knuth 算法 D，在标准化步骤 (D1) 期间，规定将 d 设置为

(b-1)//v_hi

，其中

b

是基础（字大小或半字大小），

v_hi

是分母的上半部分。然后将分母乘以d，得到一个相同大小的多肢整数。

Knuth 算法 D 步骤 D1 (TAOCP 4.3.1)

问题是乘以 d NOT 不会给出相同大小的多肢整数。有时会溢出。例如，当 b 为 10，v 为 19 时，我们得到 d 为 9，v 的新值为 171，这显然溢出了 2 个肢体。

我是否误解了步骤 D1 的文字，或者将 d 设置为

(b-1)//v_hi

的处方是否略有错误？ d 的正确表述是什么？

步骤 D1 的后半部分指出“在二进制计算机上，最好选择 d 作为 2 的幂，而不是使用此处建议的值”。不幸的是，我正在一个没有

clz

指令的平台上工作，并且模拟它的成本非常昂贵。使用简单的截断除法来计算 d 会更快。

最终，我只需要计算 v 的乘数即可给出条件

v_hi >= b//2

。同样不幸的是，这个平台上的查找表太大了。

也许更新版本的 TAOCP 可以解决这个问题，但我现在没有看书。

Answer 1

是的，我同意你的观点，有一些棘手的极端情况会溢出。 我遇到了同样的错误，在 32 位架构上工作，一个反例是

v = (1, 2)

（即

v = 2^32 + 2

、

v_1 = 1

、

v_0

= 2），标准化步骤 D1 计算

d = floor((b-1)/v_1)

即

0xffffffff

与

b = 2^32

。但随后

d * v = (2^32-1) * (2^32 + 2) = 2^64 + 2^32 - 2 = (1, 0, 0xfffffffe)

出现溢出。

d = ceil(((b/2)/v_1))

有用吗？