stringtranslate.com

base negativa

Se puede utilizar una base negativa (o base negativa) para construir un sistema numérico posicional no estándar . Como otros sistemas de valor posicional, cada posición tiene múltiplos del poder apropiado de la base del sistema; pero esa base es negativa, es decir, la base b es igual a −r para algún número natural r ( r ≥ 2 ).

Los sistemas de base negativa pueden acomodar los mismos números que los sistemas estándar de valor posicional, pero tanto los números positivos como los negativos se representan sin el uso de un signo menos (o, en la representación por computadora, un bit de signo ); esta ventaja se ve contrarrestada por una mayor complejidad de las operaciones aritméticas. La necesidad de almacenar la información normalmente contenida en un signo negativo a menudo resulta en que un número de base negativa sea un dígito más largo que su equivalente de base positiva.

Los nombres comunes para los sistemas numéricos posicionales de base negativa se forman anteponiendo nega- al nombre del correspondiente sistema de base positiva; por ejemplo, negadecimal (base −10) corresponde a decimal (base 10), negabinario (base −2) a binario (base 2), negaternario (base −3) a ternario (base 3) y negacuaternario (base −4) al cuaternario (base 4). [1] [2]

Ejemplo

Consideremos lo que se entiende por representación.12243 en el sistema negadecimal, cuya base b es −10:

La representación12,243 −10 (que pretende ser una notación negadecimal) es equivalente a8,163 10 en notación decimal, porque 10,000 + (−2,000) + 200 + (−40) + 3 =8.163 .

Observación

Por otro lado,−8,163 10 en decimal se escribiría9,977 −10 en negadecimal.

Historia

Las bases numéricas negativas fueron consideradas por primera vez por Vittorio Grünwald en una monografía de 1885 publicada en Giornale di Matematiche di Battaglini . [3] Grünwald proporcionó algoritmos para realizar sumas, restas, multiplicaciones, divisiones, extracción de raíces, pruebas de divisibilidad y conversión de bases. Las bases negativas fueron mencionadas más tarde de pasada por AJ Kempner en 1936 [4] y estudiadas con más detalle por Zdzisław Pawlak y A. Wakulicz en 1957. [5]

Negabinary se implementó en la primera computadora polaca BINEG (y UMC ), construida entre 1957 y 1959, basada en ideas de Z. Pawlak y A. Lazarkiewicz del Instituto de Matemáticas de Varsovia . [6] Las implementaciones desde entonces han sido raras.

zfp, un algoritmo de compresión de punto flotante del Laboratorio Nacional Lawrence Livermore , utiliza negabinario para almacenar números. Según la documentación de zfp: [7]

A diferencia de las representaciones de signo-magnitud, el bit más a la izquierda en negabinario codifica simultáneamente el signo y la magnitud aproximada de un número. Además, a diferencia del complemento a dos, los números de magnitud pequeña tienen muchos ceros a la izquierda en negabinario independientemente del signo, lo que facilita la codificación.

Notación y uso

Denotando la base como −r , cada número entero a se puede escribir de forma única como

donde cada dígito d k es un número entero de 0 a r − 1 y el dígito principal d n > 0 (a menos que n = 0 ). La expansión de base −r de a entonces viene dada por la cadena d n d n −1 ... d 1 d 0 .

Por tanto, los sistemas de base negativa pueden compararse con representaciones de dígitos con signo , como el ternario equilibrado , donde la base es positiva pero los dígitos se toman de un rango parcialmente negativo. (En la siguiente tabla, el dígito del valor −1 se escribe como un solo carácter T.)

Algunos números tienen la misma representación en base −r que en base r . Por ejemplo, los números del 100 al 109 tienen las mismas representaciones en decimal y negadecimal. Similarmente,

y está representado por 10001 en binario y 10001 en negabinario.

Algunos números con sus expansiones en un número de bases positivas y negativas correspondientes son:

Tenga en cuenta que, con la excepción del ternario balanceado negativo, las expansiones en base −r de números enteros negativos tienen un número par de dígitos, mientras que las expansiones en base −r de números enteros no negativos tienen un número impar de dígitos.

Cálculo

La expansión de base −r de un número se puede encontrar dividiendo repetidamente por −r , registrando los restos no negativos en y concatenando esos restos, comenzando con el último. Tenga en cuenta que si a /  b es c con resto d , entonces bc + d = a y por lo tanto d = abc . Para llegar a la conversión correcta, el valor de c debe elegirse de modo que d no sea negativo y sea mínimo. Para la cuarta línea del siguiente ejemplo, esto significa que

