Dark Arithmetic 〜✝暗算✝〜 入門

> 「馬鹿な、フォースパワーオブサーティーンをそらで唱えるだと？！」
俺の詠唱したダークアリスメティックに、男の顔が恐怖で歪む。

# フォースパワーオブサーティーン！

13の4乗。高校数学をかじっていると、

$$(10+3)^4 = 10^4 + 4 \cdot 10^3 \cdot 3 + 6 \cdot 10^2 \cdot 3^2 + 4 \cdot 10 \cdot 3^3 + 3^4$$

なんてやり方が思い浮かぶだろう。

この記事を読むような、プログラミングをある程度やっている人であれば高速冪乗法を知っているだろう。そんな人は

$$ 13^4 = (13^2)^2$$

が思い当たるはずだ。

日本の高校受験をまともにやっている人間であれば $ 13^2 = 169 $ は覚えているだろう。覚えていなくとも $ (10 + 3)^2 = 100 + 60 + 9 $ で簡単に求まるはずだ。

問題はその次である。他にも変態的なやり方はあるが、標準的なやり方で

```math
\begin{eqnarray}
169^2 &=& (170-1)^2 \\
&=& 170^2 - 2 \cdot 170 + 1 \\
&=& 170^2 - 340 + 1 \\
\end{eqnarray}
```

まあここまでは誰もがたどり着けるだろう。さて、読者は $17^2=289$ を暗記しているだろうか？<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby>に入門したての<ruby>新入り<rt>ニュービー</rt></ruby>にはハードルが高いかもしれないが、$100 + 140 + 49 = 289$ と考えれば納得だろう。

$\therefore 170^2 = (17\cdot10)^2 = 289 \cdot 100 = 28900.$

初心者の君は元の数式をもう忘れてしまったかもしれない。我々は何故$170^2$を計算しようとしていたのだろう？

<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby>において、このような迷子はよくあることだ。気に病むことはない、誰もが通ってきた道だ。
迷子にならないためには、 **方針をよく反芻し、一歩進むごとに今までやってきたこと、これからすべきことを見直す** ことだ。ここまでノンストップで来てしまったのなら、それは間違いだ。迷子にならないためには一歩進むごとにパンくずを床に撒くくらいの慎重さが必要なのだ。

さて、方針をよく反芻した賢明な読者であれば、我々が $170^2 - 340 + 1$ の計算のために $170^2$ を計算していたことを思い出すことが出来るだろう。そしてその答えが $28900$ だったことも。先に進もう。

```math
\begin{eqnarray}
&&28900 - 340 + 1 \\
&=& 28[900 - 340] + 1 \\
&=& 28[900 - 300 - 40] + 1 \\
&=& 28[600 - 40] + 1 \\
&=& 28560 + 1 \\
&=& 28561 \\
\end{eqnarray}
```

ただの足し算引き算であっても、**うまく工夫してわかりやすい部分に分割することを怠らないようにしよう。**今回はたまたま簡単だったが、数字が大きく、複雑になればなるほどその恩恵は大きくなる。

# <ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby>には問題解決のためのエッセンスが詰まっている

問題解決を仕事としているエンジニア諸氏はお気づきだろうか？これまでの過程に、問題解決のための基本が詰まっているということに。

## 問題をわかりやすい部分にブレイクダウンする

今回 $13^4$ という比較的難しい問題を、 $13^2$ や $17^2$、 足し算や引き算といった簡単な問題に分解し、その答えを組み合わせることで解決した。

どんなに難しい問題でも、詳しく紐解いていけば自明の理の組み合わせになる。

## 迷子にならないように振り返り、見通しを立てる

これは実感してもらった通りである。実感したよね？

考えなしに作業を進めていても、たどり着くのは袋小路なのだ。常に問題全体を俯瞰する姿勢を持とう。

## パターンを知っていると速く解決できる

$13^2$ や $17^2$ を覚えていた人は、それを覚えていなかった人に比べてかなりの時間が短縮できたはずだ。

あなたの直面した問題は、既に誰かが解決しているかもしれない。逆に、この先誰かが同じ問題に直面するかもしれない。

