Construindo números negativos em computadores

maxresdefault

1. “Tudo é número” (Pitágoras)

Os autores costumam dizer que a Matemática é desenvolvida conforme o homem necessita. Assim, podemos imaginar que os humanos primitivos faziam risquinhos para representar uma coleção de objetos (cabras, peles, filhos…). Constatada sua ineficiência, criaram-se símbolos que representavam tamanhos de coleções diferentes, depois símbolos que representavam uma coleção de outros símbolos, e a coisa foi ficando cada vez mais sofisticada.

Representamos os numerais em uma base B, da seguinte forma, em uma notação de ponto fixo onde “a” é inteiro:

eq

O sistema de base 10 que utilizamos é composto pelos símbolos {0,1,2,3,4,5,6,7,8,9} para representar as quantidades de zero a nove unidades de algo. Aliás, o zero é uma invenção muito interessante pois é um símbolo que representa ‘nada’. Alguns autores incluem o 0 como um número natural, outros não.

Dizemos também que utilizamos um sistema posicional – desloque o número para esquerda ou direita ele assume centenas, dezenas, milhares, centésimos…

Certamente você já internalizou o conceito, mas se em engenharia os números são representações de grandezas físicas, o sinal sempre carrega outro significado. Se eu tenho +R$100,00 na conta-corrente esse dinheiro pode sair do banco e entrar no meu bolso. Se eu tenho -R$100,00, este dinheiro somente pode assumir a direção contrária. Um móvel com aceleração de -12m/s^2 permanece em repouso sob uma referência que acelera a 12m/s^2. Não à toa, os números negativos também são chamados de relativos, e ter isto em mente ajuda a entender como representá-los em um computador digital.

Vamos analisar um somador hipotético, sem sinal, que utiliza 3 bits para representar cada uma das suas parcelas, e também 3 bits para representar o resultado. Em notação decimal, as entradas variam de 0 a 7. Ao somarmos 7+7, por exemplo, a saída ‘estoura’:

 111
+111
====
1110

O importante aqui é você perceber que estamos trabalhando num universo onde o maior número possível de ser representado é o 7. E isto é exatamente o que ocorre quando construímos computadores. Se o meu computador pode somente ter 3 bits, é como se tudo o que tivéssemos fosse um conjunto de 8 elementos distintos.

(d.i) Definição. Um Grupo G é um conjunto de elementos em que se pode definir uma operação binária *, que satisfaz os critérios de fechamento, identidade (elemento neutro), inverso (elemento simétrico) e associatividade. 

G = {x, y, z} é um grupo, se para uma operação binária *, {G, *} satisfaz os seguintes axiomas:

a) Fechamento: Se x e y ∈ G, x *y ∈ G
b) Identidade: Existe um elemento I ∈ G, tal que a*I = I*a = a,
c) Inverso: Para todo elemento a ∈ G, existe um elemento s tal que a * s = I
d) Associatividade: Para x, y, z ∈ G é verdadeiro que: x*y*z = (x*y)*z = x*(y*z)
A

2. Subtração com números não-negativos

Talvez seja conveniente representarmos um grupo finito G onde o maior módulo possível é 8, na forma de um círculo de comprimento 8:

modulo
(d.iii) Definição. Dizemos que dois conjuntos são equivalentes quando existe uma relação biunívoca, tal que para todo elemento a ∈ A e b ∈ B, existe k inteiro tal que a = b + kN, onde N é o número de elementos (módulo) de A e B.

Desta forma, podemos representar qualquer número inteiro a = b + kN, onde k é o “número de voltas” dadas no círculo de comprimento N, e ‘b’ o restante de arco (em unidades) necessário para completar ‘a’, que chamamos de resto ou resíduo.

Assim, para o nosso grupo de módulo 8:
i) 21 = 5 + 2x8
ii) 64 = 0 + 8x8
iii) 10 = 2 + 1x8

Que podemos escrever da seguinte forma:
iv) 21 ≡ 5 (mod8) (21 é congruente a 5 módulo 8)
v) 64 ≡ 0 (mod8) (64 é congruente a 0 módulo 8)
vi) 10 ≡ 2 (mod8) (10 é conguente a 2 módulo 8)

Se eu quero resolver 8 – 6, posso evitar trabalhar com subtrações. Primeiro vamos pensar graficamente:

  • Partindo do zero e andando 8 unidades voltamos ao zero, ou: 8 ≡ 0 (mod8)
  • Partindo do zero e andando 6 unidades a esquerda, chegamos ao 2, ou: -6 ≡ 2 mod8

Logo: 8 (mod8) – 6 (mod8) ≡ 0 (mod8) + 2 (mod8) ≡ 2 (mod8).

Abaixo, com exemplos, descrevo um algoritmo para resolver subtrações utilizando números não-negativos em um grupo módulo N.

(p.1) Problema.
Resolva 15 – 8 somente com números não-negativos, em G = {0,1,2,3,4,5,6,7}
1o - Ache o minuendo congruente no grupo desejado.
O ‘equivalente modulo 8’ de 15 pode ser encontrado em G com (1):
15 = b + 8k, se k = 1, b = 7.
2o - Ache o subtraendo equivalente ao grupo desejado e some ao minuendo:
O equivalente a 8 em G é 0.
8 = b + 8x1; b = 0
Assim:
7 + 0 = 7.
3o - Encontre o equivalente do resultado no grupo desejado:
7 já esta no grupo desejado, e é o resultado.

