Ekonomika Radix - Radix economy - Wikipedia

The radix ekonomika čísla v konkrétní základně (nebo základ ) je počet číslice potřeboval to vyjádřit v této základně, vynásobené základnou (počet možných hodnot, které by každá číslice mohla mít). Toto je jeden z různých návrhů, které byly provedeny ke kvantifikaci relativních nákladů na použití různých radic při reprezentaci čísel, zejména v počítačových systémech.

Ekonomika Radix má také důsledky pro organizační strukturu, vytváření sítí a další pole.

Definice

The radix ekonomika E(b,N) pro jakékoli konkrétní číslo N v dané základně b je definován jako

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

kde používáme funkce podlahy ${ displaystyle lfloor rfloor}$ a základna-b logaritmus ${ displaystyle log _ {b}}$ .

Pokud obojí b a N jsou kladná celá čísla, pak radixová ekonomika ${ displaystyle E (b, N)}$ se rovná počtu číslice potřebné k vyjádření čísla N v základně b, vynásobeno základnou b.^[1] Ekonomika radixu tak měří náklady na ukládání nebo zpracování čísla N v základně b pokud jsou náklady na každou "číslici" úměrné b. Základna s nižší průměrnou ekonomikou radixu je proto v některých smyslech efektivnější než základna s vyšší průměrnou ekonomikou radixu.

Například, 100 v desetinný má tři číslice, takže jeho radixová ekonomika je 10 × 3 = 30; jeho binární reprezentace má sedm číslic (1100100₂) má tedy radixovou ekonomiku 2 × 7 = 14 v základně 2; v základna 3 jeho reprezentace má pět číslic (10201₃) s radixovou ekonomikou 3 × 5 = 15; v základně 36 (2S₃₆) jeho radixová ekonomika je 36 × 2 = 72.

Pokud je číslo představováno jako a číselný zámek nebo a počítadlo, ve kterém má každé kolo b číslice, od ${ displaystyle 0,1, ..., b-1}$ a mít ${ displaystyle lfloor log _ {b} (N) +1 rfloor}$ kola, pak ekonomika radix ${ Displaystyle b lfloor log _ {b} (N) +1 rfloor}$ je celkový počet digitálních ploch potřebných k inkluzivnímu reprezentaci jakéhokoli celého čísla od 0 do N.

Asymptotické chování

Radixová ekonomika pro velké N lze aproximovat takto:

{ displaystyle E (b, N) = b lfloor log _ {b} (N) +1 rfloor cca b log _ {b} (N) = {b over ln (b)} ln (N)}

{ displaystyle {E (b, N) nad ln (N)} přibližně {b nad ln (b)}}

Radixová ekonomika různých bází

E má nejnižší radixovou ekonomiku

Tady je důkaz E je nemovitý-hodinová základna s nejnižší průměrnou ekonomikou radixu:

Nejprve si povšimněte této funkce

{ displaystyle f (x) = { frac {x} { ln (x)}} ,}

se přísně snižuje na 1 < X < E a přísně roste dál X > E. Jeho minimum tedy pro x> 1 nastává v E.

Dále to zvažte

{ displaystyle {E (b, N)} přibližně {b { log _ {b} (N)}} = {b { ln (N) nad ln (b)}}}

Pak pro konstantní N, ${ displaystyle {E (b, N)}}$ bude mít minimum na E ze stejného důvodu to dělá f (x), což znamená, že e je tedy základna s nejnižší průměrnou ekonomikou radixu. Protože 2 / ln (2) ≈ 2,89 a 3 / ln (3) ≈ 2,73, vyplývá z toho, že 3 je celé číslo základna s nejnižší průměrnou ekonomikou radixu.

Porovnání různých základen

Radixová ekonomika základen b₁ a b₂ lze porovnat pro velkou hodnotu N:

{ displaystyle {{E (b_ {1}, N)} nad {E (b_ {2}, N)}} přibližně {{b_ {1} { log _ {b_ {1}} (N) }} přes {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})} nad {b_ {2} ln (b_ {1})}} ,.}

Výběr E pro b₂ dává ekonomiku ve srovnání s E funkcí:

{ displaystyle {{E (b)} nad {E (e)}} přibližně {{b ln (e)} nad {e ln (b)}} = {{b} nad {e ln (b)}} ,}

