日々精進

新しく学んだことを書き留めていきます

プログラマの数学

日記

プログラマの数学

プログラマの数学

最初のほうを少し読んでみた。
一章はN進法のハナシで、基数変換が出てきた。
基数変換は簡単な計算で可能。詳細は↓参照
http://www.jtw.zaq.ne.jp/kayakaya/new/kihon/text/kisuhenkan.htm
なんでこの計算で変換できるんだろうと疑問に思ったので証明してみた。
a_{n}を基数変換の計算法におけるn-1回目の演算結果（つまり、a_{1}は変換前の数）
R_{n}を余り
とすると、以下の漸化式が成り立つ。
a_{n}=1/2(a_{n-1}-R_{n-1})
この漸化式を解くと、以下の式になる。（途中の操作は省略）
a_{n}=a_{1}/2^n^-^1-\sum^{n-1}_{k=1}(R_{n-k}/2^k)
この計算法では計算結果が0になるまで計算を続けるので、a_{n}=0である。
これを代入して式を変形すると以下となる。
a_{1}=\sum^{n-1}_{k=1}(2^k^-^1*R_{k})
右辺はR_{n}をn桁目とする2進数を10進数に変換するときの計算式と同じである。
よって上記の基数変換は常に成り立つ。


TeX記法初めて試してみたけどめんどいｗ一部ずれてるし。
理系の癖に論文はすべてWordで書いたし。。
数列とか懐かしいなぁ。