p20190917a

IMULで整数の割り算を実現する

• (by K, 2019.09.17)

(1)

• gccが生成したアセンブラを見ていたら、EAXに入っている値を40で割るときに、

  SAR EAX,3
  IMUL EAX,EAX,0xcccccccd

• という見慣れないコードを生成していた。何だこれは？
• でも確かにこの方法で、40での割り算が実現できている。
• これは面白いと思ったので、ちょっと探求してみたい。

(2)

• まず5での割り算をIMULでやる方法を考えてみる。ここで仮定としては、EAXには5の倍数以外は入っていないとする。

  5 * 0x33333333 = 0x0:ffffffff  失敗(-1/5倍)
  5 * 0x33333334 = 0x1:00000004  失敗(+4/5倍)
  5 * 0x66666666 = 0x1:fffffffe  失敗(-2/5倍)
  5 * 0x66666667 = 0x2:00000003  失敗(+3/5倍)
  5 * 0x99999999 = 0x2:fffffffd  失敗(-3/5倍)
  5 * 0x9999999a = 0x3:00000002  失敗(+2/5倍)
  5 * 0xcccccccc = 0x3:fffffffc  失敗(-4/5倍)
  5 * 0xcccccccd = 0x4:00000001  成功(+1/5倍)

  • [Q]この0x33333333とかはどうやって思いついたの？
  • [A]ええと、0x100000001を5で割ってみただけです。0x200000001を5で割ったら0x66666666が出ます。
• なるほどこういう仕組みなのかー。逆に言うと、-5で割りたいときは、0x33333333を掛け算すればいいということか。

• 他の数値はどうだろう。主要な値を調べてみた。

  3 * 0x55555555 = 0x0:ffffffff (-1/3倍)
  3 * 0xaaaaaaab = 0x2:00000001 (+1/3倍)
  7 * 0x49249249 = 0x1:ffffffff (-1/7倍)
  7 * 0xb6db6db7 = 0x5:00000001 (+1/7倍)

• こうしてみると、その気になれば大抵の奇数は逆数もどきが作れそうな感じだ。

(3)

• では偶数ではどうだろう？

  6 * 0x2aaaaaaa = 0x0:fffffffc (-4/6倍)
  6 * 0x2aaaaaab = 0x1:00000002 (+2/6倍)
  6 * 0x55555555 = 0x1:fffffffe (-2/6倍)
  6 * 0x55555556 = 0x2:00000004 (+4/6倍)
  6 * 0xaaaaaaaa = 0x3:fffffffc (-4/6倍)
  6 * 0xaaaaaaab = 0x4:00000002 (+2/6倍)

• どうやら、1/6倍や-1/6倍というのはできないようだ。
• だから40で割るときも、まずは8で割っていたのか・・・。

(4)

• なぜGCCは整数除算を実装する際に奇数で乗算を使用するのですか？
• https://codeday.me/jp/qa/20181219/20410.html

• ここをみると、ターゲットが倍数ではない場合でさえ、乗算とシフトでDIVを回避しているように見える。
• うーん、まだまだ奥が深い・・・。

こめんと欄