最新

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


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 にかければ一発じゃん……とか言わずに。 (計算の続きを読む) ...

……ふぅ。間違えてないよなぁ(こっそり 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進法が若干効率が良い、ということにもなるのですね。


大岩 寛 (おおいわ ゆたか) <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)