HN 日本語サマリー

← 一覧へ戻る
プログラミング

クヌースの筆算(TAOCP Vol II, Algorithm 4.3.1D)における数十年前のバグ

A decades-old bug in Knuth's long division (TAOCP Vol II, Algorithm 4.3.1D) (kolja.rs)

163 pointsby nk_kolja38 コメント

要約

この記事は、ドナルド・クヌースの『The Art of Computer Programming』に掲載されている筆算アルゴリズム(Algorithm 4.3.1D)に、数十年前から存在するバグを発見した経緯を綴っています。筆者は、アルゴリズムの正当性を支える定理の証明に疑問を持ち、自身で証明を試みた結果、アルゴリズムが長年見過ごされてきた反例を発見しました。この発見により、筆者自身にちなんだアルゴリズムの正当性に関する定理が生まれ、さらにLLVMの実装における「バグ」についても言及しています。

全文翻訳

長除算の物語

2026年8月13日

クヌースの「The Art of Computer Programming」で数十年前のバグを発見した後、定理を受け取るまで

私はクヌースの「The Art of Computer Programming」で有名な長除算アルゴリズム、Algorithm Dを実装していて、どうしても見過ごせない問題に遭遇しました。アルゴリズムの正しさは定理Bに依存していましたが、その証明が私を悩ませました。それは不自然に感じられ、単純な命題を証明するために非常に複雑な経路をたどり、問題とは無関係に見える、コーナーケースではない特別なケースを孤立させていました。何かがおかしいと感じたので、自分で定理を証明しようとしましたが、失敗しました。しかし、その失敗は、数十年間正しいとされてきたAlgorithm Dの反例と、私の名前を冠したアルゴリズムの正当性に関する定理をもたらしました。

[画像: 定理B(N. Kaluđerović, 2026)、TAOCPの誤植集に追加]

この記事では、背景を説明し、長除算を(必要とする人のために)ゼロから解説し、バグがどのように発生し、なぜ長年隠されていたのかについての私の考えを共有し、最後に長除算を実装するより現代的な方法のプレビューで締めくくります。この記事を書く過程で、llvmにおけるこのアルゴリズムの実装にも「バグ」を見つけたので、それについても詳しく説明します。バグだけに関心がある場合は、バグに直接ジャンプできます。

目次

私がここにたどり着くまで

インタビューの準備として、小さなプロジェクトを行うことにしました。それは、素体上の算術演算のための小さなライブラリを構築することでした。これには、固定サイズの多倍長整数、算術演算、いくつかの体演算、定数時間、定数メモリアクセスが含まれており、現代の暗号プロトコルの出発点となります。

実装を進めるにつれて、そのプロセスは一つのルールを持つゲームに変わりました。それは、あらゆるコストを払ってでも除算を避けることです。ほとんどのことは除算なしで達成できますし、私の知る限り、暗号ライブラリは実行時に除算命令を実行しません。除算が必要な場合は、通常、乗算と少々のシャッフリングで置き換えられます。1

なぜ私たちは除算を避けるためにこれほど手間をかけるのでしょうか?乗算は非常に単純で、自然数の公理と考えることさえできます。除算ははるかに複雑です。まず、どこでも定義されているわけではありません。ゼロで割ることはできません。しかし、5を2で割ることもできません!実際には、「剰余を伴う除算」という、より複雑な操作があり、2つの結果を返します。それは商と剰余、つまり被除数と除数の倍数の最小非負差です。「最小」が正確に何を意味するのか、なぜこの特定の定義を選ぶのか、そしてなぜ「サイズ」という概念がそもそも問題になるのか、という点に問題が潜んでいます。異なる選択をすることもできます。例えば、ゼロ中心の剰余です。しかし、さらに進んで、異なるサイズ関数を選択することもでき、それはまったく異なる除算アルゴリズムを生み出します。2

これらすべてを念頭に置くと、理論的な複雑さが実践に転移するのも不思議ではありません。乗算命令は、現代のマシンでは1〜2サイクルでパイプライン化されますが、除算は最大20サイクルかかることがあり、通常はパイプライン化されません。

最終的に、多倍長実装に残された唯一のギャップは、多倍長除算アルゴリズムでした。そこで、私は当然のことをして、長除算の実装に取り掛かりました。参考資料として、ドナルド・クヌースの「The Art of Computer Programming」第II巻、第3版、アルゴリズム4.3.1Dを使用しました。

