最適な基数の選択

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

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

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

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

bとN の両方が正の整数である場合、その量は、基数 bで数N を表すために必要な桁数に基数bを掛けたものに等しくなります。^[1]したがって、この量は、各「桁」のコストがbに比例する場合、基数bで数N を格納または処理するコストを測定します。したがって、平均値が低い基数は、ある意味では、平均値が高い基数よりも効率的です。 ${\displaystyle E(b,N)}$${\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 個の数字面があるコンビネーションロックまたはタリーカウンターによって表されると想定すると、 は、 0 からNまでの任意の整数を包括的に表すために必要な数字面の総数です。 ${\displaystyle 0,1,...,b-1}$${\displaystyle \lfloor \log _{b}(N)+1\rfloor }$${\displaystyle E(b,N)}$

Nが大きい場合の量は次のように近似できます。 ${\displaystyle E(b,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\,.}$

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

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

b ₂にeを選択すると、

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

2 から 12 の累乗およびeに近い数を避ける、いくつかの任意の数までのさまざまな底の平均が、下の表に示されています。また、底eの値に対する相対値も示されています。 任意の数の はちょうど であるため、最初のいくつかの整数については単項が最も経済的ですが、 N が無限大に増加する と、これは当てはまらなくなります。${\displaystyle E(b,N)}$${\displaystyle E(1,N)}$${\displaystyle N}$${\displaystyle N}$

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

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

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

1950 年の文献「高速計算装置」では、当時の技術を使った特定の状況が説明されています。数字の各桁は、複数の三極管で構成されたリング カウンタの状態として保存されます。真空管であれサイラトロンであれ、三極管はカウンタの中で最も高価な部品でした。約 7 未満の小さな基数rの場合、1 つの桁にr個の三極管が必要でした。^[4] (より大きな基数では、 ENIACの 10 進カウンタのように、r個のフリップフロップとして配置された2 個のr個の三極管が必要でした。) ^[5]

したがって、 n桁の数値レジスタ内の三極管の数はrnです。 10 ⁶までの数値を表すには、次の数の真空管が必要でした。

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

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

• 三進法コンピュータ
• 記数法の一覧

• 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 実装指向代数」、コンピュータサイエンスと多値ロジック: 理論とアプリケーション、DC Rine、第 2 版、DC Rine 編、The Elsevier North-Holland、ニューヨーク、NY、1984 年、268 ～ 288 ページ。
• G. Abraham、「多値負性抵抗集積回路」、コンピュータサイエンスと多値ロジック：理論とアプリケーション、DC Rine、第 2 版、DC Rine 編、The Elsevier North-Holland、ニューヨーク、NY、1984 年、394 ～ 446 ページ。