tiene que ser elegido, y no ni

Por ejemplo, para convertir 146 en decimal a negaternario:

Leyendo los restos hacia atrás obtenemos la representación negaternaria de 146 10 : 21102 –3 .

Prueba: -3 · (-3 · (-3 · (-3 · ( 2 ) + 1 ) + 1 ) + 0 ) + 2 = ((( 2  · (–3) + 1 ) · (–3) + 1 ) · (–3) + 0 ) · (–3) + 2
= 146 10 .

Leyendo los restos hacia adelante podemos obtener la representación negaternaria del primer dígito menos significativo.

Prueba: 2 + ( 0 + ( 1 + ( 1 + ( 2 ) · -3 ) · -3) · -3 ) · -3 = 146 10 .

Tenga en cuenta que en la mayoría de los lenguajes de programación , el resultado (en aritmética de enteros) de dividir un número negativo entre un número negativo se redondea hacia 0, dejando generalmente un resto negativo. En tal caso tenemos a = (− r ) c + d = (− r ) c + dr + r = (− r )( c + 1) + ( d + r ) . Porque | re | < r , ( d + r ) es el resto positivo. Por lo tanto, para obtener el resultado correcto en tal caso, las implementaciones informáticas del algoritmo anterior deben sumar 1 yr al cociente y al resto respectivamente.

Código de implementación de ejemplo

a negabinario

C#
cadena estática ToNegabinary ( int val ) { resultado de cadena = cadena . Vacío ;      mientras ( val ! = 0 ) { int resto = val % - 2 ; valor = valor / - 2 ;            si ( resto < 0 ) { resto += 2 ; valor += 1 ; }       resultado = resto . ToString () + resultado ; }    resultado de retorno ; } 
C++
auto to_negabinary ( valor int ) { std :: bitset < tamaño de ( int ) * CHAR_BIT > resultado ; std :: tamaño_t posición_bit = 0 ;            mientras ( valor ! = 0 ) { const auto div_result = std :: div ( valor , -2 );           si ( div_result . rem < 0 ) valor = div_result . " + 1 ; más valor = div_result . " ;             resultado . establecer ( posición_bit , resultado_div . rem ! = 0 );    ++ posición_bit ; }  resultado de retorno ; } 

a negaternario

