Sistemas de numeração 4 - Generalizando a aritmética: subtração de dois inteiros

Esta é mais uma das minhas séries que andava meio paradona, e que este deve ser o último post. Creio que, depois daqui, qualquer leitor que queira prosseguir para outras operações, ou queira enveredar pelo caminho mais abstrato da teoria dos números, já tenha sido propriamente estimulado e possa seguir adiante com esforço próprio.

Nosso problema de hoje é: conhecidas as representações b-árias dos números inteiros X (chamado minuendo) e Y (chamado subtraendo) tais que

Encontrar um procedimento genérico para determinar a representação b-ária do número inteiro D (diferença) tal que D = X - Y.

Na nossa já conhecida expansão nos polinômios de representação de acordo com o TGE (cujo enunciado e prova estão no primeiro post desta série), temos então que:

Novamente, como no caso da soma, temos duas possibilidades para o coeficiente di. O primeiro deles é:

Quando isto ocorre o valor do coeficiente di é obtido diretamente da subtração dos valores dos coeficientes xi (do minuendo) e yi (do subtraendo). As tabelas de tabuada da soma dos algarismos para os sistemas binário, decimal e hexadecimal apresentadas no post anterior desta série podem ser usadas para simplificar a tarefa de execução desta subtração. Obviamente o segundo caso será:

Para resolver este impasse nós vamos recorrer a uma consequência da nossa hipótese inicial que X seja maior ou igual a Y: existe na representação b-ária do minuendo pelo menos um algarismo não nulo cuja ordem de grandeza é maior que i (a ordem de grandeza considerada no momento).

Porque isto é verdade? Simples: se isto não fosse verdade então xi seria o dígito de maior ordem de grandeza na representação b-ária do minuendo; mas se ele for o dígito de mais alta ordem ele não pode ser menor que o dígito de ordem de grandeza equivalente na representação do subtraendo, o que contraria a situação inicial que assumimos.

Como existe este dígito xj (j > i), então podemos fazer o seguinte desdobramento:

Como, obviamente b + xi > yi , recaímos no primeiro caso. Vale observar que este "empréstimo" de uma ordem superior altera efetivamente os valores dos coeficientes do termo que fez a cessão e de todos os eventuais termos com coeficiente nulo existentes entre ele e o termo que recebe a cessão. Esta modificação tem de ser levada em conta quando, na execução do algoritmo, formos tratar os termos de ordem superior.

Algoritmo geral da subtração

Considerando o que dissemos acima, nosso algoritmo generalizado para a subtração de dois números inteiros fica da seguiinte forma:

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. i = 0;
3. xi < yi ?
   SIM: vá para o passo 10
   NÃO: vá para o passo 4;
4. Consultando a tabuada da soma b-ária efetue a subtração xi - yi;
5. Escreva o dígito da diferença nesta ordem de grandeza (i) usando o algarismo b-ário cujo valor corresponde ao resultado do passo (4);
6. Ainda existem dígitos de ordem mais alta que a atual na representação de X?
   SIM: vá para o passo 7
   NÃO: vá para o passo 19;
7. i = i + 1;
8. Vá para o passo 3;
9. j = i + 1;
10. xj é um dígito não nulo?
    SIM: vá para o passo 13
    NÃO: vá para o passo 11;
11. j = j + 1;
12. Vá para o passo 11;
13. xj = xj - 1;
14. j = j - 1;
15. j = i ?
    SIM: vá para o passo 16
    NÃO: vá para o passo 18;
16. xi = b + xi;
17. Vá para o passo 4;
18. Vá para o passo 15;
19. FIM.

Vejamos alguns exemplos de aplicação do algoritmo. As linhas adicionais acima do minuendo correspondem aos dígitos do minuendo que passam a valer após a ocorrência de um empréstimo. Os sistemas de numeração apresentados nos exemplos são, respectivamente, binário, decimal e hexadecimal.

Creio que isso chega para meus propósitos. Para quem quiser continuar nesta linha de raciocínio, o algoritmo da multiplicação é bem fácil de desenvolver, e fica fácil de entender a necessidade do deslocamento de uma ordem de grandeza para cima para cada novo algorismo do multiplicador que vai operar sobre os algarismos do multiplicando. Também é fácil deduzir as tabuadas de multiplicação necessárias para cada sistema de numeração de uso mais comum (binário, decimal e hexadecimal).

O algoritmo da divisão é um pouco mais sutil, mas não é difícil. Se alguém quiser mais dados sobre isso é só gritar (os comentários estão abertos para todos os posts). Inté a próxima.