長除算が実際にどのように機能するかを見てみましょう。

長除算をゼロから学ぶ

ハードウェアにおける多倍長整数

暗号用の整数は数百または数千ビットに達するため、単一レジスタをはるかに超えます。そのため、それらを基数bで、1つの肢(limb)をマシンワードとして格納します。x = (x_{n-1}, …, x_0)b = ∑{i=0}^{n-1} x_i b^i、ここで 0 ≤ x_i < b です。

多倍長算術アルゴリズムの主な構成要素は、単一/倍精度肢で動作する4つの原始的な命令です。

addc:  x, y          ->  s, carry     # s = (x+y) mod b,   carry  = 1 iff overflow
subc:  x, y          ->  d, borrow    # d = (x−y) mod b,   borrow = 1 iff underflow
mul:   x, y          ->  (hi, lo)     # x·y = hi·b + lo
div:   (hi, lo), y   ->  (q1, q0), r  # hi·b + lo = q·y + r,  0 ≤ r < y,  q = q1·b + q0

最初の3つは特筆すべきことではありませんが、除算は異質です。2つの単一肢乗数同士の乗算は常に2つの肢の積を返しますが、2つの肢の被除数と1つの肢の除数による商は、常に単一の肢に収まるとは限りません。そのため、2つの肢の商を使用します。さらに、剰余が必要な副産物として現れます。ゼロ除算では、未定義の動作を仮定します。つまり、qとrは任意の値を取り得ますが、一部のアーキテクチャはこのケースを異なる方法で扱います。

長除算を中規模除算に還元する

私たちのタスクは、多倍長整数uをvで割ることです。つまり、u = q·v + r かつ 0 ≤ r < v となる整数qとrを見つけることです。一般性を失わないように、除数vが非ゼロの最上位肢v_{n-1}を持つn肢の整数であると仮定し、被除数uを先頭にゼロをパディングしてvよりも厳密に多くの肢を持つようにします。uの肢の数をn+m+1とします。

次に、後続の処理で自然になる別の要件があります。uの最上位n肢をn肢の整数として読んだとき、vよりも厳密に小さくなければなりません。

(u_{n+m}, …, u_{m+1})b < (v{n-1}, …, v_0)_b、等価的に ⌊u/b^{m+1}⌋ < v。

これがまだ満たされていない場合は、uにさらにゼロを追加することで保証できます。この仮定は、商のサイズをm+1肢に固定します。

⌊u/b^{m+1}⌋ < v ⟺ u < v b^{m+1} ⟺ q = ⌊u/v⌋ < b^{m+1}。

パディングが完了すると、すべてのオペランドは固定された形状を持ちます。qとrをuをvで割ったときの商と剰余とすると、次のようになります。

u = (u_{n+m}, u_{n+m-1}, ..., u_0)_b
v = (v_{n-1}, v_{n-2},   ..., v_0)_b    0 < v_{n-1}
q = (q_{m},   q_{m-1},   ..., q_0)_b    u = q·v + r
r = (r_{n-1}, r_{n-2},   ..., r_0)_b    0 ≤ r < v

この説明では、3つの異なる除算アルゴリズムを3つのレベルで使用します。私たちが望むのは、n+m+1肢対n肢、つまり「長」n+m+1/n 除算です。私たちが持っているのは、「短」2/1 除算命令です。それらを橋渡しするために、「中」n+1/n 除算を使用します。

qの肢を計算する自然な方法は、上から下へ進むことです。3 最上位の肢は次のようになります。

q_m = ⌊⌊u/v⌋ / b^m⌋ = ⌊(u_{n+m}, ..., u_m)_b / v⌋。

分子 ⌊u/b^m⌋ は単純にuの最上位n+1肢であり、したがって商q_mの最上位肢はn+1/n除算の商そのものです。そして、uの最上位n肢がvより小さいという仮定により、それは単一の肢に収まります。

(u_{n+m}, ..., u_{m+1})b < v ⟺ (u{n+m}, ..., u_m)_b < v b

