最適な基数選択

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

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

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

床関数を使用する${\displaystyle \lfloor \rfloor }$そして底bの対数$\displaystyle \log _{b}}$。

bとNが両方とも正の整数である場合、その量は${\displaystyle E(b,N)}$は、数N をb基数で 表すのに必要な桁数にbを掛けたものに等しい。^{[ 1 ]}この量は、各「桁」のコストがbに比例する場合、数Nをb基数で保存または処理するコストを測定する。平均が低い基数${\displaystyle 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桁の面があり、${\displaystyle 0,1,...,b-1}$そして持っている${\displaystyle \lfloor \log _{b}(N)+1\rfloor }$車輪、それから${\displaystyle E(b,N)}$は、0からNまでの任意の整数を包括的に表現するために必要な数字面の総数です。

数量${\displaystyle E(b,N)}$Nが大きい場合、次のように近似できます。

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

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

漸近的に最良の値は、基数3の場合に得られます。${\displaystyle b \over \ln(b)}$最小値に達する${\displaystyle b=3}$正の整数において：

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

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

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

10進数では、次のようになります。

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

値${\displaystyle E(b,N)}$Nの値が大きい場合、_塩基b1とb2を_比較することができます。

$${\displaystyle {{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})}}\,.}$$

選択する${\displaystyle e}$のために${\displaystyle b_{2}}$与える

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

平均${\displaystyle E(b,N)}$様々な基数（2～12のべき乗およびeのべき乗に近接しないもの）の値が以下の表に示されています。また、基数eに対する相対値も示されています。 ${\displaystyle E(1,N)}$任意の数${\displaystyle N}$はただ${\displaystyle N}$そのため、最初のいくつかの整数では単項演算子が最も経済的ですが、Nが無限大に近づくとこれはもはや成り立ちません。

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

d進ヒープ（d進木に基づく優先度キューデータ構造）では、ヒープ内の操作ごとの比較の最悪ケース数は、${\displaystyle n}$要素は${\displaystyle d\log _{d}n}$（低次の項まで）上記と同じ式。${\displaystyle d=3}$または${\displaystyle d=4}$実際には最適なパフォーマンスを発揮する可能性がある。^{[ 7 ]}

ブライアン・ヘイズは次のように示唆している${\displaystyle E(b,N)}$インタラクティブ音声応答メニューの複雑さの適切な尺度となる可能性がある。ツリー構造の電話メニューでは${\displaystyle n}$結果と${\displaystyle r}$ステップごとの選択肢数、メニューをたどる時間は、${\displaystyle r}$（各ステップで選択肢を提示する時間）${\displaystyle \log _{r}n}$（結果を決定するために必要な選択の数）。この分析から、このようなメニューにおける各ステップでの最適な選択数は3つであることがわかる。^{[ 1 ]}

1950年の参考文献「高速コンピューティングデバイス」では、当時の技術を用いた特定の状況が説明されています。数値の各桁は、複数の三極管で構成されるリングカウンタの状態として格納されます。真空管であろうとサイラトロンであろうと、三極管はカウンタの中で最も高価な部分でした。基数rが約7未満の場合、1桁にはr個の三極管が必要でした。^{[ 8 ]} （基数が大きい場合は、 ENIACの10進カウンタのように、r個のフリップフロップとして配置された2r個の三極管が必要でした。） ^{[ 9 ]}

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

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

これらの仮定の下では、平均的に基数 3 が最も経済的な選択肢であり、基数 2 と 4 がそれに僅差で続きます。もちろん、これらの仮定は近似的にしか有効ではなく、基数 2 の選択はより完全な分析によって正当化されることがよくあります。10 個の三極管で 10 進リングが得られるという楽観的な仮定でも、基数 10 は基数 2、3、または 4 の約 1.5 倍の複雑さになります。ここで使用されている議論の浅い性質にもかかわらず、これはおそらく重要なことです。^{[ 10 ]}

• 三値計算機
• 数字体系の一覧

• 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「アレン・ギヴォーン実装指向代数」、DC Rine編『コンピュータサイエンスと多値論理：理論と応用』 第2版、The Elsevier North-Holland、ニューヨーク、NY、1984年、pp. 268 – 288。
• G. Abraham、「多値負抵抗集積回路」、DC Rine編『コンピュータサイエンスと多値論理：理論と応用』 第2版、The Elsevier North-Holland、ニューヨーク、NY、1984年、 394 ～ 446ページ。