「プログラマの数学」1章メモ#1 位取り記数法、0とは、指数法則など

##目次
1章 [位取り記数法、0とは、指数法則など](http://qiita.com/weedslayer/items/a218f3ff66dc96effbe0)
2章 [論理積、論理和、ド・モルガンの法則、ベン図、カルノー図、3値論理など](http://qiita.com/weedslayer/items/c87ee0956a20ae9975f3)
3章 (in progress)

##経緯
[プログラマの数学](http://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AE%E6%95%B0%E5%AD%A6-%E7%B5%90%E5%9F%8E-%E6%B5%A9/dp/4797329734/ref=sr_1_1?ie=UTF8&qid=1450997268&sr=8-1&keywords=%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AE%E6%95%B0%E5%AD%A6)という本をおすすめされたので読んでみた。ここにメモがてら簡単に学んだことを書いていこうと思う。全部で9章分あるので章毎に分けてお送り致します。*all credit goes to the author: 結城浩さん

>文系プログラマを対象にした基礎数学の解説書。帰納法，再帰，命題論理といった数学的考え方の基礎を，「ケーニヒスベルクの橋渡り」や「ハノイの塔」のような著名なパズルを題材に説いている。著者は，誰しもが学校のテストで解いてきたであろう問題を，簡潔な語り口でプログラムに置き換えていく。初心者は「いかに問題を単純化して関数に落とし込むか」という根本的課題に対する解を見いだす上で，中上級者は肌で覚えた感覚的スキルに理論の裏付けを得る上で，それぞれ役立つだろう。
-- 日経BP企画

とかとか言ってます。レビューには「この本は文系向きではない」とか「数学を逃げてきた人にとってはわかりにくい」とか書いてあるますが楽しみです。

##位取り記数法
10進法や2進法そして8進法や16進法たくさんあるけど、そういうのをまとめて箱に入れてそれを位取り記数法と呼ぼうと誰かが考える。根本的な中身は一般化するとほぼ同じ。変わるのは使われる数字の範囲の広さと基数の値。ただ16進法では0から9に加えてAからFの16種類。基数はもちろん16。
ちなみにローマ数字の記法では位取り記数法を使わずに数字そのものが値を示すと言ったら分かりやすいでしょうか。例えば1000をMという値にしましょうと決めちゃってるのでそれに従うだけですね。

##表記法の歴史
本書通りに表記法の歴史を辿って行くと、
1. 古代エジプト人が5進法と10進法の混ざった表記法を用いる。5と10のまとまりを示す値を定義して数字を扱った。ゼロという概念はまだなし。パピルスという紙に書き写していたらしい。
2. バビロニア人は粘土板にくさび型の記法を書いて数を表していたらしい。10進法と60進法の混合した位取り記数法の誕生はこの時。1時間60分、1分60秒といった値はバビロニアの60進法の影響らしい。
3. ギリシア人が数は哲学的な心理が隠されているのではないかと考え数学以外のものと関連付けた。
4. マヤ人は0を起点に数を考える。当時使っていたのは20進法。
5. ローマ人が5進法と10進法の混じったローマ数字を使う。
6. インド人が0も数であると認識する。彼らは10進法を採用しアラビア数字と言われる現在我々が使っている記号を使いはじめる。

このように表記法が変わっていったのはひとえに大きい数を扱い始めると当時の表記法では限界があったからだと筆者はいいます。12という数字を表現するのに$IIIIIIIIIIII$は面倒くさい$XII$にしよう、いやそれも面倒くさいいっそのこと12しようという具合に。

##「大きな問題は、小さなまとまりに分けて解け」
大きな数を効率よく表現することは古代の人にとって重要な問題だったといいます。人間の認識能力に応じた最適な表現方法は10進法及び位取り記数法だったのです。

>　人間が宇宙にロケットを飛ばし、遺伝子情報を解析するようになると、私たちが扱う数は爆発的に大きくなっていきます。そうすると位取り記数法でも不十分です。1000000000000と10000000000000ではどちらが大きいか、すぐにはわかりませんね。そこで指数を使った表現が重要になります。

##10進法とは何か
英訳するとdecimal number
使う数字は0から9までの10個。数の桁に意味があり右から順に1の位、10の位と桁が上がっていく。10進法は桁が少なくてすむが、数字の幅が広い。
例：
$2503 = 2*10^3 + 5*10^2 + 0*10^1 + 3*10^0$
10進法は全て$10^n$。これを10進法の基数と呼ぶ。

##2進法とは何か
英訳するとbinary number
使う数字は0から1までの2個。右から順に1,2の位。
左の桁から8の個数、4の個数、2の個数、1の個数と決まっている。2進法は逆に数字の幅が狭くて済むが、桁数が多くなる。
例えば数が単純（12とか）だと二進法では1100とすぐわかるんだが、数が大きくなってくると対処が面倒くさい。
例：
$1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0$
そこで2進法では数をひたすら2で割っていきそのあまりが0になるか1になるかで数字の値を決めている。割れれば0とし、割れなければ１とするそれを最後の1もしくは0になるまで続ける。あとは最後に出てきた数字から先頭に数を書いていけばよし。2進法の詳しい表記方法は[この辺](http://www.geisya.or.jp/~mwm48961/math/m2si32.htm)を参考に。

###補足
10進法のほうが数の大きさが直感的に分かりやすいことから、人間は2進法よりも10進法のほうが扱いやすいと感じる傾向にある。人間は指が10本ありますしね。

ちなみに人間がコンピューターを使って数字の計算をするときは、
1. 人間がコンピューター上に10進法で数字を入力する
2. コンピューターがその数字を2進法に変換して数字を2進法で計算
3. コンピューターが10進法へ変換して答えを表示
*ちなみにここで行われている変換は基礎変換と呼ばれるらしい。

例：
> $21 + 19 → 10101 + 10011 = 101000 → 40$

##N進法
まとめというわけではないがここでN進法についても触れておく
使われる数字は0からN-1までのN個の数字。
例:
$a3 * N^3 + a2 * N^2 + a1 * N^1 + a0 * N^0$
Nはその値のくらいの大きさに応じて指数を1ずつ増やしていく。最終的にはNの値とaの値（0からN-1）を掛けあわせた和が答えとなる。

##指数法則
10進法でよく出てくる$10^0$は1というのは当たり前の事実なのですが、なぜそうなるのでしょうか。$10^2$が100であるならば0乗は1ではなく0ではないかと。
そこで「指数が1減ると、全体は10分の1になる」というルールに則って考えてみる。すると何の障壁もなく$10^0$は1ということがわかる。$10^-1, 10^-2,10^-3$も同じように$1/10, 1/100, 1/1000$と数が小さくなっていくことが分かる。
つまり指数を減らす毎にその数を基数で割ってあげればいいのです。もちろん指数が上がればその数を基数で掛けあわせてあげるだけ。

##0はplaceholder

> 位取り記数法では、位が重要な意味を持ちますから、10の位の数が「ない」としても、そこに何も数字を置かないわけには行きません。そこで0の出番です。すなわち、0の役割は場所を確保しておくことにあるのです。いうなれば、0は上の桁が落ちてこないように支えているのです。

まさにplaceholderの定義を語っているかのようですね。
例：
$ak * 10^k, n = 3, a3 = 2, a2 = 5, a1 = 0, a0 = 3$とすると、
$2 * 10^3 + 5 * 10^2 + 0 * 10^1 + 3 * 10^0 = 2503$となる。
0を使ってその値は何もないということをシンプルかつ簡単に説明できることがわかる。
日常的な例で一番わかりやすいのは何も予定の入っていない日をゼロとする考え方と似ていると本書では言っていました。