したがって、q_m = ⌊(u_{n+m}, ..., u_m)_b / v⌋ < b となります。q_mを計算した後、uからvのb^k倍を減算し、更新されたuでアルゴリズムを続行します。このuの更新操作は、uの最上位n+1肢をR_m(q_mに対応する剰余)に置き換えることに相当します。これはn肢に収まることがわかっています。したがって、更新されたuは1肢少なくなり、残りのm肢のqを計算するためにアルゴリズムを続行します。この折りたたみ技術が正しい答えを計算することが容易にわからないかもしれませんが、次のアルゴリズムを観察し、ループの各エントリとエグジットで2つの不変条件が満たされていることに注意することで、容易に推測できます。

アルゴリズム 1: 長除算
入力:
        u = (u_{n+m}, ..., u_0)_b,  最上位n肢 < v となるようにパディング済み
        v = (v_{n-1}, ..., v_0)_b,  v_{n-1} > 0
開始:
        r = u,  q = 0                         # r は u として開始し、最終的な剰余に縮小する
ループ:
        for k = m down to 0:
            u' = (r_{k+n}, ..., r_k)_b        # k番目の位置にある r の最上位 n+1 肢
            (q_k, R_k) = ⌊u'/v⌋, u' mod v     # n+1/n 除算
            q += q_k·b^k                      # 商のk番目の肢
            r -= q_k·v·b^k                    # (r_{k+n},...,r_k) を (0, R_k) に置き換える
戻り値: (q, r)
不変条件:
        1. u = q·v + r
        2. r の最上位 n 肢 < v               # 肢 k+1 から n+k まで

k=0 まで不変条件2を実行すると r < v となり、ペア (q,r) は正確に商と剰余になります。

長除算の例は、既に示されているように、初期化されたuです。各イテレーション:rの強調表示された上位4ワードをv=314(商の数字をqへ)で割ります。それらを314で割った剰余をr_k(r3,r2,r1,r0)として取得します。rのそれらのワードをクリアし、r_kをrの上に移動します。4ステップ後、q=5599、r=207です。長除算の例 urvqrkr3r2r1r031455991758293/%/%/%/%183813202307b = 10

ステップ 1 / 15

次へ / 前へ をクリックするか、← → を使用します。再生 は全ステップを実行します。Space キーで切り替えます。

したがって、n+m+1/n の長除算は、m+1回の中規模 n+1/n 除算を要し、各商の肢ごとに1回実行されます。

中規模除算を小規模除算に還元する

前のセクションでは、中規模除算が残りました。

u = (u_n, u_{n-1}, ..., u_0)_b,
v = (v_{n-1},      ..., v_0)_b,
⌊u/b⌋ < v          # ゆえに q < b

uによるuの除算は、商 0 ≤ q = ⌊u/v⌋ < b と剰余 0 ≤ r < v を返します。

自然なステップは、最上位肢の2/1除算によってn+1/n除算を近似することです。これはdiv命令で計算できます。パラメータを次のように書き換えます。

u = u''·b^{n-1} + u'      u'' = (u_n, u_{n-1})_b     0 ≤ u'' < b²,    0 ≤ u' < b^{n-1},
v = v''·b^{n-1} + v'      v'' = v_{n-1}              0 < v'' < b,     0 ≤ v' < b^{n-1},

そして、単一のdiv((u_n, u_{n-1}), v_{n-1})で計算される q̂ = ⌊u''/v″⌋ を設定します。q^は、その命令の完全な2肢の商(q1, q0)_bです。私たちの制約はuをv·bに対して制限しますが、u″をv″·bに対して制限するわけではないため、q^が単一の肢を超えるのを妨げるものはありません。

q^はどれほど良い推測でしょうか?ひどく超えることはありますか?下回ることはありますか?以下の両方の定理は、床関数に関する単純な事実に基づいています。d = ⌊m/n⌋ の場合、dn ≤ m ≤ (d+1)n - 1 です。

定理A (q ≤ q^): アンダーシュートなし

q ≤ u/v ≤ u″b^{n-1} + u′/v″b^{n-1} < (u″+1)b^{n-1}/v″ ≤ q^+1。

2番目のステップは v ≥ v″b^{n-1} を使用し、3番目は u′ ≤ b^{n-1} - 1 を使用し、最後は床関数、u″+1 ≤ (q^+1)v″ の形式です。q < q^+1 であり、両方とも整数なので、q ≤ q^ です。

定理B' (q^ < q+1 + b/v″): オーバーシュートの境界

q^ ≤ u″/v″ = u″b^{n-1}/v″b^{n-1} ≤ (u/v)v″b^{n-1} < (q+1)v^{-1}v″b^{n-1} < q+1 + bv″。

