Economía radical

Número de dígitos necesarios para expresar un número en una base particular

La economía de base de un número en una base particular (o base ) es el número de dígitos necesarios para expresarlo en esa base, multiplicado por la base (el número de valores posibles que podría tener cada dígito). Esta es una de varias propuestas que se han hecho para cuantificar los costos relativos del uso de diferentes raíces para representar números, especialmente en sistemas informáticos.

La economía Radix también tiene implicaciones para la estructura organizacional, las redes y otros campos.

Definición

La economía de base E ( b , N ) para cualquier número particular N en una base b dada se define como

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

donde usamos la función piso y el ${\displaystyle \lfloor \rfloor }$logaritmo en base b . ${\displaystyle \log _{b}}$

Si tanto b como N son enteros positivos, entonces la economía de base es igual al número de dígitos necesarios para expresar el número N en base b , multiplicado por base b . ^[1] La economía de base mide así el costo de almacenar o procesar el número N en base b si el costo de cada "dígito" es proporcional a b . Por lo tanto, una base con una economía de base promedio más baja es, en algunos sentidos, más eficiente que una base con una economía de base promedio más alta. ${\displaystyle E(b,N)}$

Por ejemplo, 100 en decimal tiene tres dígitos, por lo que su economía de base es 10×3 = 30; su representación binaria tiene siete dígitos (1100100 ₂ ) por lo que tiene economía de base 2×7 = 14 en base 2; en base 3 su representación tiene cinco dígitos (10201 ₃ ) con una economía de base de 3×5 = 15; en base 36 (2S ₃₆ ) su economía de base es 36×2 = 72.

Si se imagina que el número está representado por una cerradura de combinación o un contador de cuentas , en el que cada rueda tiene b caras de dígitos, de y con ruedas, entonces la economía de base es el número total de caras de dígitos necesarias para representar inclusive cualquier número entero a partir de 0. a N.​ ${\displaystyle 0,1,...,b-1}$ ${\displaystyle \lfloor \log _{b}(N)+1\rfloor }$ ${\displaystyle b\lfloor \log _{b}(N)+1\rfloor }$

Comportamiento asintótico

La economía de base para N grande se puede aproximar de la siguiente manera:

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

La economía de base asintóticamente mejor se obtiene para la base 3, ya que alcanza un mínimo para en los números enteros positivos: ${\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\,.}$

Para base 10 tenemos:

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

Comparando diferentes bases

La economía de base de las bases b ₁ y b ₂ se puede comparar para un valor grande de 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})}}\,.}$

Elegir e para b ₂ da la economía relativa a la de e mediante la función:

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

En la siguiente tabla se muestran las economías de base promedio de varias bases hasta varios números arbitrarios (evitando la proximidad a potencias de 2 a 12 ye ). También se muestran las economías de base en relación con la de e . Tenga en cuenta que la economía de base de cualquier número en base 1 es ese número, lo que lo convierte en el más económico para los primeros números enteros, pero a medida que N sube hasta el infinito, también lo hace su economía relativa.

Eficiencia del árbol ternario

Un resultado de la economía relativa de la base 3 es que los árboles de búsqueda ternarios ofrecen una estrategia eficiente para recuperar elementos de una base de datos. ^[2] Un análisis similar sugiere que el diseño óptimo de un sistema de menú telefónico grande para minimizar el número de opciones de menú que el cliente promedio debe escuchar (es decir, el producto del número de opciones por menú y el número de niveles de menú) es tener tres opciones por menú. ^[1]

Eficiencias del hardware informático

La referencia de 1950 Dispositivos informáticos de alta velocidad describe una situación particular que utiliza tecnología contemporánea. Cada dígito de un número se almacenaría como el estado de un contador en anillo compuesto por varios triodos . Ya fueran tubos de vacío o tiratrones , los triodos eran la parte más cara de un contador. Para radices pequeñas r menores que aproximadamente 7, un solo dígito requería r triodos. ^[3] (Las raíces más grandes requerían 2 r triodos dispuestos como r flip-flops , como en los contadores decimales de ENIAC ). ^[4]