C#
cadena estática Negaternario ( int val ) { resultado de cadena = cadena . Vacío ;      mientras ( val ! = 0 ) { int resto = val % - 3 ; valor = valor / - 3 ;            si ( resto < 0 ) { resto += 3 ; valor += 1 ; }       resultado = resto . ToString () + resultado ; }    resultado de retorno ; } 
Pitón
def  negaternario ( i :  int )  ->  str : """Decimal a negaternario.""" si i == 0 : dígitos = [ "0" ] más : dígitos = [] mientras que i ! = 0 : i , resto = divmod ( i , - 3 ) si resto < 0 : i , resto = i + 1 , resto + 3 dígitos . agregar ( cadena ( resto )) devolver "" . unirse ( dígitos [:: - 1 ])                                     
>>> negaternario ( 1000 ) '2212001'
ceceo común
( defun negaternario ( i ) ( if ( zerop i ) "0" ( let (( digits "" ) ( rem 0 )) ( bucle while ( not ( zerop i )) do ( progn ( multiple-value-setq ( i rem ) ( truncar i -3 )) ( cuando ( menosp rem ) ( incf i ) ( incf rem 3 )) ( setf dígitos ( concatenar 'cadena ( escribir en cadena rem ) dígitos )))) dígitos )))                                        

A cualquier base negativa

Java
importar java.util.ArrayList ; importar java.util.Collections ; pública ArrayList <Entero> basenegativa ( int entrada , int base ) { ArrayList <Entero> resultado_rev = nueva ArrayList < > ( ) ;número int = entrada ; mientras ( número ! = 0 ) { int i = número % base ; número /= base ; si ( i < 0 ) { i += Matemáticas . abdominales ( base ); número ++ ; } resultado_rev . agregar ( yo ); } devolver colecciones . revertir ( resultados_rev . clonar ()); }                                             

Lo anterior da el resultado en un ArrayList de números enteros, para que el código no tenga que manejar cómo representar una base menor que -10. Para mostrar el resultado como una cadena, se puede decidir sobre una asignación de base a caracteres. Por ejemplo:

importar java.util.stream.Collectors ; alfabeto de cadena final = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@_" ; public String toBaseString ( ArrayList <Integer> lst ) { // Lanzaría una excepción si la base supera los 64 caracteres posibles return lst . arroyo (). mapa ( n -> alfabeto [ n ] ). recopilar ( Coleccionistas . unirse ( "" )); }              
AutoLisp
( defun negabase ( num baz / dig rst ) ;; NUM es cualquier número. ;; BAZ es cualquier número en el intervalo [-10, -2]. (Esto se ve obligado por cómo hacemos la notación de cadenas) . ;; ;; NUM y BAZ se truncarán a un número entero si son flotantes (por ejemplo, 14.25 ;; se truncarán a 14, -123456789.87 a -123456789, etc. ( if ( y ( numberp num ) ( numberp baz ) ( <=) . ( reparar baz ) -2 ) ( > ( reparar baz ) -11 )) ( progn ( setq baz ( flotar ( reparar baz )) num ( flotar ( reparar num )) dig ( if ( = num 0 ) "0" "" )) ( while ( /= num 0 ) ( setq primero ( - num ( * baz ( setq num ( fix ( / num baz )))))) ( if ( menosp primero ) ( setq num ( 1+ num ) primero ( - primer baz ))) ( setq dig ( strcat ( itoa ( arreglar primero )) dig ))) dig ) ( progn ( rápido ( cond (( y ( no ( númerop num )) ( no ( númerop baz ))) "\ nNúmero incorrecto y negabase." ) (( not ( numberp num )) "\nNúmero incorrecto." ) (( not ( numberp baz )) "\nNegabase incorrecto." ) ( t                                                                                                  "\nNegabase debe estar dentro del intervalo [-10 -2]". ))) ( príncipe )))) 

Cálculo de atajos

Los siguientes algoritmos suponen que

  1. la entrada está disponible en cadenas de bits y codificada en (base +2; dígitos en ) (como en la mayoría de las computadoras digitales actuales),
  2. existen operaciones de suma (+) y xor (^) que operan en dichas cadenas de bits (como en la mayoría de las computadoras digitales actuales),
  3. el conjunto de dígitos de salida es estándar, es decir. mi. con base ,
  4. la salida está codificada en el mismo formato de cadena de bits, pero el significado de los lugares es otro.

a negabinario

La conversión a negabinario (base −2; dígitos en ) permite un atajo notable (implementación en C):

uint32_t toNegaBinary ( valor uint32_t ) // entrada en binario estándar { uint32_t Schroeppel2 = 0xAAAAAAAA ; // = 2/3*((2*2)^16-1) = ...1010 retorno ( valor + Schroeppel2 ) ^ Schroeppel2 ; // eXclusive OR // resultante unsigned int que se interpretará como una cadena de elementos ε {0,1} (bits) }             

Puerto JavaScript para el mismo cálculo de acceso directo:

función toNegaBinary ( valor ) { const Schroeppel2 = 0xAAAAAAAA ; // Convertir como en C, luego convertir a una cadena NegaBinary return ( ( valor + Schroeppel2 ) ^ Schroeppel2 ). toString ( 2 ); }                 

El algoritmo fue descrito por primera vez por Schroeppel en HAKMEM (1972) como elemento 128. Wolfram MathWorld documenta una versión en Wolfram Language de D. Librik (Szudzik). [8]

a negacuaternario

La conversión a negacuaternario (base −4; dígitos en ) permite un atajo similar (implementación en C):

uint32_t toNegaQuaternary ( valor uint32_t ) // entrada en binario estándar { uint32_t Schroeppel4 = 0xCCCCCCCC ; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030 retorno ( valor + Schroeppel4 ) ^ Schroeppel4 ; // eXclusive OR // resultante unsigned int que se interpretará como una cadena de elementos ε {0,1,2,3} (pares de bits) }             

Puerto JavaScript para el mismo cálculo de acceso directo:

función toNegaQuaternary ( valor ) { const Schroeppel4 = 0xCCCCCCCC ; // Convertir como en C, luego convertir a NegaQuaternary String return ( ( valor + Schroeppel4 ) ^ Schroeppel4 ). toString ( 4 ); }                 

Operaciones aritmeticas

A continuación se describen las operaciones aritméticas para negabinario; Los cálculos en bases más grandes son similares.

Suma

La suma de números negabinarios se realiza bit a bit, comenzando desde los bits menos significativos ; los bits de cada sumando se suman con el acarreo ( ternario balanceado ) del bit anterior (0 en el LSB). Luego, esta suma se descompone en un bit de salida y se lleva a la siguiente iteración como se muestra en la tabla:

La segunda fila de esta tabla, por ejemplo, expresa el hecho de que −1 = 1 + 1 × −2; la quinta fila dice 2 = 0 + −1 × −2; etc.

Como ejemplo, para sumar 1010101 −2 (1 + 4 + 16 + 64 = 85) y 1110100 −2 (4 + 16 − 32 + 64 = 52),

Llevar: 1 −1 0 −1 1 −1 0 0 0Primer sumando: 1 0 1 0 1 0 1Segundo sumando: 1 1 1 0 1 0 0 + --------------------------Número: 1 −1 2 0 3 −1 2 0 1Bit (resultado): 1 1 0 0 1 1 0 0 1Llevar: 0 1 −1 0 −1 1 −1 0 0

entonces el resultado es 110011001 −2 (1 − 8 + 16 − 128 + 256 = 137).

Otro método

Al agregar dos números negabinarios, cada vez que se genera un acarreo, se debe propagar un acarreo adicional al siguiente bit. Considere el mismo ejemplo que el anterior.

Transporte adicional: 1 1 1 0 1 0 0 0 Llevar: 0 1 1 0 1 0 0 0Primer sumando: 1 0 1 0 1 0 1Segundo sumando: 1 1 1 0 1 0 0 + --------------------------Respuesta: 1 1 0 0 1 1 0 0 1

Sumador completo negativo

Se puede diseñar un circuito sumador completo para sumar números en negabinario. Se utiliza la siguiente lógica para calcular la suma y los acarreos: [9]

Incrementar números negabinarios

Se puede incrementar un número negabinario usando la siguiente fórmula: [10]

(Las operaciones en esta fórmula deben interpretarse como operaciones en números binarios regulares. Por ejemplo, es un desplazamiento binario a la izquierda de un bit).

Sustracción

Para restar, multiplica cada bit del segundo número por −1 y suma los números, usando la misma tabla que arriba.

Como ejemplo, para calcular 1101001 −2 (1 − 8 − 32 + 64 = 25) menos 1110100 −2 (4 + 16 − 32 + 64 = 52),

Llevar: 0 1 −1 1 0 0 0Primer número: 1 1 0 1 0 0 1Segundo número: −1 −1 −1 0 −1 0 0 + --------------------Número: 0 1 −2 2 −1 0 1Bit (resultado): 0 1 0 0 1 0 1Llevar: 0 0 1 −1 1 0 0

entonces el resultado es 100101 −2 (1 + 4 −32 = −27).

La negación unaria, x , se puede calcular como una resta binaria de cero, 0 − x .

Multiplicación y división

Desplazarse hacia la izquierda multiplica por −2, desplazarse hacia la derecha divide por −2.

Para multiplicar, multiplique como números decimales o binarios normales , pero usando las reglas negabinarias para sumar el acarreo, al sumar los números.

Primer número: 1 1 1 0 1 1 0Segundo número: 1 0 1 1 0 1 1 × ------------------------------- 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 + -------------------------------Llevar: 0 −1 0 −1 −1 −1 −1 −1 0 −1 0 0Número: 1 0 2 1 2 2 2 3 2 0 2 1 0Bit (resultado): 1 0 0 1 0 0 0 1 0 0 0 1 0Llevar: 0 −1 0 −1 −1 −1 −1 −1 0 −1 0 0

Para cada columna, agregue el acarreo al número y divida la suma por −2 para obtener el nuevo acarreo y el bit resultante como resto.

Comparando números negabinarios

Es posible comparar números negabinarios ajustando ligeramente un comparador binario normal sin signo . Al comparar los números y , invierta cada bit impar de ambos números. Después de esto, compare y utilice un comparador estándar sin signo. [11]

números fraccionarios

Por supuesto, la representación de la base −r puede llevarse más allá del punto de la base , lo que permite la representación de números no enteros.

Al igual que con los sistemas de base positiva, las representaciones terminales corresponden a fracciones donde el denominador es una potencia de la base; Las representaciones repetidas corresponden a otras racionales, y por la misma razón.

Representaciones no únicas

A diferencia de los sistemas de base positiva, donde los números enteros y las fracciones terminales tienen representaciones no únicas (por ejemplo, en decimal 0,999... = 1 ), en los sistemas de base negativa los números enteros tienen una sola representación. Sin embargo, existen racionales con representaciones no únicas. Para los dígitos {0, 1, ..., t } con el dígito más grande y

tenemos

    así como

Entonces, cada número al que se le suma una fracción terminal tiene dos representaciones distintas.

Por ejemplo, en negaternario, es decir y , hay

.

Estas representaciones no únicas se pueden encontrar considerando las representaciones más grandes y más pequeñas posibles con partes enteras 0 y 1 respectivamente, y luego observando que son iguales. (De hecho, esto funciona con cualquier sistema de base entera.) Los racionales así no unívocamente expresables son aquellos de forma

con

base imaginaria

Así como usar una base negativa permite la representación de números negativos sin un signo negativo explícito, usar una base imaginaria permite la representación de números enteros gaussianos . Donald Knuth propuso la base quater-imaginaria (base 2i) en 1955. [12]

Ver también

Referencias

  1. ^ Knuth, Donald (1998), El arte de la programación informática , volumen 2 (3.ª ed.), págs.. Knuth menciona tanto negabinario como negadecimal.
  2. ^ El sistema negaternario se analiza brevemente en Petkovšek, Marko (1990), "Los números ambiguos son densos", The American Mathematical Monthly , 97 (5): 408–411, doi :10.2307/2324393, ISSN  0002-9890, JSTOR  2324393, Señor  1048915.
  3. ^ Vittorio Grünwald. Intorno all'aritmetica dei sistemi numerici a base negativa con particolare riguardo al sistema numerico a base negativo-decimale per lo studio delle sue analogie coll'aritmetica ordinaria (decimale), Giornale di Matematiche di Battaglini (1885), 203-221, 367
  4. ^ Kempner, AJ (1936), "Sistemas anormales de numeración", American Mathematical Monthly , 43 (10): 610–617, doi :10.2307/2300532, JSTOR  2300532, MR  1523792. La única referencia a bases negativas es una nota a pie de página en la página 610, que dice: "Los números positivos menores de 1 y los números negativos pueden usarse como bases con ligeras modificaciones del proceso y restricciones adecuadas en el conjunto de dígitos empleados".
  5. ^ Pawlak, Z.; Wakulicz, A. (1957), "Uso de expansiones con base negativa en el aritmómetro de una computadora digital", Bulletin de l'Académie Polonaise des Sciences , Classe III, 5 : 233–236.
  6. ^ Marczynski, RW, "Los primeros siete años de la informática polaca" Archivado el 19 de julio de 2011 en Wayback Machine , IEEE Annals of the History of Computing, vol. 2, n° 1, enero de 1980
  7. ^ "Algoritmo: documentación de zfp 1.0.1". zfp.readthedocs.io .
  8. ^ Consulte el enlace MathWorld Negabinary. En concreto, las referencias son:
    • Szudzik, M. "Desafío de programación: un concurso de programación de Mathematica". Conferencia de tecnología Wolfram, 1999.
    • Schroeppel, R. Artículo 128 en Beeler, M.; Gosper, RW; y Schroeppel, R. HAKMEM . Cambridge, MA: Laboratorio de Inteligencia Artificial del MIT, Memo AIM-239, p. 24 de febrero de 1972. http://www.hakmem.org/#item128
  9. ^ Francisco, Yu; Suganda, Jutamulia; Shizuhuo, Yin (4 de septiembre de 2001). Introducción a la Óptica de la Información . Prensa académica. pag. 498.ISBN 9780127748115.
  10. ^ "¿Por qué la siguiente fórmula incrementa un número negabinario (número en base -2)?" . Consultado el 29 de agosto de 2016 .
  11. ^ Murugesan, San (1977). "Circuitos aritméticos negativos utilizando aritmética binaria". Revista IEE sobre circuitos y sistemas electrónicos . 1 (2): 77. doi :10.1049/ij-ecs.1977.0005.
  12. ^ D. Knuth. El arte de la programación informática. Volumen 2, 3ª edición. Addison-Wesley. págs.205, "Sistemas numéricos posicionales"

Otras lecturas

enlaces externos