ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

2乗計算が速い理由

2つの整数を掛け算するときに、たとえば98*37の計算なんかは筆算を使うだろう(これくらいなら暗算できなくもないが)。これが2乗のとき、98*98を計算する場合は筆算してもいいが、98*98 = (100-2)*(100-2)なので2乗の展開の公式を使うと100*100 - 2*100*2 + 2*2とでき、筆算を使わなくてもよさそうだ。しかし桁数が大きくなると紙の上で計算するのが大変なのでコンピュータに任せたくなる。コンピュータ上でも2乗(sqr(X))は同じ数の掛け算(mul(X, X))よりも効率よく計算できるので速いそうだ。

紙の上ではたしかに楽に計算できたが、コンピュータ上ではどうやって効率化を図っているのか気になる。

 

3桁の2つの整数AとBがあり、筆算法で掛け算するときの図を下に示す。

f:id:ushiromiya3:20191222180130j:plain

筆算法の掛け算(AとBが異なる場合)

図からわかるように、9回の掛け算をやったあと足し算して答えを求めている。一般に、n桁*n桁の掛け算を筆算法でやるとn^{2}回の掛け算が発生する。桁数が大きくなるにつれ掛け算の回数も一気に増えていく。これを2乗という掛け算の特殊ケースの場合に効率化するのが目的だ。

 

では次に2乗するとき(A=B)の筆算法を下に示そう。 

f:id:ushiromiya3:20191222180159j:plain

2乗計算

 よく見ると同じ掛け算が3回発生している。同じ掛け算を2回してから足さなくとも、1回だけ掛け算して2倍すればよい。コンピュータ上における2倍は1ビットの左シフトなので、複数回の掛け算がビットシフトに置き換わる。計算に必要な掛け算の回数が減るので2乗は速い。筆算法が一番naiveな方法で、これと比較すると2乗計算はかなりコストが落ちているように思えるが、実際は一つ一つの掛け算は筆算法よりも効率の良いものがあるのでmul(X, X)のコストを1とするとsqr(X)は0.8くらいに収まる(要出典)。

速いのはたしかなので2乗専用の関数があるなら使ったほうがよい。