3番目のステップは q = ⌊u/v⌋ の床関数です。最後のステップは v = v″b^{n-1} + v′ を展開し、v′ ≤ b^{n-1} - 1 および q+1 ≤ b を使用します。

これらを合わせると、次の境界が得られます。q ≤ q^ < q+1 + b/v″。v″が小さい場合、この境界はあまり良くありません。v″=1の場合、推測は最大bだけオーバーシュートする可能性があります。しかし、短い迂回路を取ることでv″を制御できます。

正規化

両方のオペランドが同じ係数でスケーリングされる場合、商は変更されません。q = ⌊u/v⌋ = ⌊uf/vf⌋。したがって、v″を大きくする係数fを探します。f = ⌊b/(v″+1)⌋ の選択がうまくいきます。分母vfは依然としてn肢に収まり、分子ufはn+1肢に収まります。vfをvと再命名した後、新しい最上位肢は v″ ≥ ⌊b/2⌋ を満たします。5 このようなvを正規化と呼びます。実際には、fは2のべき乗として取られるため、両方のスケーリングは単純なシフトです。

剰余もスケーリングされることに注意してください。rf = uf mod vf の場合、rf = r·f となるため、長除算全体が商qと剰余rfで終了すると、真の剰余は r = rf/f となります。これは正確な単一肢による除算で計算できます。これは別のレベルの再帰を追加します。つまり、別の、ただし小さい、長除算です。しかし、n=1の場合、近似商q^は実際には正確です(そしてfが2のべき乗の場合、除算は単なるシフトなので、このステップは自明です)。正規化は、長除算全体に対して(中規模ステップごとに1回ではなく)一度だけ、最初に行われます。

v″ ≥ ⌊b/2⌋ とすると、定理B'は次のようになります。

定理B ( q^ ≤ q+3 ):

q^ < q+1 + bv″ ≤ q+1 + b/⌊b/2⌋ ≤ q+4、

そしてq^, qは整数なので、q^ ≤ q+3 です。6

これはn+1/n除算にどのように役立つでしょうか?手順は次のとおりです。q^を計算し、u - q^·vを形成して推測をテストします。これは2つの定理により [−3v, v) の範囲にあります。具体的には、1回の2 x n多倍長乗算と1回の多倍長減算を計算します。減算がアンダーフローした場合、vを戻してq^を1減らします。結果が非負になるまで、最大3回修正を繰り返します。その時点で q^ = q となり、uに残ったものが剰余です。

アルゴリズム 2: 中規模除算
入力:
        u = (u_n, u_{n-1}, ..., u_0)_b,  ⌊u/b⌋ < v          # ゆえに q < b
        v = (v_{n-1},      ..., v_0)_b,  v_{n-1} ≥ ⌊b/2⌋    # 正規化済み
試行:
        (q̂, r̂) = div((u_n, u_{n-1}), v_{n-1})      # 単一の 2/1 除算; q̂ は2肢
修正:
        r = u - q̂·v                                # 単一の 2xn 乗算、単一の mp 減算
補正:
        if r < 0:  q̂ -= 1, r += v                  # アンダーフロー -> 1回目の mp 加算補正
        if r < 0:  q̂ -= 1, r += v                  # アンダーフロー -> 2回目の mp 加算補正
        if r < 0:  q̂ -= 1, r += v                  # アンダーフロー -> 3回目の mp 加算補正
戻り値: (q̂, r)                                     # (q̂, r) = (q, r)、定理Bにより正しい(?)
不変条件:
        u = q̂·v + r                                # 各行の後で保持される

(n+1)/n 除算 3129 / 314 q̂·v v r̂ u r q̂ q 3 1 4 b = 10 3 1 4 0 3 9 0 1 9 3 2 8 0 9 9 3 / 1 0 % 1 × − 0 − 1 − 1 − 1 borrow = 0 ? q̂ -= 1 0 9 + 1 + 1 + 1 + 0 borrow = 0 ? ✓

ステップ 1 / 17

次へ / 前へ をクリックするか、← → を使用します。再生 は全ステップを実行します。Space キーで切り替えます。

バグ