巨人の肩に(理解した上で)乗ろう。自分の肩への登り方をわかりやすく共有しよう。

## 諦めるな、鍛錬を積み重ねよ

最後の足し算引き算や、方針を忘れないでいるために、一時メモリの限界を感じた人もいるかもしれない。

こればっかりは一朝一夕でどうにかなるものではない。限界を感じても、諦めず時間を掛けて考え続ければ答えにたどり着くことが出来る。

<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby>ジャンキーの私でさえ、最近 $11 \cdot 12 \cdot 13 \cdot \dots \cdot 19$ という難問を丸3日掛けてやっと解いたところだ。最後の19倍は本当に苦しく楽しかった。

# まとめ

<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby> はカッコイイ
<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby> は楽しい
<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby> には問題解決の基礎が詰まっている

# おまけ: 2倍は左から

2倍という計算は1桁しか繰り上がりが発生しないので、左から順に読みつつ計算が出来る。
発声と同じ順番で答えが出てくるので効率が良い。

コードにするとこんな感じだ ~~(申し訳程度のプログラミング要素)~~ :

```elixir:twice.ex
twice_map = Map.new(0..9, fn n -> {n, Integer.mod(n * 2, 10)} end)
Stream.repeatedly(fn -> Enum.random(0..9) end) # ランダムなdigitを出力するストリーム
|> Stream.map(&IO.inspect/1) # ストリームの中身を出力しておく
|> Stream.chunk_every(2, 1) # 2個のカタマリを1ずつずらしながら取得
|> Stream.map(fn [a, b] ->
  Map.fetch!(twice_map, a) + if b < 5, do: 0, else: 1
end)
|> Enum.take(6)
|> IO.inspect()
```

これを twice.ex として保存して、iex から読んで実行すると

```elixir
iex(1)> Code.load_file("twice.ex")
3
6
5
6
8
7
9
[7, 3, 1, 3, 7, 5]
[] # これは Code.load_file/1 の返り値
```

3656879... というストリームに対して 731375... と左から2倍の計算が出来ていることがわかる。

<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby>においても、バッチ処理よりストリーム処理の方が楽なことは多い。

# おまけ: 別解

```math
\begin{eqnarray}
169^2 &=& (160 + 9)^2 \\
&=& 160^2 + 2 \cdot 160 \cdot 9 + 9^2 \\
&=& 25600 + 2 \cdot 10 \cdot 16 \cdot 9 + 9^2 \\
&=& 25600 + 2 \cdot 10 \cdot 4^2 \cdot 3^2 + 9^2 \\
&=& 25600 + 2 \cdot 10 \cdot 12^2 + 9^2\\
&=& 25600 + 2 \cdot 10 \cdot 144 + 9^2 \\
&=& 25600 + 2880 + 81 \\
&=& 25600 + 2961 \\
&=& 25600 + 3000 - 39 \\
&=& 28600 - 39 \\
&=& 28561 \\
\end{eqnarray}
```

```math
\begin{eqnarray}
169^2 &=& (144 + 25)^2 \\
&=& (12^2 + 5^2)^2 \\
&=& 12^4 + 2 \cdot 60^2 + 5^4 \\
&=& 3^4 \cdot 4^4 + 2 \cdot 3600 + 5^4 \\
&=& 81 \cdot 4^4 + 7200 + 625 \\
&=& 324 \cdot 4^3 +... \\
&=& 1296 \cdot 4^2 + ... \\
&=& 1296 \cdot 2^4 + ... \\
&=& 2592 \cdot 2^3 + ... \\
&=& 5184 \cdot 2^2 + ... \\
&=& 10368 \cdot 2 + ... \\
&=& 20736 + 7200 + 625 \\
&=& 27936 + 625 \\
&=& 28000 - 64 + 625 \\
&=& 28000 - 40 + 601 \\
&=& 28561 \\
\end{eqnarray}
```

他にも色々あるはず。
1つの問題に対する解法がいくつもある所も<ruby>✝暗算✝<rt>ダークアリスメティック</rt></ruby>の魅力である。