Průměrné radixové ekonomiky různých bází až do několika libovolných čísel (vyhýbání se blízkosti sil 2 až 12 a E) jsou uvedeny v tabulce níže. Zobrazeny jsou také ekonomiky radixů ve srovnání s ekonomikami E. Všimněte si, že radixová ekonomika jakéhokoli čísla v základně 1 je toto číslo, což je nejekonomičtější pro prvních několik celých čísel, ale jako N stoupá do nekonečna, stejně tak i jeho relativní ekonomika.

Základna b	Prům. E(b,N) N = 1 až 6	Prům. E(b,N) N = 1 až 43	Prům. E(b,N) N = 1 až 182	Prům. E(b,N) N = 1 až 5329	${ displaystyle {{E (b)} nad {E (e)}}}$	Relativní velikost E (b )/E (E )
1	3.5	22.0	91.5	2,665.0	${ displaystyle infty}$	—
2	4.7	9.3	13.3	22.9	1.0615	1.0615
E	4.5	9.0	12.9	22.1	1.0000	1
3	5.0	9.5	13.1	22.2	1.0046	1.0046
4	6.0	10.3	14.2	23.9	1.0615	1.0615
5	6.7	11.7	15.8	26.3	1.1429	1.1429
6	7.0	12.4	16.7	28.3	1.2319	1.2319
7	7.0	13.0	18.9	31.3	1.3234	1.3234
8	8.0	14.7	20.9	33.0	1.4153	1.4153
9	9.0	16.3	22.6	34.6	1.5069	1.5069
10	10.0	17.9	24.1	37.9	1.5977	1.5977
12	12.0	20.9	25.8	43.8	1.7765	1.7765
15	15.0	25.1	28.8	49.8	2.0377	2.0377
16	16.0	26.4	30.7	50.9	2.1230	2.123
20	20.0	31.2	37.9	58.4	2.4560	2.456
30	30.0	39.8	55.2	84.8	3.2449	3.2449
40	40.0	43.7	71.4	107.7	3.9891	3.9891
60	60.0	60.0	100.5	138.8	5.3910	5.391

Účinnost ternárního stromu

Jedním z výsledků relativní ekonomiky základny 3 je to ternární vyhledávací stromy nabídnout efektivní strategii pro načítání prvků databáze.^[2] Podobná analýza naznačuje, že optimální design velkého systém telefonního menu minimalizovat počet možností nabídky, které musí průměrný zákazník poslouchat (tj. součin počtu možností v nabídce a počtu úrovní nabídky), je mít tři možnosti v nabídce.^[1]

Účinnost počítačového hardwaru

Odkaz z roku 1950 Vysokorychlostní výpočetní zařízení popisuje konkrétní situaci pomocí současné technologie. Každá číslice čísla by byla uložena jako stav a počítadlo prstenů složený z několika triody. Zda vakuové trubky nebo tyratrony, triody byly nejdražší částí počítadla. Pro malé radices r méně než přibližně 7, je vyžadována jedna číslice r triody.^[3] (Jsou zapotřebí větší radice 2r triody uspořádané jako r žabky, jako v ENIAC počítadla desetinných míst.)^[4]

Takže počet triod v číselném registru s n číslice byla rn. Aby bylo možné představovat čísla až 10⁶, byl zapotřebí následující počet zkumavek:

Základ r	Trubky N = rn
2	39.20
3	38.24
4	39.20
5	42.90
10	60.00

Autoři uzavírají,

Za těchto předpokladů je radix 3 v průměru nejekonomičtější volbou, těsně následovanou radices 2 a 4. Tyto předpoklady jsou samozřejmě pouze přibližně platné a volba 2 jako radixu je často oprávněna na více kompletní analýza. I s optimistickým předpokladem, že 10 triod získá desetinný kruh, vede radix 10 k přibližně jeden a půlnásobku složitosti radix 2, 3 nebo 4. To je pravděpodobně významné navzdory povrchní povaze zde použitého argumentu.^[5]

Další kritéria

V jiné aplikaci autoři Vysokorychlostní výpočetní zařízení rychlost, s jakou může být kódované číslo odesláno, považujte za sérii vysokofrekvenčních napěťových pulzů. Pro tuto aplikaci je kompaktnost zobrazení důležitější než ve výše uvedeném příkladu ukládání. Došli k závěru: „Úsporu 58 procent lze dosáhnout přechodem z binárního do ternárního systému. Menší procentní zisk se dosáhne přechodem ze systému radix 3 do systému radix 4.“^[6]

