2で割ることと3で割ること - Qiita

この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除

[mozukuyummy]

大昔にマイコンで16bitのitoaを自作した時は、10の累乗で割るよりも、「これ以上引けなくなるまで10000を引く」「これ以上引けなくなるまで1000を引く」...をベタベタに書く方が早かったなあ。

[yife]

"じゃあ除算はというと...なんと最大 97クロックかかります。メモリアクセスの方が速くなりかねないぐらいの遅さです。" 3で割るっていうシンプルな題材と、現実の泥臭い実装の差が面白かった

[magicalboy]

画像処理は2^n - 1の定数で割る処理が結構あるのでこういう乗算＋シフトをよく使っていた。

[theatrical]

3のマジックナンバーなんて、なんでこんなの思いつけるんだよ。と言う感じがあるけど、理屈を聞けば意味がわかるし、ちゃんと知識と考え続ける能力があればたどり着けるものだと考えると、やる気がでる

[mominis]

これを考えつく発想力がやばい

[kamocyc]

“ 『ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか』に載っている内容です。” そのうち読みたい

[h3poteto]

2で割るのをビットシフトにするのは知ってたけど，3はすごいな

[terazzo]

この記事は誤差の正当性の証明が核だな。／宴会の割り勘で14人で割るときに総額を7倍するとかしてた(誤差はまあ愛嬌)。5人なら2倍して10で割る(こっちは誤差なし)。

[greenbow]

なるほど面白い。 “発想は「もう3で割られている」大きな整数Mを作ることです。”

[wrss]

3は知らなかった！！

[efcl]

除算命令は遅いため、乗算で表現する話。 2の倍数と3の倍数。

[tasshi820]

“割る対象の数にMMMをかけ、かけた値に右ビットシフトをして？？？の部分を除去すると、割る3部分だけが残るはずだ、というのが方針です。”

[mrkn]

32ビット整数除算を64ビット固定小数点乗算に置き換える話

[zyzy]

ひえー、こんな事してたのか。2の倍数と3の倍数がハックできれば、かなりの計算が楽できるよな。

[manaten]

なるほどなと思いつつ、乗算部分でオーバーフローしても期待通りに動くんだろうかとおそらく初歩的なところで躓いている自分

[knok]

こういう最適化の積み重ねがコンパイラ技術には投入されてるのがすごい。歴史もあるけど

[honma200]

おー、なるほど。あとは7ができれば良い感じ？(素数全般そうなっちゃうけど・・・)

[kamei_rio]

四則演算として同列に並べるには、割り算って難しすぎるよね。やはり逆元がある体は偉大

[Nyoho]

3で割るところの謎の整数1431655766は、読みながらmod 2^32での3の逆数をかけているのかなあと予想したけど、その2倍だった。

[yarumato]

“除算は圧倒的に遅い。x86 CPUだと、加算・シフト演算は1クロック。乗算は4クロック。除算は最大97クロック。だからコンパイラは除算命令の生成を極力避け、定数２で割る場合シフト使い、定数3で割る場合も乗算でやる”

[maghrib]

“ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか”

[richard_raw]

なるほど、3の場合はこうなるのか。

[sytkm]

前どこかで読んだ気がしたけど多分参考資料にあるやつだと思う。やっぱり面白い。

[fukurou112]

逃げ出さないこと信じ抜くこと

[Guro]

いままで知らずにプログラマやってたわ。。

[cu39]

地道な積み重ねの跡が見えて面白い。

[natu3kan]

2の補数とビットシフトで手早く割り算をする。10進法の1431655766は2進法で1010101010101010101010101010110で16進法で55555556。ウィキペによると1431655766/2の715827883はワグスタッフ素数で2^31+1/3。

[tettekete37564]

3の割り算のやつあとで読む。8ビット時代にアセンブラで整数の割り算実装した事あるはずだけどもう全然覚えてない。

[naoya2k]

3で割るやつの実装、さもすごいことのように書かれているけど、学校では「割り算は遅いので、除数が定数の場合は一般的に逆数の乗算で実装されます」の1行で説明完了してたしみんなそれで理解できてたで。

[kujoo]

"1431655766 という謎のマジックナンバー"

[hatest]

10進数の世界の常識と2進数の世界の常識の違い

[oktnzm]

32.768 kHzを連想した。謎定数好き。

[sharaku3eyes]

すごい。こういう人と働きたい

[Sampo]

除算を乗算に変換するアイディア、どうも学部の授業でやってたらしいんだけどおれの取った講義では習わなくて、院に行ったあと学部の後輩の勉強みてやってたときに出てきてなんだこの神テクはってなった思い出。

[higamma]

やばい…

[kirakking]

理論上の除算とくらべて、数値の精度に限度があるからこそできるハックを感じて面白い。