2つのnビット数の再帰除算アルゴリズム

Question

以下の除算アルゴリズムでは、qとrに2つの演算を掛ける理由とxが奇数の場合にrをインクリメントする理由を理解できません。

この再帰除算アルゴリズムの理論的正当性を教えてください。

ありがとうございます。

function divide(x, y) 
    if x = 0: 
     return (q, r) = (0, 0) 
    (q, r) = divide(floor(x/2), y) 
    q = 2q, r = 2r 
    if x is odd: 
     r = r + 1 
    if r ≥ y: 
     r = r − y, q = q + 1 
    return (q, r) 

Answer 1

すなわち者がxが偶数であると仮定しようx = Q * y + R

を表し、あなたがyでxを分割したいと仮定しましょう。あなたは再帰的にx/2をyで割り、小文字の場合はx/2 = q * y + rの表現を得ます。

2を乗算すると、x = 2q * y + 2rが得られます。あなたが最初にxのために得たかった表現を見ると、あなたはそれを見つけたことがわかります！ Q = 2qとR = 2rとし、希望のQとRが見つかりました。

xが奇数の場合は、再び第1より小さい場合のために所望の表現を取得：、(x - 1)/2 = q * y + rを2で乗算：x - 1 = 2q * y + 2r、そして右に1を送信：x = 2q * y + 2r + 1。再度、QとRが見つかりました：Q = 2q、R = 2r + 1。

アルゴリズムの最後の部分は、正規化のため、r < yです。 rは、2倍の乗算を実行するとyより大きくなる可能性があります。