Algorithm DのステップD3で、クヌースは修正段階の前に試行商を改善する方法を提案しています。q^ = q を正確に得ることはできなくても、さらに1肢の被除数と除数を読み取ることで、ギャップを狭めることができます。クヌースのステップの利点は二重です。

  • 第一に、q^ は q^ ≤ q+1 の境界に絞り込まれます。これは、アルゴリズム2の補正ステップでの修正回数が最大1回で済むことを意味し、最大3回から減少します。
  • 第二に、クヌースは、試行商q^がD3ステップの終了時に単一の肢に収まると主張しています。つまり、後続の乗算q^·vは単一肢の数による乗算です。これにより、2×n乗算ではなく1×n乗算を実行するため、さらなるパフォーマンス向上が実現します。

これらの改善は、クヌースのアルゴリズムDのステップD3(「試行」)とD4(「修正」)で表現されています。

TAOCP Vol. 2, §4.3.1, Algorithm D, steps D3-D4 (pp. 272–273)。インデックスはn+1/n除算に対応するように変更されています。

D3. [q̂を計算する。] q̂ ← ⌊(uₙb + uₙ₋₁)/vₙ₋₁⌋ とし、r̂を剰余 (uₙb + uₙ₋₁) mod vₙ₋₁ とする。次に、q̂ ≥ b または q̂·vₙ₋₂ > b·r̂ + uₙ₋₂ かどうかをテストする。もしそうなら、q̂を1減らし、r̂にvₙ₋₁を加え、r̂ < b ならこのテストを繰り返す。(vₙ₋₂に対するテストは、試行値q̂が1だけ大きいほとんどの場合を高速に決定し、q̂が2だけ大きいすべてのケースを排除する。演習19、20、21を参照。)

D4. [乗算と減算。] (uₙ, uₙ₋₁, ..., u₀)b を (uₙ, uₙ₋₁, ..., u₀)b − q̂·(0, vₙ₋₁, ..., v₁, v₀)b に置き換える。この計算(アルゴリズムMのステップM3、M4、M5に類似)は、単一桁の数による単純な乗算と減算からなる。数字 (uₙ, uₙ₋₁, ..., u₀) は正に保たれるべきである。もしこのステップの結果が実際には負であれば、(uₙ, uₙ₋₁, ..., u₀)b は真の値に bⁿ⁺¹ を加えたもの、すなわち真の値のbの補数として残され、左側に「借り」が記憶される。

アルゴリズム 3: 中規模除算、クヌース
入力:
        u = (u_n, u_{n-1}, ..., u_0)_b,  ⌊u/b⌋ < v          # ゆえに q < b
        v = (v_{n-1},      ..., v_0)_b,  v_{n-1} ≥ ⌊b/2⌋    # 正規化済み
D3:
        (q̂, r̂) = div((u_n, u_{n-1}), v_{n-1})          # 単一の 2/1 除算; q̂ は2肢
        if q̂ ≥ b or q̂·v_{n-2} > b·r̂ + u_{n-2}:
            q̂ -= 1;  r̂ += v_{n-1};
        if (r̂ < b) and (q̂ ≥ b or q̂·v_{n-2} > b·r̂ + u_{n-2}):
            q̂ -= 1;  r̂ += v_{n-1};
D4:                                                    # q̂ は1肢に減少
        r = u - q̂·v                                    # 単一の 1xn 乗算、単一の mp 減算
D5:
        if r < 0:  q̂ -= 1, r += v                      # アンダーフロー -> 1回目の mp 加算補正
戻り値: (q̂, r)                                         # (q̂, r) = (q, r)、定理Bにより正しい(?)
不変条件:
        u = q̂·v + r                                    # 各行の後で保持される

クヌースの試行商近似の例を以下に示します。

アルゴリズムD(クヌース) 3129 / 314 q̂·v v r̂ u r q̂ q 3 1 4 b = 10 3 0 1 3 2 0 9 3 2 8 2 6 / 1 0 % 1 0 q̂ ≥ b ? ✓ q̂ −= 1 r̂ += v_{n-1} 0 9 4 r̂ < b ? ✓ q̂ ≥ b ? ✗ q̂·v_{n-2} > b·r̂ + u_{n-2} ? ✗ × − 0 − 0 − 1 − 0 borrow = 0 ? ✓

ステップ 1 / 16

次へ / 前へ をクリックするか、← → を使用します。再生 は全ステップを実行します。Space キーで切り替えます。

