stringtranslate.com

Base negativa

Se puede utilizar una base negativa (o un radio negativo) para construir un sistema de numeración posicional no estándar . Al igual que otros sistemas de valor posicional, cada posición contiene múltiplos de la potencia correspondiente 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 aceptar 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 informática, 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 que normalmente contiene un signo negativo a menudo da como resultado que un número de base negativa tenga un dígito más que su equivalente de base positiva.

Los nombres comunes de los sistemas de numeración posicional de base negativa se forman anteponiendo nega- al nombre del sistema de base positiva correspondiente; 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) a cuaternario (base 4). [1] [2]

Ejemplo

Consideremos lo que se entiende por representación12243 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, extracciones de raíces, pruebas de divisibilidad y conversión de bases. Las bases negativas fueron mencionadas de pasada por AJ Kempner en 1936 [4] y estudiadas con más detalle por Zdzisław Pawlak y A. Wakulicz en 1957. [5]

El sistema negabinario 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 Matemático 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 el sistema 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 pequeños en magnitud 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 entero a puede escribirse de forma única como

donde cada dígito d k es un 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 está dada entonces por la cadena d n d n −1 ... d 1 d 0 .

Los sistemas de base negativa pueden compararse con representaciones de dígitos con signo , como el ternario balanceado , donde el radio es positivo pero los dígitos se toman de un rango parcialmente negativo. (En la tabla siguiente, el dígito de valor −1 se escribe como el carácter único 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 la misma representación en decimal y negadecimal. De manera similar,

y se representa 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:

Nótese que, con la excepción del ternario negativo balanceado, las expansiones base −r de los enteros negativos tienen un número par de dígitos, mientras que las expansiones base −r de los 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 mediante la división repetida por −r , registrando los residuos no negativos en , y concatenando esos residuos, comenzando con el último. Tenga en cuenta que si a /  b es c con residuo 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 manera que d sea no negativo y 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 negativo:

Leyendo los restos al revés obtenemos la representación negaternaria de 146 10 : 21102 –3 .

Demostración: -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 dígito menos significativo primero.

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 números enteros) de dividir un número negativo por un número negativo se redondea hacia 0, por lo general dejando un resto negativo. En tal caso, tenemos a = (− r ) c + d = (− r ) c + dr + r = (− r )( c + 1) + ( d + r ) . Debido a que | d | < 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 agregar 1 y r al cociente y al resto respectivamente.

Código de implementación de ejemplo

Para negabinario

DO#
cadena estática ToNegabinary ( int val ) { cadena resultado = cadena . Vacío ;      mientras ( val != 0 ) { int resto = val % - 2 ; val = val / - 2 ;            si ( resto < 0 ) { resto += 2 ; val += 1 ; }       resultado = resto . ToString () + resultado ; }    devolver resultado ; } 
C++
auto to_negabinary ( int valor ) { std :: bitset < sizeof ( int ) * CHAR_BIT > resultado ; std :: size_t bit_position = 0 ;            mientras ( valor != 0 ) { const auto div_result = std :: div ( valor , -2 );           si ( div_result . rem < 0 ) valor = div_result . quot + 1 ; de lo contrario valor = div_result . quot ;             resultado . establecer ( bit_posicion , div_result . rem != 0 );    ++ posición_bit ; }  devolver resultado ; } 

A negaternario

