<前の日記(2013-10-12) 次の日記(2016-06-20)> 最新

おおいわのこめんと (2014-04-14)


2014-04-14

[Misc] Radix Economy の話

仕事でなんとなく3値論理を調べていて、 「そういえば3進法(非整数でも良ければ e 進法)が数学的には最も効率がいいって言うんだよなぁ」 と思いだしてしまったのが事の発端。

Radix economy といって、端的に言うと

b 進法で、各桁の表現に b のリソースを要求されるとき、大きな数字を表現するのに漸近的に最もリソース利用効率がいいのは何進法か。

という問題で、上のページを見てもらうとわかりますが比例係数が \[b / \log b\] になるので、この最小値が \[b = \mathrm{e}\] のとき、整数では \[b = 3\] になります。4進法で1桁当たり信号線4本を使うのと、2進法で1桁当たり信号線2本を使うのが同じ効率になるのも、理解できます。

でも、上のページでは色々と初期の計算機の話が書いてあったりするのですが、 現代の普通のコンピュータでは2進法のほうがどう考えても効率がいいよな、と思ってしまったわけです。 それで、なんでこんな結果が出ているのかなと考えたら、 結局は「(少なくとも現代のコンピュータでは)2進法の使うリソースは1ビット当たり2本ではなく1本」で、「信号がない」ということに情報を割り当てているから差が出るわけです。

さて、それではどう直すかなのですが、現代的な情報量の概念を入れて1桁あたり \[\log b\] のリソース消費とかしたら、全く計算の意味がないわけです。元の定義の気持ちを生かしつつ、2進法について辻褄が合うことを考えると、とりあえず元の定義に一番近い修正としては、 「『0 = 信号なし』で表現できるので、\[n - 1\] 本の信号線で十分」 と直せそうです。例えば3進法の場合、「1」「2」の2本の信号線があって、何もなければ0という意味。あきらかに2進法に都合の良い設定ですが、とりあえずの変更としては妥当じゃないかなぁ。

さて、これで計算やり直してみますか、と思いついたのが運の尽き。計算の誘惑にズブズブとはまっていきます。久々にやると楽しいね(笑)

先ほどの Radix economy の計算式は、

\[E(b,N) = b \lfloor \log_b(N) + 1\rfloor \sim b \log_b N = \frac b{\log b} \log N\qquad(N \to \infty)\]

だったのですが、これを

\[E^-(b,N) = (b - 1) \lfloor \log_b(N) + 1\rfloor \sim (b - 1) \log_b N = \frac {(b - 1)}{\log b} \log N\qquad(N \to \infty)\]
と書き換えて、\[\log N\] を取り去って定義域を実数化した \[f(x) := \frac{x-1}{\log x} \quad (x > 0)\] の増減を考えます。Gnuplot にかければ一発じゃん……とか言わずに。 まずは微分。
\[f'(x) = 
\frac{(x-1)' \log x - (x-1)(\log x)'}{(\log x)^2} = 
\frac{\log x + x^{-1} - 1}{(\log x)^2} =: 
\frac{g(x)}{(\log x)^2}\]

分子の微分を考えると

\[g'(x) = \frac 1x - \frac1{x^2} = \frac{x - 1}{x^2}\]

となります。増減表を書いていくのですが、 極値を求めるのには L'Hôpital の定理がフル活用になります。

\[g'(1) = 0\]

\[g(1) = 0, \lim_{x \to +0} g(x) = +\infty\]

\[\lim_{x \to +0} f'(x) =^* \lim_{x \to +0} \frac{g'(x)}{[(\log x)^2]^\prime} = \lim_{x \to +0} \frac{x-1}{x^2}\Big/\frac{2\log x}{x} = \lim_{x \to +0} \frac{x - 1}{2x \log x} = \frac{-1}{-0} = +\infty\]

\[\lim_{x \to 1} f'(x) =^* \lim_{x \to 1} \frac{x - 1}{2x \log x} =^* \lim_{x \to 1}\frac1{2(\log x + 1)} = \frac12\]

\[\lim_{x \to +0} f(x) = \frac{-1}{-\infty} = +0\]

\[\lim_{x \to 1} f(x) =^* \lim_{x \to 1}\frac{1}{1/x} = 1\]

途中 * のついた所でロピタルの定理を使いつつ、適用条件を毎回確かめて……とやってますが、全部省略。「大学入試で使ってもいいけど細かい条件全部ちゃんと確かめてないと減点だぞー」とか、少し前の話題にありましたね。

……ふぅ。間違えてないよなぁ(こっそり Gnuplot にグラフ書かせてそれらしいことは確かめている)。久々の計算なので、ドキドキしながら増減表。

\[\begin{array}{c|cccc}
x & +0 & & 1 & \\\hline
g'(x) & -\infty & - & 0 & + \\\hline
g(x) & +\infty & ^+\searrow & 0 & \nearrow^+ \\\hline
f'(x) & +\infty & + & (1/2) & + \\\hline
f(x) & (0) & \nearrow & (1) & \nearrow
\end{array}\]

はい、結局のところ、単調増加です。この設定では1進法は「無限桁必要で各リソース0」という意味のないケース(そもそも極限はあるけど値は未定義)なので、2進法が最適効率になります。

グラフ

グラフ書いてみました。まぁあまりに2進法に有利すぎる設定ですが、 その上もずーっと単調増加なのはわかったかなと。

逆に考えると、非同期式計算機の実現方法の中には、2進法での0信号線と1信号線が別々に用意されている(「計算中で未確定」という状態を、両方0で表す)ものがあるので、そういう場合はやっぱり3進法が若干効率が良い、ということにもなるのですね。

[TrackBack URL: http://www.oiwa.jp/~yutaka/tdiary/trackback.rb/20140414 (note: TrackBacks are moderated: spams will not be shown.) ]

大岩 寛 (おおいわ ゆたか) <yutaka@oiwa.jp.nospam ... remove .nospam> .

Copyright © 2005-2014 Yutaka OIWA. All rights reserved.
Posted comments and trackbacks are copyrighted by their respective posters.

記事の内容について (Disclaimer / Terms and Conditions)