アルゴリズム 4.3.1D の説明は、Art of The Computer Programming Vol. この質問の付録にある D. Knuth による2 (pages 272-273)。

ステップD.6では、qhat最大で 1 だけずれていると予想されるようです。

基数が であると仮定2^32しましょう (つまり、符号なしの 32 ビット数字で作業しています)。u = [238157824, 2354839552, 2143027200, 0]してみましょうv = [3321757696, 2254962688]。この分割の期待される出力は4081766756 リンクです

uとは両方とも、 D.1vで説明されているように既に正規化されています( andはゼロで埋められています)。v[1] > b / 2u

ループD.3からD.7の最初の反復は、最初の反復であるためノーオペレーションですqhat = floor((0 * b + 2143027200) / (2254962688)) = 0。

ループの 2 回目の繰り返しでは、qhat = floor((2143027200 * b + 2354839552) / (2254962688)) = 4081766758 Link .

これが問題である理由を確認するために、ステップD.4とD.5を計算する必要はありません。D.6qhatでが 1 減るので、アルゴリズムの結果は となりますが、結果はLinkのはずです。4081766758 - 1 = 40817667574081766756

アルゴリズムにバグがあると考えるのは正しいですか、それとも私の推論に誤りがありますか?

付録