Binární kódování má oproti všem ostatním systémům významnou výhodu: větší odolnost proti rušení. Je nepravděpodobné, že by náhodné kolísání napětí generovalo chybný signál, a obvody mohou být sestaveny s širšími tolerancemi napětí a stále přesně představují jednoznačné hodnoty.

Viz také

Reference

^ ^A ^b Brian Hayes (2001). "Třetí základna". Americký vědec. 89 (6): 490. doi:10.1511/2001.40.3268. Archivovány od originál dne 11.01.2014. Citováno 2013-07-28.
^ Bentley, Jon; Sedgewick, Bob (01.04.1998). „Ternární vyhledávací stromy“. Dr. Dobb's Journal. UBM Tech. Citováno 2013-07-28.
^ Zaměstnanci společnosti Research Research Associates (1950). „3-6 r-triodový čítač, Modulo r". Vysokorychlostní výpočetní zařízení. McGraw-Hill. s. 22–23. Citováno 2008-08-27.
^ Zaměstnanci společnosti Research Research Associates (1950). „3-7 The 2r-triodový čítač, Modulo r". Vysokorychlostní výpočetní zařízení. McGraw-Hill. 23–25. Citováno 2008-08-27.
^ Zaměstnanci společnosti Research Research Associates (1950). "Ekonomika 6-7 dosažená Radix Choice". Vysokorychlostní výpočetní zařízení. McGraw-Hill. str. 84–87. Citováno 2008-08-27.
^ Zaměstnanci společnosti Research Research Associates (1950). „16-2 Nové techniky“. Vysokorychlostní výpočetní zařízení. McGraw-Hill. 419–421. Citováno 2008-08-27.

Další čtení

S.L. Hurst, „Vícehodnotová logika - její stav a budoucnost“, IEEE trans. počítače, Sv. C-33, č. 12, s. 1160–1179, DEC 1984.
J. T. Butler, „Vícehodnotová logika v designu VLSI,“ IEEE Computer Society Press Technology Series, 1991.
CM. Allen, D.D. Givone „Algebra zaměřená na implementaci Allen-Givone“, v Informatika a vícehodnotová logika: Teorie a aplikace, D.C. Rine, druhé vydání, D.C. Rine, ed., The Elsevier North-Holland, New York, NY, 1984. str. 268–288.
G. Abraham, „Vícehodnotové integrované obvody se záporným odporem“, in Informatika a vícehodnotová logika: Teorie a aplikace, D.C. Rine, druhé vydání, D.C. Rine, ed., The Elsevier North-Holland, New York, NY, 1984. str. 394–446.

[Hayes-1] A ^b Brian Hayes (2001). "Třetí základna". Americký vědec. 89 (6): 490. doi:10.1511/2001.40.3268. Archivovány od originál dne 11.01.2014. Citováno 2013-07-28.

[2] Bentley, Jon; Sedgewick, Bob (01.04.1998). „Ternární vyhledávací stromy“. Dr. Dobb's Journal. UBM Tech. Citováno 2013-07-28.

[3] Zaměstnanci společnosti Research Research Associates (1950). „3-6 r-triodový čítač, Modulo r". Vysokorychlostní výpočetní zařízení. McGraw-Hill. s. 22–23. Citováno 2008-08-27.

[4] Zaměstnanci společnosti Research Research Associates (1950). „3-7 The 2r-triodový čítač, Modulo r". Vysokorychlostní výpočetní zařízení. McGraw-Hill. 23–25. Citováno 2008-08-27.

[5] Zaměstnanci společnosti Research Research Associates (1950). "Ekonomika 6-7 dosažená Radix Choice". Vysokorychlostní výpočetní zařízení. McGraw-Hill. str. 84–87. Citováno 2008-08-27.

[6] Zaměstnanci společnosti Research Research Associates (1950). „16-2 Nové techniky“. Vysokorychlostní výpočetní zařízení. McGraw-Hill. 419–421. Citováno 2008-08-27.

[1]

[2]

[3]

[4]

[5]

[6]