注意深い読者は、アルゴリズム3に問題があることに気づくでしょう。定理Bでは、q^ ≤ q+3 という境界がありましたが、ステップD3では最大2回の修正が行われ、その後q^が単一の肢に収まることを期待しています。最悪の場合、q = b-1 かつ q^ = q+3 = b+2 となると、2回の修正ではq^を単一の肢に押し込むのに十分ではないため、2番目のプロパティに違反します。このケースは実際に発生するのでしょうか、それとも定理Bの境界はタイトではないのでしょうか?

実際、アルゴリズムDが間違った答えを返すケースが存在し、その正確な設定はかなり奇妙です。アルゴリズムDが失敗する最小の例は次のとおりです。

b = 3
u = (1,2,0,0)₃ = 45        q = ⌊45/16⌋ = 2
v =   (1,2,1)₃ = 16        q̂ = ⌊(1,2)₃/(1)₃⌋ = ⌊5/1⌋ = 5 = q + 3 = (1,2)₃

D3ステップでq^を2回修正した後も、q^は依然として2肢の値 q^ = (1,0)₃ となります。そこから、1×n乗算はq^の最下位肢のみを見てゼロで乗算し、何も減算しないため、エラーが伝播します。

以下のアニメーションは、誤った除算を示しています。

基数3でのアルゴリズムD 3129 / 314 u v q q̂ r̂ 2 1 2 0 0 1 2 1 b = 3 1 2 1 0 0 0 1 2 / % q̂ ≥ b ? ✓ q̂ −= 1 r̂ += v_{n-1} r̂ < b ? ✓ q̂ ≥ b ? ✓ q̂ −= 1 r̂ += v_{n-1}

ステップ 1 / 9

次へ / 前へ をクリックするか、← → を使用します。再生 は全ステップを実行します。Space キーで切り替えます。

何十年も隠されていた理由

TAOCPの第4.3.1章をさらに読み進めると、驚くべきことに、クヌースがMIX7アセンブリで書いたAlgorithm Dの実装であるProgram Dには、このエラーが見られないことがわかります。プログラムは確かに正しいのですが、アルゴリズムが間違っており、この違いの背後にはバグの正確な理由があります。

注意深い読者は、私が導入した除算命令の定義が唯一のものではないことに気づいたかもしれません。実際、(≥)2つの方法で除算命令を実装できます。これは、商が単一の肢に収まらない場合に何が起こるかという問題によって分けられます。

div_arm: (hi, lo), (y) -> (q1, q0), r
div_x86: (hi, lo), (y) ->     (q0), r, F

前者は完全な2肢の商を返し、ゼロ除算を未定義のままにします。8 これはARMでの除算の単純化であり、__udivti3が128ビット整数に対して計算するものに似ています。9

後者は単一肢の商を返し、商のオーバーフローまたはゼロ除算の場合にフラグを立てます。これはx86での除算の単純化です。10 これはクヌースのMIXマシンで使用される除算命令です。

2つのアプローチは、2つの異なる試行商を生成します。

q^arm = ⌊(uₙb + uₙ₋₁)/vₙ₋₁⌋, q^x86 = min{q^arm, b-1}。

TAOCPの第1版と第2版では、Algorithm Dは飽和した商q^x86を使用しました。これはMIX自身のdiv命令と一致していました。その量に対して、書籍の定理は真実です。

TAOCP Vol. 2, 第2版, §4.3.1, 定理AおよびB (pp. 256–257)。説明のために整理された定理:

定理AおよびB: v_{n-1} ≥ ⌊b/2⌋ ならば q ≤ q^x86 ≤ q+2。

ステップD3は次のように記述されていました。11

D3. [q̂を計算する。] uₙ = vₙ₋₁ ならば、q̂ ← b-1 とし、そうでなければ q̂ ← ⌊(uₙb + uₙ₋₁)/vₙ₋₁⌋ とする。次に、q̂·vₙ₋₂ > (uₙb + uₙ₋₁ − q̂·vₙ₋₁)·b + uₙ₋₂ かどうかをテストする。もしそうなら、q̂を1減らし、このテストを繰り返す。(後者のテストは、試行値q̂が1だけ大きいほとんどの場合を高速に決定し、q̂が2だけ大きいすべてのケースを排除する。演習19、20、21を参照。)

記述されている通り、定理とAlgorithm Dの両方が正しかったのです。