Entonces, el número de triodos en un registro numérico con n dígitos era rn . Para representar números hasta 10 ⁶ , se necesitaban los siguientes números de tubos:

Los autores concluyen,

Según estos supuestos, la base 3, en promedio, es la elección más económica, seguida de cerca por las raíces 2 y 4. Por supuesto, estas suposiciones sólo son válidas aproximadamente, y la elección de 2 como base con frecuencia se justifica por razones más amplias. análisis completo. Incluso con la suposición optimista de que 10 triodos producirán un anillo decimal, la base 10 conduce a aproximadamente una vez y media la complejidad de la base 2, 3 o 4. Esto probablemente sea significativo a pesar de la naturaleza superficial del argumento utilizado aquí. ^[5]

Otros criterios

En otra aplicación, los autores de High-Speed ​​Computing Devices consideran la velocidad con la que se puede enviar un número codificado como una serie de pulsos de voltaje de alta frecuencia. Para esta aplicación, la compacidad de la representación es más importante que en el ejemplo de almacenamiento anterior. Concluyen: "Se puede obtener un ahorro del 58 por ciento al pasar de un sistema binario a uno ternario. Se obtiene una ganancia porcentual menor al pasar de un sistema de base 3 a uno de base 4". ^[6]

La codificación binaria tiene una ventaja notable sobre todos los demás sistemas: una mayor inmunidad al ruido. Es menos probable que las fluctuaciones aleatorias de voltaje generen una señal errónea, y los circuitos pueden construirse con tolerancias de voltaje más amplias y aún así representar valores inequívocos con precisión.

Ver también

• computadora ternaria
• Lista de sistemas de numeración

Referencias

1. Brian Hayes (2001). "Tercera base". Científico americano . 89 (6): 490. doi :10.1511/2001.40.3268. Archivado desde el original el 11 de enero de 2014 . Consultado el 28 de julio de 2013 .
2. Bentley, Jon; Sedgewick, Bob (1 de abril de 1998). "Árboles de búsqueda ternarios". Diario del Dr. Dobb . Tecnología UBM . Consultado el 28 de julio de 2013 .
3. Personal de asociados de investigación en ingeniería (1950). "3-6 El contador del triodo r , Módulo r ". Dispositivos informáticos de alta velocidad. McGraw-Hill. págs. 22-23 . Consultado el 27 de agosto de 2008 .
4. Personal de asociados de investigación en ingeniería (1950). "3-7 El contador de 2 r -triodos, Módulo r ". Dispositivos informáticos de alta velocidad. McGraw-Hill. págs. 23-25 . Consultado el 27 de agosto de 2008 .
5. Personal de asociados de investigación en ingeniería (1950). "Economía 6-7 lograda por Radix Choice". Dispositivos informáticos de alta velocidad. McGraw-Hill. págs. 84–87 . Consultado el 27 de agosto de 2008 .
6. Personal de asociados de investigación en ingeniería (1950). "16-2 Nuevas técnicas". Dispositivos informáticos de alta velocidad. McGraw-Hill. págs. 419–421 . Consultado el 27 de agosto de 2008 .

Otras lecturas

• SL Hurst, "Lógica de valores múltiples: su estado y su futuro", IEEE trad. computadoras , vol. C-33, núm. 12, págs. 1160-1179, diciembre de 1984.
• JT Butler, "Lógica de valores múltiples en diseño VLSI", Serie de tecnología de prensa de IEEE Computer Society, 1991.
• CM Allen, DD Givone “The Allen-Givone Implementation Oriented Algebra”, en Computer Science and Multiple-Valued Logic: Theory and Applications , DC Rine, segunda edición, DC Rine, ed., The Elsevier North-Holland, Nueva York, NY , 1984. págs. 268–288.
• G. Abraham, "Multiple-Valued Negative Resistance Integrated Circuits", en Computer Science and Multiple-Valued Logic: Theory and Applications , DC Rine, segunda edición, DC Rine, ed., The Elsevier North-Holland, Nueva York, NY, 1984, págs. 394–446.