Quem sou eu

Minha foto
Salvador, BA, Brazil
Analista de sistemas, expert em telecom, formado em Eng. Elétrica e nerd assumido

quinta-feira, 20 de janeiro de 2011

Sistemas de numeração 3 - Generalizando a aritmética: soma de dois inteiros

Pois bem. Depois de um intervalo (longo) volto a publicar artigos no blog. Enfim... o assunto de hoje é, continuando a série sobre sistemas de numeração, a generalização dos algoritmos da aritmética para que eles sejam aplicáveis a números expressos em qualquer sistema de numeração posicional baseados no TGE.

Alguém aí deve estar pensando: "peraí... algoritmos da aritmética?" É algoritmos mesmo, porque a aritmética básica trata dos métodos para execução das operações fundamentais. E todos os procedimentos da aritmética são, na essência, operações executadas sobre polinômios. Vamos começar analisando o algoritmo para a soma de dois números inteiros

Conhecidas as representações b-árias dos números naturais X e Y (parcelas), queremos determinar um procedimento para obter a representação b-ária do número natural S (soma) tal que S = X + Y.

Como a operação de soma S das representações é apenas uma "abreviatura" para a soma dos polinômios de representação de X e Y na base b, de acordo com o TGE, cada dígito da representação de S corresponde a um coeficiente do seu polinômio de representação que, por sua vez, é obtido pela soma dos coeficientes dos termos de mesma ordem de grandeza dos polinômios de reprsentação de X e Y. Então:


Isto nos dá duas possibilidades para a determinação do coeficiente si:


Este é o caso mais simples. Nesta situação, pelo TGN, existe um algarismo b-ário que corresponde ao valor de si.


Neste caso podemos escrever que


A justificativa para os possíveis valores do fator delta n expressão acima é simples. Basta lembrar que, pelo TGE, todos os coeficientes do polinômio de representação são valores entre zero e b - 1 (inclusive). Agora, substituindo este resultado no termo genérico do polinômio de representação de S temos


Este resultado mostra que este cado para a soma dos termos dos polinômios de representação de X e Y resultam em um termo nesta mesma ordem de grandeza com coeficiente igual a delta, que pode ser representado diretamente por um algarismo b-ário, e um termo na ordem de grandeza imediatamente superior com coeficiente unitário (que também possui algarismo b-ário correspondente). Este segundo termo é o famoso "vai um" a que nos acostumamos ao aprender o procedimento da soma com números decimais (embora não os chamássemos assim) no priimeiro ano do ensino fundamental.

O único fato adicional para a realização de operações de soma é dominar a tabela de resultados da soma de números com um único dígito b-ário. A título de exemplo seguem abaixo as "tabuadas" da soma para os sistemas binário, decimal e hexadecimal.




Infelizmente não existe maneira de aprender a execução do procedimento de soma de dois números inteiros que não envolva decorar (ou, pelo menos, ter à mão) a tabuada da soma para o(s) sistema(s) de numerção desejado(s). A parte boa da história, embora seja difícil de acreditar quando a gente é criança, é que a constante repetição causa a memorização, provavelmente para a vida inteira, desta(s) tabuada(s). O procedimento de soma descrito abaixo é genérico para qualquer sistema de numeração, mas presume o conhecimento (memorizado ou documental) da tabuada da soma para o sistema de numeração utilizado.

Algoritmo para a soma de dois números inteiros:

Supõem-se cohecidas as representações b-árias das parcelas X e Y da soma, e deseja-se obter a representação b-ária de S = X + Y
  1. Escreva as representações b-árias de X e Y uma sobe a outra, mantendo alinhamento vertical dos dígitos de mesma ordem de grandeza a partir da menor ordem de grandeza (da direita para a esquerda);
  2. Posicione-se na coluna de menor ordem de grandeza;
  3. Transporte = 0;
  4. Consultando a tabuada da soma b-ária verifique o valor a soma dos dígitos das duas parcelas e do Transporte;
  5. A soma obtida no passo (4) tem um único dígito?
    SIM: vá para o passo 6
    NÂO: vá para o passo 9;
  6. Escreva o dígito da soma nesta ordem de grandeza usando o algarismo b-ário cujo valor corresponde à soma obtida no passo (4);
  7. Transporte = 0
  8. Vá para o passo 11;
  9. Escreva o dígito da soma nesta ordem de grandeza usando o algarismo b-ário das unidades na soma obtida no passo (4); 
  10. Transporte = 1;
  11. Ainda existem dígitos de ordem mais alta que a atual em alguma das parcelas?
    SIM: vá para o passo 12
    NÃO: vá para o passo 14;
  12. Posicione-se na próxima ordem de grandeza;
  13. Vá para o passo 4;
  14. Transporte é igual a 1?
    SIM: vá para o passo 15
    NÂO: vá para o passo 16;
  15. Escreva o dígito da na ordem de grandeza imediatamente superior usando o algarismo b-ário que representa a quantidade unitária;
  16. FIM.
Vejamos exemplos da aplicação deste algoritmo, respectivamente, para somas nos sistemas binário, decimal e hexadecimal.


Muito bem... No próximo artigo desta séria vamos continuar com este assunto, abordando a operação de subtração de números inteiros. Até lá!

Um comentário: