はじめに
「プログラミング・ビットコイン」というオライリーの本にて、2進展開を使って計算量を減らすテクニックに出会って感動したので、それを記録しておくためにこの記事を書きました。
2進展開とは
情報系の学問を学ぶにあたって前菜として出てくる2進数。ある整数$a$を2進数で表すために、
a = a_{0}\times2^0 + a_{1}\times2^1 + a_{2}\times2^2 + \dots + a_{n}\times2^n
を満たすような$a_0, a_1, \dots, a_n$を求める必要があります。言い方を変えると、$a$を2の累乗を用いて表す必要があるということです。このような表し方を2進展開といいます。
例えば整数14を考えてみましょう。整数14は
\{14\}_{10} = 0 + 2 + 4 + 8 = 0 \times 2^0 + 1 \times 2 ^ 1 + 1 \times 2 ^ 2 + 1 \times 2 ^ 3 = \{1110\}_{2}
のように2進展開で表すことができます。
2進展開を用いて計算量を減らすテクニック
本題のテクニックについてですが、用いるところはかなりシンプルです。
以下の問題を解くアルゴリズムを考えます。
ある整数mについてn回加算を繰り返した時に得られる数を求めなさい。ただし、使用可能な演算は加算のみとする。
ただし、使用可能な演算は加算のみとする。という文に疑問を持つ方もいると思います。これについては補足で浅く説明しています。興味ある方は参照してください。
さて、アルゴリズムについて、パッと思いつくのはfor文で$n$回ループさせることでしょうか。
プログラムは以下のようになります。
# O(n)
m = 3
ans = 0
n = 10
for _ in range(n):
ans += m
print(ans) # ans = 30
こちらの計算量は$O(n)$となります。このアルゴリズムには欠点があります。それは$n$が大きくなったとき計算にかなりの時間を要してしまうということです。
そこで改良版として2進展開を用いたアルゴリズムを考えます。
まず、求める解はm=3, n=10のとき、
\begin{align}
ans &= m \times n\\
&= 3 \times 10 \\
&= 3 \times (0 \times 2^0 + 1 \times 2^1 + 0 \times 2^2 + 1 \times 2^3)\\
&= 0 \times 3 \times 2^0 + 1 \times 3 \times 2^1 + 0 \times 3 \times 2^2 + 1 \times 3 \times 2^3\\
&= 0 \times 3 \times 1 + 1 \times 3 \times 2 + 0 \times 3 \times 4 + 1 \times 3 \times 8\\
&= 0 \times (3) + 1 \times (3 + 3) + 0 \times (3 + 3 + 3 + 3) + 1 \times(3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \tag{1}
\end{align}
のようになります。式変形ではnを2進展開したのちそれぞれの項にm=3をかけています。式$(1)$を用いてプログラムを書いていきます。
コードに落とし込むと以下のようになります。
# O(log_2(n))
m = 3
ans = 0
current = m
while n:
if n & 1:
ans += current
current += current
n >>= 1
print(ans) # ans = 30
プログラムの内容を説明していきます。
先ほどの例ではなかった変数currentは、ansに加算する値を格納しておきます。
while n:
...
n >>= 1
n >>= 1では、nの2進数値に対して1ビット右にスライドしています。これとwhileによってnの2進数値の各桁に対して演算を行なっていきます。
if n & 1:
ans += current
current += current
if n & 1はnの2進数値の1桁目が1であるか0であるかの条件分岐を行なっています。1のときans += currentを実行し、0のときif文内には入らず処理が継続されます。
先ほどの処理によってnはスライドされるので、これは演算対象の桁における数が0か1かを判断していることになります。
すなわち、この処理は式$(1)$における0をかけているか1をかけているかに対応しています。
current += currentによって演算する桁に応じた加算する数を用意しています。currentの初期値は3です。ループしていくとcurrentの値は3, 6, 12, 24となります。この処理は式$(1)$における括弧内（$(3 + 3)$や$(3 + 3 + 3 + 3)$など）と対応しています。
説明を踏まえて、このプログラムの全体を眺めてみると、式$(1)$の計算を行っていることがわかりますでしょうか。ループ回数についてはnを2進数にしたときの桁数に依存します。桁数と言えばlogですね。したがって計算量は$O(log_2(n))$となります。
いかがでしょうか。2進展開を用いることで計算量を$O(n)$から$O(log_2(n))$まで減らすことができました！
補足
数学の世界で群と呼ばれる概念があります。詳しい定義は調べて欲しいのですが、この郡で定義される演算は1つのみです。そしてビットコインで扱われる有限巡回群において定義される演算は加算であり、その加算は非線形です。したがって、同じものをn回加算した後の数値を求める方法は、正直に1つずつ足していく方法しかありません。そのときに今回紹介した2進展開を用いることになります。これより深いことは実際に本を読んでみることをおすすめします！！