最適な基数の選択

数学とコンピュータサイエンスにおいて、最適な基数選択とは、数値を表現するのに最適な基数（基数）を選択する問題です。特にコンピュータシステムにおいて、数値を表現する際に異なる基数を使用することの相対的なコストを定量化する様々な提案がなされてきました。一つの公式は、その基数で表現するために必要な桁数に、基数（各桁が取り得る値の数）を乗じるというものです。この式は、組織構造、ネットワーク構築、その他の分野に関する問題にも用いられます。

意味

与えられた基数bで数Nを表現するコストは次のように定義できる。

E(b,N)=b\lfloor \log _{b}(N)+1\rfloor \,

ここでは、 floor 関数 $\lfloor \rfloor$ と b を底とする対数を使用します。 $\log _{b}$

bとNがともに正の整数である場合、この量は、基数bで数Nを表すために必要な桁数に基数bを乗じた値に等しい。^[1]この量は、各桁のコストが基数bに比例する場合、基数bで数Nを格納または処理するコストを測定する。したがって、平均値が低い基数は、ある意味では平均値が高い基数よりも効率的である。 $E(b,N)$ $E(b,N)$

たとえば、100 を10 進数で表すと3 桁なので、表現コストは 10×3 = 30 ですが、2 進数で表すと 7 桁 (1100100 ₂ ) なので、同様の計算で 2×7 = 14 になります。同様に、3 進数で表すと 5 桁 (10201 ₃ ) なので、値は 3×5 = 15 となり、36 進数 (2S ₃₆ ) では 36×2 = 72 になります。

数字が、ホイールから各ホイールにb個の数字面があるコンビネーションロックまたはタリーカウンターで表されると想定すると、ホイールがある場合、は、0 からNまでの任意の整数を表すために必要な数字面の総数です。 $0,1,...,b-1$ $\lfloor \log _{b}(N)+1\rfloor$ $E(b,N)$

漸近的挙動

Nが大きい場合の量は次のように近似できます。 $E(b,N)$

E(b,N)=b\lfloor \log _{b}(N)+1\rfloor \sim b\ \log _{b}(N)={b \over \ln(b)}\ln(N).

{E(b,N) \over \ln(N)}\sim {b \over \ln(b)}.

漸近的に最も良い値は基数3で得られます。これは、正の整数で最小値が得られるためです。 $b \over \ln(b)$ $b=3$

{2 \over \ln(2)}\approx 2.88539\,,

{3 \over \ln(3)}\approx 2.73072\,,

{4 \over \ln(4)}\approx 2.88539\,.

10 を底とする場合には次のようになります。

{10 \over \ln(10)}\approx 4.34294\,.

シュタイナーの微積分問題

関数の最大値を求める、あるいはそれと同等の、対数をとって逆関数をとったときにの整数値ではなく連続値に対してを最小化するという連続最適化問題は、 1850 年にヤコブ・シュタイナーによって提起され解決されました。^[2]解はオイラー数、つまり自然対数の底であり、この解をシュタイナーの定式化に戻すと、の唯一の最大値となります。^[3] $f(x)=x^{1/x},$ ${\tfrac {x}{\ln x}}$ $x$ $e\approx 2.71828$ ${\frac {e}{\ln e}}=e\approx 2.71828\,.$ $e^{1/e}\approx 1.44467$ $f(x)=x^{1/x}$

この分析は、実際にはそれが何を意味するのか理解するのが難しいにもかかわらず、ある意味では「基数は数値の表現と保存に最も経済的な基数である」と主張するために時々使用される。^[4] $e$

この話題はアンダーウッド・ダドリーの『数学的奇人変人』に登場します。本書で論じられている奇人の一人は、シュタイナーの微積分問題に関する曖昧な理解に基づき、基数の選択の重要性を過度に誇張した上で、が最良の基盤であると主張しています。^[5] $e$

異なるベースの比較

基数b ₁とb ₂の値は、 Nの値が大きければ比較できる。 $E(b,N)$

{{E(b_{1},N)} \over {E(b_{2},N)}}\approx {{b_{1}{\log _{b_{1}}(N)}} \over {b_{2}{\log _{b_{2}}(N)}}}={\left({\dfrac {b_{1}\ln(N)}{\ln(b_{1})}}\right) \over \left({\dfrac {b_{2}\ln(N)}{\ln(b_{2})}}\right)}={{b_{1}\ln(b_{2})} \over {b_{2}\ln(b_{1})}}\,.

選択すると与える $e$ $b_{2}$

{{E(b)} \over {E(e)}}\approx {{b\ln(e)} \over {e\ln(b)}}={{b} \over {e\ln(b)}}\,.

