Economia Radix - Radix economy

A economia de raiz de um número em uma base particular (ou raiz ) é o número de dígitos necessários para expressá-lo naquela base, multiplicado pela base (o número de valores possíveis que cada dígito poderia ter). Esta é uma das várias propostas que foram feitas para quantificar os custos relativos do uso de diferentes radices na representação de números, especialmente em sistemas de computador.

A economia da Radix também tem implicações para a estrutura organizacional, redes e outros campos.

Definição

A economia de raiz E ( b , N ) para qualquer número particular N em uma determinada base b é definida como

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

onde usamos a função floor ${\ displaystyle \ lfloor \ rfloor}$ e o logaritmo de base-b . ${\ displaystyle \ log _ {b}}$

Se b e N são inteiros positivos, então a economia da raiz é igual ao número de dígitos necessários para expressar o número N na base b , multiplicado pela base b . A economia de raiz mede, portanto, o custo de armazenamento ou processamento do número N na base b se o custo de cada "dígito" for proporcional a b . Uma base com uma economia de raiz média mais baixa é, portanto, em alguns sentidos, mais eficiente do que uma base com uma economia de raiz média mais alta. ${\ displaystyle E (b, N)}$

Por exemplo, 100 em decimal tem três dígitos, então sua economia de raiz é 10 × 3 = 30; sua representação binária tem sete dígitos (1100100 ₂ ), portanto, tem economia de raiz 2 × 7 = 14 na base 2; na base 3 sua representação tem cinco dígitos (10201 ₃ ) com uma economia de raiz de 3 × 5 = 15; na base 36 (2S ₃₆ ), sua economia de raiz é 36 × 2 = 72.

Se o número é imaginado como sendo representado por uma fechadura de combinação ou um contador de contagem , em que cada roda tem b faces de dígitos, de e tendo rodas, então a economia de raiz é o número total de faces de dígitos necessárias para representar inclusivamente qualquer inteiro a partir de 0 para N . ${\ displaystyle 0,1, ..., b-1}$ ${\ displaystyle \ lfloor \ log _ {b} (N) +1 \ rfloor}$ ${\ displaystyle b \ lfloor \ log _ {b} (N) +1 \ rfloor}$

Comportamento assintótico

A economia de raiz para N grande pode ser aproximada da seguinte forma:

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

A melhor economia de raiz assintoticamente é obtida para a base 3, uma vez que atinge um mínimo para : ${\ 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)} \ aproximadamente 2.88539 \ ,.}

Para a base 10, temos:

{\ displaystyle \! \! {10 \ over \ ln (10)} \ aproximadamente 4.34294 \ ,.}

Eficiência da árvore ternária

Um resultado da economia relativa da base 3 é que as árvores de busca ternárias oferecem uma estratégia eficiente para recuperar elementos de um banco de dados. Uma análise semelhante sugere que o design ideal de um grande sistema de menu de telefone para minimizar o número de opções de menu que o cliente médio deve ouvir (ou seja, o produto do número de opções por menu e o número de níveis de menu) é ter três escolhas por menu.

Eficiências de hardware de computador

A referência 1950 High-Speed Computing Devices descreve uma situação particular usando tecnologia contemporânea. Cada dígito de um número seria armazenado como o estado de um contador de anéis composto de vários triodos . Sejam tubos de vácuo ou tiratrons , os triodos eram a parte mais cara de um contador. Para rádios pequenos, r menos do que cerca de 7, um único dígito exigia r tríodos. (Radices maiores exigiam 2 r triodos arranjados como r flip-flops , como nos contadores decimais do ENIAC .)

Portanto, o número de triodos em um registro numérico com n dígitos era rn . A fim de representar números até 10 ⁶ , os seguintes números de tubos foram necessários:

Radix r	Tubos N = rn
2	39,20
3	38,24
4	39,20
5	42,90
10	60,00

Os autores concluem,

Sob essas suposições, o radical 3, em média, é a escolha mais econômica, seguido de perto pelos radices 2 e 4. Essas suposições são, é claro, apenas aproximadamente válidas, e a escolha de 2 como um radical é freqüentemente justificada em mais análise completa. Mesmo com a suposição otimista de que 10 triodos produzirão um anel decimal, o radical 10 leva a cerca de uma vez e meia a complexidade do radical 2, 3 ou 4. Isso é provavelmente significativo, apesar da natureza superficial do argumento usado aqui.

Outros critérios

Em outra aplicação, os autores de High-Speed Computing Devices consideram a velocidade com que um número codificado pode ser enviado como uma série de pulsos de tensão de alta frequência. Para esta aplicação, a compactação da representação é mais importante do que no exemplo de armazenamento acima. Eles concluem: "Uma economia de 58 por cento pode ser obtida passando de um sistema binário para um ternário. Um ganho percentual menor é obtido ao passar de um sistema raiz 3 para um sistema raiz 4."

A codificação binária tem uma vantagem notável sobre todos os outros sistemas: maior imunidade a ruídos. As flutuações de tensão aleatórias têm menos probabilidade de gerar um sinal errôneo e os circuitos podem ser construídos com tolerâncias de tensão mais amplas e ainda representam valores inequívocos com precisão.

Veja também

Referências

Leitura adicional

SL Hurst, "Multiple-Valued Logic-Its Status and its Future", IEEE trans. computadores , vol. C-33, No 12, pp. 1160-1179, DEZ 1984.
JT Butler, "Multiple-Valued Logic in VLSI Design," IEEE Computer Society Press Technology Series, 1991.
CM Allen, DD Givone "The Allen-Givone Implementation Oriented Algebra", em Ciência da Computação e Lógica de Valores Múltiplos: Teoria e Aplicações , DC Rine, segunda edição, DC Rine, ed., The Elsevier North-Holland, Nova York, NY , 1984. pp. 268-288.
G. Abraham, "Multiple-Valued Negative Resistance Integrated Circuits", em Computer Science and Multiple-Valued Logic: Theory and Applications , DC Rine, segunda edição, DC Rine, ed., The Elsevier North-Holland, New York, NY, 1984. pp. 394–446.

Languages

In other projects