Gobble up pudding

プログラミングの記事がメインのブログです。

MENU

割り算を考えてみる

スポンサードリンク

f:id:fa11enprince:20200628231655j:plain
アセンブラの勉強をしていて、CPUの話に興味をもって突っ込んだら、
割り算って苦労してるのね…ってことがわかりました。
なんかで聞いた話ではゲームボーイとかは割り算が使えなかったとか。
割り算にもいろいろな方式があって、いまSRT法っていうのが主流だそうで。

ここを読むとCPUにもバグって起こりうるんだね…へーという感じでした。

その一歩手前の非回復型(または非復元型)除算 (non-restoring division) 、
引き放し法というのがあって、wikipediaに載っていて、
そこに書いてある擬似コードをCで書き直してみようと思ったら挫折しました(´・ω・`)。
だって2進の配列みたいのを4Byteでやるなら32個だかものによっては
33個?用意して回さないといけないんだけど……
めんどくさい。
書いてある擬似コードがなんか不完全なんですよね……。
除算 (デジタル) - Wikipedia

P[0] := N
i := 0
while i < n do
  if P[i] >= 0 then
    q[n-(i+1)] := 1
    P[i+1] := 2*P[i] - D
  else
    q[n-(i+1)] := -1
    P[i+1] := 2*P[i] + D
  end if
  i := i + 1
end while

このコード納得いかない。
Pのそれぞれの要素には0か1しか入ってはいけないのに、
N(除数)をそのまんま入れているのがまず変。
1回目ループで商の桁の開始位置をどこか決めないとダメな気がするし、
Pがnより1個多くないと範囲外アクセスだし。やりたい意図はわかるんだけど。

Cで素直に割り算を使わずに割り算を書くと以下のようになるでしょう。

なんだかとっても勉強になりました。