Elección de radix óptima

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

En matemáticas y ciencias de la computación, la elección óptima del radio es el problema de elegir la base, o radix , que sea más adecuada para representar números. Se han hecho varias propuestas para cuantificar los costos relativos de usar diferentes bases para representar números, especialmente en sistemas informáticos. Una fórmula es la cantidad de dígitos necesarios para expresarlo en esa base, multiplicada por la base (la cantidad de valores posibles que podría tener cada dígito). Esta expresión también surge en cuestiones relacionadas con la estructura organizacional, las redes y otros campos.

Definición

El coste de representar un número N en una base b dada se puede definir como

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

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

Si tanto b como N son números enteros positivos, entonces la cantidad es igual al número de dígitos necesarios para expresar el número N en base b , multiplicado por la base b . ^[1] Esta cantidad mide entonces 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 un promedio más bajo es, en algunos sentidos, más eficiente que una base con un valor promedio más alto. ${\displaystyle E(b,N)}$ ${\displaystyle E(b,N)}$

Por ejemplo, 100 en decimal tiene tres dígitos, por lo que su costo de representación es 10×3 = 30, mientras que su representación binaria tiene siete dígitos (1100100 ₂ ), por lo que el cálculo análogo da 2×7 = 14. Asimismo, en base 3 su representación tiene cinco dígitos (10201 ₃ ), para un valor de 3×5 = 15, y en base 36 (2S ₃₆ ) se encuentra 36×2 = 72.

Si se imagina que el número se representa mediante una cerradura de combinación o un contador de recuento , en el que cada rueda tiene b caras de dígitos, de y que tienen ruedas, entonces es el número total de caras de dígitos necesarias para representar de manera inclusiva cualquier número entero de 0 a N. ${\displaystyle 0,1,...,b-1}$ ${\displaystyle \lfloor \log _{b}(N)+1\rfloor }$ ${\displaystyle E(b,N)}$

Comportamiento asintótico

La cantidad para un N grande se puede aproximar de la siguiente manera: ${\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)}.}$

El mejor valor asintóticamente 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 la base 10, tenemos:

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

Comparando diferentes bases

Los valores de las bases b ₁ y b ₂ pueden compararse para un valor grande de 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})}}\,.}$

Al elegir e para b ₂ se obtiene

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

En la tabla siguiente se dan los promedios de varias bases hasta varios números arbitrarios (evitando la proximidad a potencias de 2 a 12 y e ). También se muestran los valores relativos a la base e . de cualquier número es simplemente , lo que hace que el unario sea el más económico para los primeros números enteros, pero esto ya no se cumple a medida que N asciende hasta el infinito. ${\displaystyle E(b,N)}$ ${\displaystyle E(1,N)}$ ${\displaystyle N}$ ${\displaystyle N}$

Eficiencia del árbol ternario

Un resultado de la relativa economía 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 la cantidad de opciones de menú que el cliente promedio debe escuchar (es decir, el producto de la cantidad de opciones por menú y la cantidad de niveles de menú) es tener tres opciones por menú. ^[1]

En un montón d -ario , una estructura de datos de cola de prioridad basada en árboles d -arios, el número de comparaciones por operación en el peor de los casos en un montón que contiene elementos es (hasta los términos de orden inferior), la misma fórmula utilizada anteriormente. Se ha sugerido que elegir o puede ofrecer un rendimiento óptimo en la práctica. ^[3] ${\displaystyle n}$ ${\displaystyle d\log _{d}n}$ ${\displaystyle d=3}$ ${\displaystyle d=4}$

Brian Hayes sugiere que esta podría ser la medida adecuada para la complejidad de un menú de respuesta de voz interactiva : en un menú telefónico estructurado en árbol con resultados y opciones por paso, el tiempo para recorrer el menú es proporcional al producto de (el tiempo para presentar las opciones en cada paso) por (la cantidad de opciones que se deben elegir para determinar el resultado). A partir de este análisis, la cantidad óptima de opciones por paso en un menú de este tipo es tres. ^[1] ${\displaystyle E(b,N)}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle \log _{r}n}$

Eficiencias del hardware informático

La referencia de 1950 High-Speed ​​Computing Devices describe una situación particular utilizando tecnología contemporánea. Cada dígito de un número se almacenaría como el estado de un contador de 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 bases pequeñas r menores de aproximadamente 7, un solo dígito requería r triodos. ^[4] (Las bases más grandes requerían 2 r triodos dispuestos como flip-flops r , como en los contadores decimales de ENIAC ). ^[5]

Por lo tanto, 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:

Bajo estas suposiciones, el número de base 3 es, en promedio, la opción más económica, seguido de cerca por los números de base 2 y 4. Estas suposiciones, por supuesto, son sólo aproximadamente válidas, y la elección del número 2 como base se justifica con frecuencia en un análisis más completo. Incluso con la suposición optimista de que 10 triodos darán como resultado un anillo decimal, el número de base 10 da como resultado aproximadamente una vez y media la complejidad de los números de base 2, 3 o 4. Esto es probablemente significativo a pesar de la naturaleza superficial del argumento utilizado aquí. ^[6]

Véase también

• Computadora ternaria
• Lista de sistemas de numeración

Referencias

1. Brian Hayes (2001). "Tercera base". American Scientist . 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 . UBM Tech . Consultado el 28 de julio de 2013 .
3. Tarjan, RE (1983). "3.2. d -heaps". Estructuras de datos y algoritmos de red . Serie de conferencias regionales CBMS-NSF sobre matemáticas aplicadas. Vol. 44. Sociedad de matemáticas industriales y aplicadas . págs. 34–38.
4. Personal de Engineering Research Associates (1950). "3-6 El contador de triodo r , módulo r ". Dispositivos informáticos de alta velocidad. McGraw-Hill. págs. 22-23 . Consultado el 27 de agosto de 2008 .
5. Personal de Engineering Research Associates (1950). "3-7 El contador de 2 r -triodo, módulo r ". Dispositivos informáticos de alta velocidad. McGraw-Hill. págs. 23–25 . Consultado el 27 de agosto de 2008 .
6. Personal de Engineering Research Associates (1950). "Economía 6-7 lograda mediante elección de radix". Dispositivos informáticos de alta velocidad. McGraw-Hill. págs. 84–87 . Consultado el 27 de agosto de 2008 .

Lectura adicional

• SL Hurst, "Lógica de múltiples valores: su estatus y su futuro", IEEE trans. computers , vol. C-33, n.º 12, págs. 1160–1179, diciembre de 1984.
• JT Butler, "Lógica de múltiples valores en diseño VLSI", IEEE Computer Society Press Technology Series, 1991.
• CM Allen, DD Givone “El álgebra orientada a la implementación de Allen-Givone", en Ciencias de la computación y lógica de múltiples valores: teoría y aplicaciones , DC Rine, segunda edición, DC Rine, ed., The Elsevier North-Holland, Nueva York, NY, 1984. págs. 268–288.
• G. Abraham, "Circuitos integrados de resistencia negativa de valores múltiples", en Ciencias de la computación y lógica de valores múltiples: teoría y aplicaciones , DC Rine, segunda edición, DC Rine, ed., The Elsevier North-Holland, Nueva York, NY, 1984. págs. 394–446.