Computer Transformation(5) - カメヲラボ

Cで実装する場合、2の累乗と3での除算という2種類の乗除はコードを長くするだけだ。ここで、第3回で書いたいくつかの式

$a_5=2^3-2^2+2^1-2^0\\a_6=2^4-2^3+2^2-2^1+2^0\\a_7=2^5-2^4+2^3-2^2+2^1-2^0$

これをもう一度よく見てみることにする。
特徴は正・負交互に2^nが並んでいて、最後は2^0だ。ここでそれぞれの式の、最終項(2^0)以外を2で括り出してみる。

$a_5=2(2^2-2^1+2^0)-2^0\\a_6=2(2^3-2^2+2^1-2^0)+2^0\\a_7=2(2^4-2^3+2^2-2^1+2^0)-2^0$

これらと上の式を比較すれば、

$a_5=2a_4-2^0\\a_6=2a_5+2^0\\a_7=2a_6-2^0$

という関係になっていることに気が付く。2^0=1なので、a_nを再び漸化式で表すと

$a_{k+1}=2a_k-(-1)^k$
$(a_1=0)$

以前作った漸化式

$a_{k+1}=2^{k-1}-a_k (a_1=0)$

と比べると、2での乗算は共通としても、減算が $a_k$ から1 or -1になり圧倒的に計算しやすい。id:kurimuraさんはこれに一早く気付き、見事Java超えを果たした。というわけで、ここからはkurimuraさんのコードを追いかけつつ、最短コードのための超絶テクニックに迫ろうと思う。