DO#
cadena estática Negaternario ( int val ) { cadena resultado = cadena . Vacío ;      mientras ( val != 0 ) { int resto = val % - 3 ; val = val / - 3 ;            si ( resto < 0 ) { resto += 3 ; val += 1 ; }       resultado = resto . ToString () + resultado ; }    devolver resultado ; } 
Pitón
def  negaternario ( i :  int )  ->  str : """Decimal a negaternario.""" si i == 0 : dígitos = [ "0" ] de lo contrario : dígitos = [] mientras i != 0 : i , resto = divmod ( i , - 3 ) si resto < 0 : i , resto = i + 1 , resto + 3 dígitos . append ( str ( resto )) return "" . join ( dígitos [:: - 1 ])                                     
>>> negaternario ( 1000 ) '2212001'
Ceceo común
( defun negaternario ( i ) ( if ( zerop i ) "0" ( let (( dígitos "" ) ( rem 0 )) ( bucle while ( not ( zerop i )) do ( progn ( conjunto-de-valores-múltiplesq ( i rem ) ( truncar i -3 )) ( when ( minusp rem ) ( incf i ) ( incf rem 3 )) ( setf dígitos ( concatenar 'string ( escritura-en-string rem ) dígitos )))) dígitos )))                                        

A cualquier base negativa

Java
importar java.util.ArrayList ; importar java.util.Collections ; public ArrayList < Integer > negativeBase ( int entrada , int base ) { ArrayList < Integer > result_rev = new ArrayList <> (); int numero = entrada ; while ( numero != 0 ) { int i = numero % base ; numero /= base ; if ( i < 0 ) { i += Math . abs ( base ); numero ++ ; } result_rev . add ( i ); } return Collections . reverse ( results_rev . clone ()); }                                             

Lo anterior muestra el resultado en una lista de enteros, de modo que el código no tiene que ocuparse de cómo representar una base menor que -10. Para mostrar el resultado como una cadena, se puede decidir una asignación de la base a caracteres. Por ejemplo:

import java.util.stream.Collectors ; final String alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@_" ; public String toBaseString ( ArrayList < Integer > lst ) { // Lanzaría una excepción si la base está más allá de los 64 caracteres posibles return lst . stream (). map ( n -> alphabet [ n ] ). collect ( Collectors . join ( "" )); }              
AutoLisp
( defun negabase ( num baz / dig rst ) ;; NUM es cualquier número. ;; BAZ es cualquier número en el intervalo [-10, -2]. (Esto es forzado por la forma en que hacemos la notación de cadenas). ;; ;; NUM y BAZ se truncarán a un entero si son flotantes (por ejemplo, 14.25 ;; se truncará a 14, -123456789.87 a -123456789, etc.). ( if ( and ( numberp num ) ( numberp baz ) ( <= ( fix baz ) -2 ) ( > ( fix baz ) -11 )) ( progn ( setq baz ( float ( fix baz )) num ( float ( fix num )) dig ( if ( = num 0 ) "0" "" )) ( while ( /= num 0 ) ( setq rst ( - num ( * baz ( setq num ( fix ( / num baz ))))) ( if ( minusp rst ) ( setq num ( 1+ num ) rst ( - rst baz ))) ( setq dig ( strcat ( itoa ( fix rst )) dig ))) dig ) ( progn ( prompt ( cond (( and ( not ( numberp num )) ( not ( numberp baz ))) "\nNúmero y base de negación incorrectos." ) (( not ( numberp num )) "\nNúmero incorrecto." ) (( not ( numberp baz )) "\nBase de negación incorrecta." ) ( t                                                                                                  "\nNegabase debe estar dentro del intervalo [-10 -2]". ))) ( princ )))) 

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 adición (+) y xor (^) que operan sobre 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, con base ,
  4. La salida está codificada en el mismo formato de cadena de bits, pero el significado de los lugares es otro.

Para negabinario

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

uint32_t toNegaBinary ( uint32_t value ) // entrada en binario estándar { uint32_t Schroeppel2 = 0xAAAAAAAA ; // = 2/3*((2*2)^16-1) = ...1010 return ( value + Schroeppel2 ) ^ Schroeppel2 ; // OR exclusivo // el int sin signo resultante 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]

Al negacuaternario

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

uint32_t toNegaQuaternary ( uint32_t value ) // entrada en binario estándar { uint32_t Schroeppel4 = 0xCCCC ; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030 return ( value + Schroeppel4 ) ^ Schroeppel4 ; // OR exclusivo // el int sin signo resultante 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 = 0xCCCCCCCCCC ; // Convertir como en C, luego convertir a NegaQuaternary String return ( ( valor + Schroeppel4 ) ^ Schroeppel4 ). toString ( 4 ); }                 

Operaciones aritméticas

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

Suma

La suma de números negabinarios se realiza bit a bit, comenzando por los bits menos significativos ; los bits de cada sumando se suman con el acarreo ( ternario balanceado ) del bit anterior (0 en el bit menos significativo). Esta suma se descompone luego en un bit de salida y un acarreo para 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.

A modo de 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 sumar dos números negabinarios, cada vez que se genera un acarreo, se debe propagar un acarreo adicional al siguiente bit. Considere el mismo ejemplo anterior

Carga 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 negabinario

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

Incremento de números negabinarios

El incremento de un número negabinario se puede realizar utilizando la siguiente fórmula: [10]

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

Sustracción

Para restar, multiplique cada bit del segundo número por −1 y sume los números, utilizando la misma tabla que la anterior.

A modo de 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 resta binaria de cero, 0 − x .

Multiplicación y división

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

Para multiplicar, multiplique como números decimales o binarios normales , pero utilizando 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.

Comparación de números negabinarios

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

Números fraccionarios

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

Al igual que en 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 otros 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 exactas tienen representaciones no únicas (por ejemplo, en decimal 0,999... = 1 ), en los sistemas de base negativa los números enteros tienen una única 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

Por lo tanto, cada número con una fracción terminal añadida tiene dos representaciones distintas.

Por ejemplo, en negaternario, es decir y , hay

.

Tales 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 notando que son iguales. (De hecho, esto funciona con cualquier sistema de base entera). Los racionales que así se pueden expresar de manera no única son aquellos de la forma

con

Base imaginaria

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

Véase también

Referencias

  1. ^ Knuth, Donald (1998), El arte de la programación informática , Volumen 2 (3.ª ed.), págs. 204-205Knuth menciona tanto el negabinario como el 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, MR  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  1523792La única referencia a bases negativas es una nota al pie en la página 610, que dice: "Los números positivos menores que 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. ^ Véase el enlace de 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: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 24, febrero de 1972. http://www.hakmem.org/#item128
  9. ^ Francis, Yu; Suganda, Jutamulia; Shizuhuo, Yin (4 de septiembre de 2001). Introducción a la óptica de la información . Academic Press. pág. 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 negabinarios que utilizan aritmética binaria". IEE Journal on Electronic Circuits and Systems . 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 de números posicionales".

Lectura adicional

Enlaces externos