2から12の累乗およびeに近い数を除く、任意の数までの様々な基数の平均を以下の表に示します。また、 eを底とする値に対する相対値も示します。任意の数のはちょうどであるため、最初のいくつかの整数については単進法が最も経済的ですが、 N が無限大になるとこの限りではありません。 $E(b,N)$ $E(1,N)$ $N$ $N$

ベースb	平均E（b、N） N = 1～6	平均E（b、N） N = 1～43	平均E（b、N） N = 1～182	平均E（b、N） N = 1から5329	${{E(b)} \over {E(e)}}$	E ( b ) /E ( e )の相対的な大きさ
1	3.5	22.0	91.5	2,665.0	$\infty$	—
2	4.7	9.3	13.3	23.0	1.0615
e	4.5	9.0	12.9	22.1	1.0000
3	5.0	9.5	13.1	22.2	1.0046
$π$	4.7	9.4	13.3	22.6	1.0096
4	6.0	10.3	14.2	23.9	1.0615
5	6.7	11.7	15.8	26.3	1.1429
6	7.0	12.4	16.7	28.3	1.2319
7	7.0	13.0	18.9	31.3	1.3234
8	8.0	14.7	20.9	33.0	1.4153
9	9.0	16.3	22.6	34.6	1.5069
10	10.0	17.9	24.1	37.9	1.5977
12	12.0	20.9	25.8	43.8	1.7765
15	15.0	25.1	28.8	49.8	2.0377
16	16.0	26.4	30.7	50.9	2.1230
20	20.0	31.2	37.9	58.4	2.4560
30	30.0	39.8	55.2	84.8	3.2449
40	40.0	43.7	71.4	107.7	3.9891
60	60.0	60.0	100.5	138.8	5.3910

三分木の効率

3進法の相対的な経済性から得られる結果の一つとして、三元探索木はデータベースの要素を検索するための効率的な戦略を提供する。^[6]同様の分析によると、平均的な顧客が聞かなければならないメニュー選択肢の数（つまり、メニューあたりの選択肢の数とメニューの階層数の積）を最小限に抑えるための大規模な電話メニューシステムの最適な設計は、メニューごとに3つの選択肢を持つことであることが示唆されている。^[1]

$d$ 進ヒープ $（d$ 進木に基づく優先キューデータ構造）において、要素を含むヒープにおける1回の操作あたりの比較回数の最悪ケースは（下位項まで）、上記と同じ式で表されます。実際には、またはを選択すると最適なパフォーマンスが得られる可能性があることが示唆されています。^[7] $n$ $d\log _{d}n$ $d=3$ $d=4$

ブライアン・ヘイズは、自動音声応答（IVR ）メニューの複雑さを測る適切な指標として、次の式を挙げている。ステップごとに結果と選択肢が提示されるツリー構造の電話メニューにおいて、メニューを巡回する時間は、（各ステップで選択肢を提示する時間）と（結果を決定するために必要な選択肢の数）の積に比例する。この分析から、このようなメニューにおけるステップごとの最適な選択肢の数は3つであることがわかる。^[1] $E(b,N)$ $n$ $r$ $r$ $\log _{r}n$

コンピューターハードウェアの効率

1950年の文献『高速計算装置』は、当時の技術を用いた特定の状況について記述している。数値の各桁は、複数の三極管で構成されるリングカウンタの状態として記憶される。真空管であれサイラトロンであれ、三極管はカウンタの中で最も高価な部品であった。基数rが約7未満の小さな基数の場合、1桁の数値にはr個の三極管が必要であった。^[8]（より大きな基数では、ENIACの10進カウンタのように、r個のフリップフロップとして配置された2個のr個の三極管が必要であった。） ^[9]

したがって、 n桁の数値レジスターにおける三極管の数はrn個です。10の⁶乗までの数値を表すには、以下の数の真空管が必要でした。

基数r	チューブN = rn
2	39.20
3	38.24
4	39.20
5	42.90
10	60.00

著者らは次のように結論づけている。

これらの仮定に基づくと、平均して基数3が最も経済的な選択であり、基数2と4が僅差でそれに続きます。もちろん、これらの仮定は近似的にしか成立せず、基数2の選択はより詳細な解析によって正当化されることが多いです。10個の三極管で10進環が得られるという楽観的な仮定を用いたとしても、基数10は基数2、3、または4の約1.5倍の計算量になります。ここで用いた議論の浅薄さにもかかわらず、これはおそらく重要な意味を持つでしょう。^[10]

参照

参考文献

