Operando números negativos em computadores

maxresdefault

Os conceitos de aritmética modular eram utilizados em computadores mecânicos, e já não eram novidade naquela época. (Imagem de: https://www.youtube.com/watch?v=nmwSmwNF9XY)

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

Eu sempre me perguntei se Matemática é descoberta ou desenvolvimento. Os autores costumam dizer que ela é 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.

Costumamos representar 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 ‘não há’. Sei que até há algum tempo não existia consenso sobre o zero ser Natural ou 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…

2. Preciso de um sinal

Certamente você já internalizou o conceito, mas se em engenharia os números são abstrações de grandezas físicas, o sinal sempre carrega outro significado. Se eu tenho R$100,00 na conta-corrente esse dinheiro sai do banco e vem para o meu bolso. Se eu tenho -R$100,00, além de estar infeliz, eu preciso fazer com que esse dinheiro chegue até o banco. 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, elemento neutro, elemento simétrico e associatividade. Um exemplo de grupo é o conjunto dos inteiros (Z) para as operações de soma e multiplicação.

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) elemento neutro: Existe um elemento I ∈ G, tal que a*I = I*a = a,
c) elemento simétrico: 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 ideia de infinito não é concebível para uma máquina, e utilizaremos grupos finitos.

(d.ii) Definição. Um grupo finito é um conjunto finito de elementos com uma operação binária que satisfaz os axiomas do fechamento, associatividade, e cancelamento (Se a*x = b*x, a = b).

Para o meu computador de 3 bits talvez seria conveniente utilizarmos os conjuntos:

A= { 0, 1, 2, 3, 4, 5, 6, 7}, ou

B = { 16, 17, 18, 19, 20, 21, 22, 23} quem sabe.

Eu empilhei os conjuntos acima para forçar a ideia de congruência entre os elementos. Além disso, para a operação de adição +, os axiomas de (d.ii) são satisfeitos se definirmos: 7+1 =0 em A e 23+1=16 e A e B podem ser considerados grupos.

(d.iii) Definição. Dizemos que dois grupos 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.

Utilizando os exemplos A e B acima:

2 = 18 + 8k, se k = -2

20 = 4 + 8k, se k = 2,

3. Subtraindo 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

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 e b = 10.

Uma pequena demonstração algébrica do método pode ser feita.
(dm.i) Demonstração.
Sejam M, S e D pontos do meu universo módulo N, de forma que:
(i) M-S=D para
(ii) M>=S e D <= N.
e
(iii) D = 0 para M=S.
Queremos demonstrar que:
(iv) D = N - [(N-M) + S]
O lado direito de (iv) satifaz (ii) para M>=S.
Ainda para M=S, (iii) é satisfeito: D=N-N-M+M=0
Naturalmente em (iv):
D= M-S = N-N+M-S
D = M-S
como queria demonstrar.

4. Complementos numéricos

(d.iv) Definição.
(d.iv’) O complemento de b de um número de n dígitos y, na base b, é dado por: b^n – y.
(d.iv’’) O complemento de b-1 de um número de n dígitos y, na base b, é dado por (b^n – 1) - y

Os livros em geral começam a tratando do assunto desta postagem 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 de 9 para 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 maiores que dezenas, fazemos o complemento para 99, 999, 9999… (nossa aritmética continua posicional!)

Exemplo:

Resolva 953 – 53 utilizando o método dos complementos, em módulo 9

046+ 53 = 99

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

5. 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 o elemento neutro 
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’ = 001.

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, entretanto, atribuímos a ele um grupo equivalente, com elementos côngruos modulo 2, mantendo todas as propriedades que já tornavam aquele um grupo finito válido (definições d.i, d.ii, d.iii). É possível provar que o conjunto G = {100, 101, 110, 111, 000, 001, 010, 011} é um grupo finito.

O complemento de 2, do número binário y de três dígitos por (d.iv’) é então 8 – y. A representação binária do complemento de 2 de um número y, é utilizada para a 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. (Pense em um círculo somente com os pontos 0 e 1 na base 2, e comprove graficamente por que funciona).
Interpretação do '1' como sinal: 

Peguemos como exemplo a igualdade 011 + 101 = 1000, que poderia significar 3 + 5 = 8, que é côngruo a 0 módulo 8. Ainda na base 2, oito é representado por 1000. O ‘1’ se pensado como sinal, indica o sentido pelo qual ultrapassamos a origem ao representarmos nossos arcos de maneira contínua. Andando da esquerda para direita os elementos assumem valores cada vez maiores. Quando os 3 bits estouram e o vai-um é necessário para representar o estado naquele instante , significa que os elementos agora estão assumindo valores cada vez mais negativos em relação aos anteriores.

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 de dígitos diferentes, devemos estender o sinal. 
Exemplo:

-16 - 2 =
 10000
+11110
======
101110

No próximo artigo sobre o assunto, vou mostrar como operar aritméticas com sinal em circuitos digitais descritos em Verilog.

Até a próxima!

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

Autor: Antonio Giacomelli de Oliveira

Engenheiro Eletrônico

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão /  Alterar )

Google photo

Está a comentar usando a sua conta Google Terminar Sessão /  Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão /  Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão /  Alterar )

Connecting to %s