(p.2) Problema.
Resolva: 22 – 12, somente com números não negativos em
G = {8,9,10,11,12,13,14,15}
O equivalente de 22 no grupo G é:
22 = a + 8k, k = 1, e a = 14
Assim:
14 + 12 = 26
Cujo equivalente em {8, 9, 10, 11, 12, 13, 14, 15} é:
26 = b + k8 -> k = 2, b = 10
.

3. Complementos numéricos

Os livros em geral começam a tratando deste assunto com uma tabela:

 Elemento | Complemento de 9 
---------------------------
0 | 9
1 | 8
2 | 7
3 | 6
4 | 5
5 | 4
6 | 3
7 | 2
8 | 1
9 | 0

Tabela 1. Complementos para 9 dos inteiros de 0 a 9

O método dos complementos é uma aplicação direta da aritmética modular, e fundamentalmente utiliza dos mesmos conceitos explicados nas seções anteriores.

Podemos efetuar as subtrações somente com números não-negativos, usando o complemento do minuendo somado ao subtraendo, e tomando o complemento da soma como resposta.

8-3 → 1 + 3 = 4.

O complemento para 9 de 4 é 5, que é a nossa resposta.

Quando tratamos de números com mais dígitos na base 10, fazemos o complemento para 99, 999, 9999… (porque a representação dos números como conhecemos é posicional).

Exemplo:

Resolva 953 – 53 utilizando o método dos complementos

046+ 53 = 99

Cujo complemento para 999 é 900, que é a nossa resposta.

4. Complemento de 2

A base para a representação numérica digital é a binária B = {0, 1}, e vamos utilizar os conceitos de aritmética modular para operarmos subtrações com números binários.

Decimal 0 a 7 | Binário | Congruentes
-----------------------------------------
0 | 000 | ...,-8,0,8,...
1 | 001 | ...,-7,1,9,...
2 | 010 | ...,-6,2,10,...
3 | 011 | ...,-5,3,11,...
4 | 100 | ...,-4,4,12,...
5 | 101 | ...,-3,5,13,...
6 | 110 | ...,-2,6,14,...
7 | 111 | ...,-1,7,15,...

Tabela 2. Inteiros decimais de 0 a 7 representados na forma binária, e seus congruentes módulo 8.

No nosso computador de três bits podemos representar a reta numérica com os pontos decimais 0 a 7, em base 2, da seguinte forma:

    b'    a'    a     b    c    d    e    f    g    h
? ? 000 001 010 011 100 101 110 111
------------------------------------------------->

Queremos representar números negativos. Ora,
Se a + s = 0, s é o simétrico de a se 0 representar a identidade da álgebra.
.

No caso dos números representados na reta numérica acima:
a + s = 000 ↔ a' = 000 (000 + 000 = 000)
b + s = 000 ↔ b’ = 111 (001 + 111 = 1000)
c + s = 000 ↔ c’ = 110
d + s = 000 ↔ d’ = 101
e + s = 000 ↔ e’ = 100

f + s = 000 ↔ f’ = 011
g + s = 000 ↔ g’ = 010

Exceto para f e g, todos os simétricos tem 1 no bit mais significativo, de forma que para lançar mão de números negativos poderíamos definir nosso grupo com os seguintes elementos escritos em base 2:

Decimal | Binário
------------------
-4 | 100
-3 | 101
-2 | 110
-1 | 111
0 | 000
1 | 001
2 | 010
3 | 011

Escolhemos não representar o 4, e sim o -4 a partir dos resultados empíricos para encontrar o elemento simétrico.

Perceba que continuamos com o mesmos elementos de antes e portanto o mesmo grupo, mas o mapeamos a outro subconjunto dos números inteiros, mantendo todas as propriedades que já tornavam aquele um grupo finito. É possível provar que o conjunto G = {100, 101, 110, 111, 000, 001, 010, 011} é um grupo finito. Neste caso, o elemento (simétrico) inverso de -4 é o próprio -4: 100+100=(1)000.

A representação binária do complemento de 2 de um número y, é utilizada para representar o elemento simétrico s, tal que y + s = 0.  Como regra prática dizemos que o complemento de 2 de um número na base 2, é sua negação adicionada a 1.

Você pode experimentar efetuar as operações com o complemento de 2 e verificar como a notação é muito conveniente.

Note que:
O complemento de 2 é definido para representar números de base 2, de
N bits, no intervalo de -2^(N-1) a 2^(N-1) – 1.
Ao operarmos representações com números binários de diferentes comprimentos, devemos estender o sinal.
Exemplo:

-16 - 2 =
110000
+111110

=======
101110
O texto deste artigo é original. As seguintes referências foram consultadas durante sua elaboração:
Conceitos Fundamentais da Matemática (Bento Jesus de Caraça)
Introduction to Logic Circuits and Logic Design With Verilog (Brock J. LaMeres)
Group Theory, em https://crypto.stanford.edu/pbc/notes/group/group.html
Introdução à Teoria dos Números, em 
http://vigo.ime.unicamp.br/Projeto/2012-1/ms777/ms777_Viviane.pdf
Abstract Algebra Notes: www.antoniogiacomelli.com/abstract-algebra-notes/

Author: Antonio Giacomelli de Oliveira

Embedded Systems Engineer

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: