La economía de la raíz de un número en una base particular (o raíz ) 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). Ésta es una de las diversas propuestas que se han hecho para cuantificar los costos relativos de utilizar diferentes radicales en la representación de números, especialmente en sistemas informáticos.
La economía radical también tiene implicaciones para la estructura organizativa, la creación de redes y otros campos.
Definición
La economía de la raíz E ( b , N ) para cualquier número particular N en una base b dada se define como
donde usamos la función de pisoy el logaritmo en base b .
Si ambos b y N son enteros positivos, entonces la economía radixes igual al número de dígitos necesarios para expresar el número N en la base b , multiplicado por la base b . [1] Por tanto, la economía de la base mide el costo de almacenar o procesar el número N en la base b si el costo de cada "dígito" es proporcional a b . Por lo tanto, una base con una economía de radix promedio más baja es, en algunos sentidos, más eficiente que una base con una economía de radix promedio más alta.
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 2 ) 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 3 ) con una economía de base de 3 × 5 = 15; en base 36 (2S 36 ) su economía de radix es 36 × 2 = 72.
Si se imagina que el número está representado por un candado de combinación o un contador de conteo , en el que cada rueda tiene b caras de dígitos, desde y tener ruedas, luego la economía de radix es el número total de dígitos caras necesarios para representar inclusive cualquier número entero de 0 a N .
Comportamiento asintótico
La economía de radix para N grande se puede aproximar de la siguiente manera:
Economía de radix de diferentes bases
e tiene la economía de radix más baja
Aquí hay una prueba de que la base e es la base de valor real con la economía de radix promedio más baja:
Primero, tenga en cuenta que la función
es estrictamente decreciente en 1 < x < e y estrictamente creciente en x > e . Su mínimo, por lo tanto, para x> 1, ocurre en e .
A continuación, considere que
Entonces, para una constante N, tendrá un mínimo en e por la misma razón que f (x), lo que significa que e es, por lo tanto, la base con la economía de radix promedio más baja. Dado que 2 / ln (2) ≈ 2,89 y 3 / ln (3) ≈ 2,73, se deduce que 3 es la base entera con la economía de radix promedio más baja.
Comparando diferentes bases
La economía de la raíz de las bases b 1 y b 2 se puede comparar para un valor grande de N :
La elección de e para b 2 da la economía relativa a la de e por la función:
Las economías de radix promedio de varias bases hasta varios números arbitrarios (evitando la proximidad a potencias de 2 a 12 ye ) se dan en la siguiente tabla. También se muestran las economías de radix en relación con la de e . Tenga en cuenta que la economía radical 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 al infinito, también lo hace su economía relativa.
Base b Promedio E ( b , N ) N = 1 a 6
Promedio E ( b , N ) N = 1 a 43
Promedio E ( b , N ) N = 1 a 182
Promedio E ( b , N ) N = 1 hasta 5329
Tamaño relativo de
E ( b ) / E ( e )1 3,5 22,0 91,5 2.665,0 - 2 4,7 9.3 13,3 22,9 1.0615 mi 4.5 9.0 12,9 22,1 1,0000 3 5,0 9.5 13,1 22,2 1,0046 4 6.0 10,3 14,2 23,9 1.0615 5 6,7 11,7 15,8 26,3 1,1429 6 7.0 12,4 16,7 28,3 1.2319 7 7.0 13,0 18,9 31,3 1.3234 8 8.0 14,7 20,9 33,0 1.4153 9 9.0 16,3 22,6 34,6 1,5069 10 10.0 17,9 24,1 37,9 1.5977 12 12,0 20,9 25,8 43,8 1,7765 15 15.0 25,1 28,8 49,8 2.0377 dieciséis 16,0 26,4 30,7 50,9 2.1230 20 20,0 31,2 37,9 58,4 2.4560 30 30,0 39,8 55,2 84,8 3.2449 40 40,0 43,7 71,4 107,7 3.9891 60 60,0 60,0 100,5 138,8 5.3910
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 gran sistema de menú telefónico 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 de hardware informático
Los dispositivos informáticos de alta velocidad de referencia de 1950 describen 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 sean tubos de vacío o tiratrones , los triodos eran la parte más cara de un contador. Para radicales pequeños r menores de aproximadamente 7, un solo dígito requiere r triodos. [3] (Los radicales más grandes requieren 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 fue rn . Para representar números hasta 10 6 , se necesitaban los siguientes números de tubos:
Radix r Tubos N = rn 2 39,20 3 38,24 4 39,20 5 42,90 10 60,00
Los autores concluyen,
Bajo estos supuestos, el radix 3, en promedio, es la opción más económica, seguido de cerca por los radix 2 y 4. Estos supuestos son, por supuesto, sólo aproximadamente válidos, y la elección de 2 como radix se justifica con frecuencia en más 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 es probablemente 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 un sistema de base 4". [6]
La codificación binaria tiene una ventaja notable sobre todos los demás sistemas: mayor inmunidad al ruido. Es menos probable que las fluctuaciones aleatorias de voltaje generen una señal errónea, y los circuitos se pueden construir con tolerancias de voltaje más amplias y aún así representar valores inequívocos con precisión.
Ver también
Referencias
- ↑ a b Brian Hayes (2001). "Tercera Base" . Científico estadounidense . 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 .
- ^ 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 .
- ^ Personal de Investigadores Asociados en Ingeniería (1950). "3-6 El contador de triodos r , módulo r ". Dispositivos informáticos de alta velocidad . McGraw-Hill. págs. 22-23 . Consultado el 27 de agosto de 2008 .
- ^ Personal de Investigadores Asociados en Ingeniería (1950). "3-7 El contador de 2 triodos r , módulo r ". Dispositivos informáticos de alta velocidad . McGraw-Hill. págs. 23-25 . Consultado el 27 de agosto de 2008 .
- ^ Personal de Investigadores Asociados en Ingeniería (1950). "6-7 Economía lograda por Radix Choice". Dispositivos informáticos de alta velocidad . McGraw-Hill. págs. 84–87 . Consultado el 27 de agosto de 2008 .
- ^ Personal de Investigadores Asociados 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 trans. computadoras , vol. C-33, No 12, págs. 1160-1179, diciembre de 1984.
- JT Butler, "Lógica de valor múltiple en el diseño VLSI", Serie de tecnología de prensa de IEEE Computer Society, 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 Valor Múltiple: 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 valor múltiple", en Ciencias de la computación y lógica de valor múltiple: teoría y aplicaciones , DC Rine, segunda edición, DC Rine, ed., The Elsevier North-Holland, Nueva York, NY, 1984. págs. 394–446.