^ abc Brian Hayes (2001). "Third Base". American Scientist . 89 (6): 490. doi :10.1511/2001.40.3268. 2014年1月11日時点のオリジナルよりアーカイブ。2013年7月28日閲覧。
^ シュタイナー、J. (1850)。「最高の製品とスマンデンジェダーザール」(PDF)。数学に関するジャーナル。40：208
^ ワイスタイン、エリック・W.「シュタイナーの問題」。マスワールド。
^ Wojcik, AS; Metze, G. (1971年10月). 「 $N$ 基数加算器のコストについて」. IEEE Transactions on Computers . C-20 (10). 米国電気電子学会 (IEEE): 1196– 1203. doi :10.1109/tc.1971.223105.
^ ダドリー、アンダーウッド(1992). 『数学の狂人』アメリカ数学協会. pp. 51– 52. ISBN 0-88385-507-0。
^ Bentley, Jon; Sedgewick, Bob (1998-04-01). 「Ternary Search Trees」. Dr. Dobb's Journal . UBM Tech . 2013年7月28日閲覧。
^ Tarjan, RE (1983). 「3.2. dヒープ」.データ構造とネットワークアルゴリズム. CBMS-NSF応用数学地域会議シリーズ. 第44巻.産業応用数学協会. pp. 34– 38.
^ Engineering Research Associates Staff (1950). 「3-6 r三極管カウンタ、モジュロr」. 高速コンピューティングデバイス. McGraw-Hill. pp. 22– 23. 2008年8月27日閲覧。
^ Engineering Research Associates Staff (1950). 「3-7 2 r -triode Counter, Modulo r」. 高速コンピューティングデバイス. McGraw-Hill. pp. 23– 25. 2008年8月27日閲覧。
^ Engineering Research Associates Staff (1950). 「基数選択による6-7の経済性」. 高速コンピューティングデバイス. McGraw-Hill. pp. 84– 87. 2008年8月27日閲覧。

さらに読む

SL Hurst、「多値ロジック：現状と将来」、IEEE trans. computers、Vol. C-33、No 12、pp. 1160–1179、1984年12月。
JT Butler、「VLSI 設計における多値ロジック」、IEEE Computer Society Press Technology Series、1991 年。
CM Allen、DD Givone「Allen-Givone 実装指向代数」、Computer Science and Multiple-Valued Logic: Theory and Applications、DC Rine、第 2 版、DC Rine 編、The Elsevier North-Holland、ニューヨーク、NY、1984 年、268 ～ 288 ページ。
G. Abraham、「Multiple-Valued Negative Resistance Integrated Circuits」、Computer Science and Multiple-Valued Logic: Theory and Applications、DC Rine、第 2 版、DC Rine 編、The Elsevier North-Holland、New York、NY、1984 年、394 ～ 446 ページ。

[Hayes-1] Brian Hayes (2001). "Third Base". American Scientist . 89 (6): 490. doi :10.1511/2001.40.3268. 2014年1月11日時点のオリジナルよりアーカイブ。2013年7月28日閲覧。

[2] シュタイナー、J. (1850)。「最高の製品とスマンデンジェダーザール」(PDF)。数学に関するジャーナル。40：208

[3] ワイスタイン、エリック・W.「シュタイナーの問題」。マスワールド。

[4] ^ Wojcik, AS; Metze, G. (1971年10月). 「 $N$ 基数加算器のコストについて」. IEEE Transactions on Computers . C-20 (10). 米国電気電子学会 (IEEE): 1196– 1203. doi :10.1109/tc.1971.223105.

[5] ダドリー、アンダーウッド(1992). 『数学の狂人』アメリカ数学協会. pp. 51– 52. ISBN 0-88385-507-0。

[6] Bentley, Jon; Sedgewick, Bob (1998-04-01). 「Ternary Search Trees」. Dr. Dobb's Journal . UBM Tech . 2013年7月28日閲覧。

[7] Tarjan, RE (1983). 「3.2. dヒープ」.データ構造とネットワークアルゴリズム. CBMS-NSF応用数学地域会議シリーズ. 第44巻.産業応用数学協会. pp. 34– 38.

[8] Engineering Research Associates Staff (1950). 「3-6 r三極管カウンタ、モジュロr」. 高速コンピューティングデバイス. McGraw-Hill. pp. 22– 23. 2008年8月27日閲覧。

[9] Engineering Research Associates Staff (1950). 「3-7 2 r -triode Counter, Modulo r」. 高速コンピューティングデバイス. McGraw-Hill. pp. 23– 25. 2008年8月27日閲覧。

[10] Engineering Research Associates Staff (1950). 「基数選択による6-7の経済性」. 高速コンピューティングデバイス. McGraw-Hill. pp. 84– 87. 2008年8月27日閲覧。