p20190917a の変更点

追加された行はこの色です。
削除された行はこの色です。
p20190917a へ行く。
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を回避しているように見えます。
 -ここをみると、ターゲットが倍数ではない場合でさえ、乗算とシフトでDIVを回避しているように見える。
 -うーん、まだまだ奥が深い・・・。
 
 * こめんと欄
 #comment