Knuth算法D（TAOCP 4.3.1）归一化步骤是否存在Bug？

核心问题分析 #

你遇到的溢出情况，既不是对D1步骤的误解，也不是(b-1)//v_hi公式的疏漏——而是忽略了该公式的适用前提：算法D处理的是(n+1)-limb被除数除以n-limb除数的场景，归一化时允许除数v乘d后变成(n+1)-limb（对应被除数u乘d后变成(n+2)-limb），后续算法会适配这个长度变化。你的例子中b=10、v=19（2-limb），按公式得到d=9后v*d=171（3-limb），这其实符合算法设计的预期，并非“错误溢出”。

但如果你的场景要求v乘d后保持原limb数不变，就需要调整d的计算逻辑。

正确的d推导（保持limb数不变的场景） #

若要保证v*d仍为n-limb数（即v*d < b^n），同时满足归一化要求(v*d)_hi >= b//2，d的推导需满足两个约束：

1. 上限约束：d <= floor( (b^n - 1) / v )，确保v*d不溢出n-limb；
2. 下限约束：d >= ceil( (b//2) / (v_hi + 1) )，因为(v*d)_hi = d*v_hi + floor(d*v_lo / b)，最坏情况下floor(d*v_lo / b) <= d-1，因此d*v_hi + d-1 >= b//2 → d >= ceil( (b//2) / (v_hi + 1) )。

以你的例子（b=10，n=2，v=19，v_hi=1，b//2=5）为例：

• 上限：floor( (100-1)/19 ) = 5；
• 下限：ceil(5/(1+1))=3；
  所以d可选3、4、5，对应的v*d分别为57、76、95，均为2-limb，且高位分别为5、7、9，都满足>=5的要求。

无CLZ指令下的d计算方案 #

如果无法用CLZ指令快速找2的幂次d，推荐用以下简化逻辑：

1. 先计算d_candidate = (b//2 + v_hi - 1) // v_hi（即ceil( (b//2)/v_hi )）；
2. 检查d_candidate * v < b^n：
   • 若满足，直接用d_candidate；
   • 若不满足，将d_candidate减1，重复检查直到满足约束；
     这个逻辑无需大查找表，仅需几次乘法和比较，成本极低。

比如你的例子：

• d_candidate = (5+1-1)//1=5；
• 5*19=95 <100，满足，直接用d=5即可。

内容的提问来源于stack exchange，提问作者Duncan Townsend