90年代にクヌースは、MIXに代わるより現代的な抽象マシン、MMIX12を導入しました。この導入に伴い、TAOCPの元の本は改訂されました。とりわけ、表記法が変更され、インデックスがリトルエンディアンの0から始まるように書き直され、必要に応じてアルゴリズムがMMIXに合わせて調整されました(ただし、最初の3巻の印刷されたプログラムは依然としてMIXで書かれています)。

Algorithm Dへの主な変更は、1995年9月28日に行われました。これはクヌースの誤植集で見ることができます。

[画像: step_d3_errata]

1995年の変更により、q^x86試行商がq^armに置き換えられましたが、定理A およびBはそれに合わせて調整されませんでした。それらはq^x86の境界のみを証明していました。ほとんどの入力では問題ありませんでしたが、退化したケースq^arm ≥ bでは、q^arm - q のギャップは技術的には無制限でした。更新された定理Bは、ダメージはそれほど深刻ではないことを示しています。境界はq^arm = q+3 = b+2の場合にのみ失敗し、これはbが奇数の場合にのみ発生し、v_{n-1} = (b-1)/2、u_n = (b-1)/2、u_{n-1} = b-1 となります。

悪用される可能性はあるか

Setun13を使用していない限り、実際にはありません。エラーには奇数基数が必要なため、b=2^64、またはとにかく非常に偶数のbを使用する現代のマシンでは発生しません。MIXの汎用bもMMIXの固定b=2^64に取って代わられました。したがって、修正はアルゴリズムの完全な証明に必要でしたが、実際には依然として正しく機能していました。

奇数肢がどこで発生する可能性があるでしょうか?奇数サイズの肢で整数を格納するシステムについては知りません。

考えられる用途の一つは、p進数です。非ゼロのp進数xは通常、ペアx = u p^e として表されます。ここで、e ∈ ℕ はxのp進評価であり、u ∈ ℤ_p^× は単位です。評価は通常の整数として表され、単位は無限桁の数値として、関心のある精度に切り詰められます。ℤ_pを別の方法で見ると、0 ≤ x_i < p の「無限精度」の数値(x₀, x₁, …)であり、p進数 x = ∑_{i=0}^∞ x_i p^i に対応します。14 この表現では、eは単に最初の非ゼロx_iのインデックスであり、uはp^eで「シフト」された数値です。基本的な算術演算は(無限)整数上の演算と同じように機能し、対応する命令add、sub、mulはbの代わりにpを使用します。15 有限マシンでは、これらの無限整数は有限精度に切り詰められ、有限シーケンスと正確に奇数基数の多倍長算術に到達します。しかし、除算は同じようには一般化されません。その理由は、剰余を伴う除算がアルキメデスノルムに関して丸められるためです。しかし、p進数上の自然なノルムはp進評価です。それに関する剰余を伴う除算は、ヘンゼルリフティングによって計算され、剰余を伴う除算、したがって対応するdivと長除算アルゴリズムが使用されるユースケースは知りません。

もう一つの候補は基数変換です。x = (x_n, x_{n-1}, …, x₀)₃ を16進数 (y_k, y_{k-1}, …, y₀)₁₆ に変換したいとします。標準的な方法は、基数3で実行される算術演算を使用してxを16で繰り返し割り、剰余から16進数の数字を読み取ることです。実際、45 = 0x2d = (1,2,0,0)₃ を3進数から16進数に変換する際の除算は (1200)₃ / (121)₃ であり、これはAlgorithm Dのバグが発生する最小の反例に正確に対応します。しかし、同じことを行うはるかに簡単な方法があります。それは、数値を直接バイナリ/16進数/基数2^64に変換することです(例えば、ホーナー法を使用)。そして、ニブルを読み取るだけです。

奇数肢整数の長除算の実用的なユースケースをご存知でしたら、ぜひお知らせください!

llvmの「バグ」

クヌースのAlgorithm Dの実装を探している間、マシンワードが奇数であるという仮定の下でも、バグが現実的に発生する可能性のある実装を見つけるのは困難でした。その理由は、ほとんどの実装がステップD3にwhileループを使用しており、そのwhileループが試行商を3回目に修正するため、バグが緩和されるからです。Algorithm Dの実装の長いリストを、Stefan Kanthakのブログで見ることができます。そこでは、さまざまなバグや問題が強調され、コメントされています。それらのすべてがwhileループを使用しています。それらはすべて、クヌースの文章のこの部分を実装しています。