Introdução
Essa é a parte dois da série “Calculando com o sed”. Nessa parte, iremos aprender como somar e subtrair dois números inteiros.
- Calculando com o sed – Parte I (Soma um)
- Calculando com o sed – Parte II (Somando e subtraindo números inteiros)
- Calculando com o sed – Parte III (Somando e subtraindo números decimais)
- Calculando com o sed – Parte IV (Multiplicação – Método Knuth)
- Calculando com o sed – Parte V (Autômatos e validação de expressões)
- Calculando com o sed – Parte VI (Calculadora completa)
O conteúdo não está completamente definido e por isso poderá sofrer mudanças no decorrer das postagens.
Somando algarismos
Vamos começar com o modo mais simples de somar, que é a soma de dois algarismos. Claro que existem vários algoritmos algoritmos para esse propósito, mas aqui veremos aquele usado no dc.sed [1].
Como antes, resolveremos esse problema usando lookup tables. Somando dois algarismos cuja soma é menor que dez, podemos obter valor da soma usando deslocamentos:
4+3 XXXXXXX9876543210 |________| +10
A lógica é inserir um número de caracteres X igual a soma dos algarismos e em seguida deslocar 10 unidades. No final, alcançaremos o valor da soma na string numérica. O caracter X é chamado de placeholder, e nesse caso, ele poderia ter qualquer valor.
Veja que esse conceito funciona para qualquer soma de algarismos cujo resultado é menor que 10:
2+6 XXXXXXXX9876543210 |________| + 10 1+1 XX9876543210 |________| + 10 0+0 9876543210 |________| + 10
Para a soma 0+0 nenhum caractere placeholder foi adicionado. Mais na frente, veremos como gerar esses caracteres placeholders e notaremos que não é ideal gerar duas strings vazias como na soma 0+0. Para contornar esse problema, aumentaremos o deslocamento para 11 e adicionaremos mais um caractere X:
0+0
X9876543210
|_________|
+11
1+8
XXXXXXXXXX9876543210
|_________|
+11
Agora vamos analisar quando a soma é maior ou igual a 10.
9+7 XXXXXXXXXXXXXXXX9876543210 |_________| +11
A soma deu maior que 10 e o deslocamento de 11 não foi o suficiente para se chegar na string numérica. Diante desse problema, teremos que alterar esses caracteres placeholders de modo que quando este tipo de soma ocorrer um deslocamento de 11 retorne o algarismo correto da soma.
No dc.sed os placeholders são gerados da seguinte maneira:
9+8 9876543210765432109876543210 |_________| | | + 11 | |________________| placeholders
ou seja, os dois algarismos são “expandidos” de forma decrescente até o zero, e no caso do primeiro algarismo, ele é incluído na sequência e o segundo não. Essa expansão garante que o placeholder indexado em uma soma maior que 10 resulte no algarismo correto do resultado. Outros exemplos:
7+6
765432105432109876543210
|_________|
+ 11
5+5
543210432109876543210
|_________|
+ 11
Repare que isso também funciona para as somas menores que 10:
4+2
43210109876543210
|_________|
+11
Lembrando que, quando a soma é menor que 10, não importa como os placeholders são gerados, pois o valor da soma é obtido na string numérica final e não nos placeholders em si.
Somando dois números
Somar dois números é o mesmo que somar os algarismos correspondentes desses números e propagar os vai-uns que aparecem. Como primeiro exemplo, veremos como somar dois números de dois algarismos:
87 34 ----- ||_ 4+7 |_ 3+8
o que aconteceu, basicamente, foi a soma dos algarismos 7+4 e depois 3+8. A diferença agora é o tratamento do vai um, que não foi abordado anteriormente. Primeiramente, devemos saber como e quando ocorre um vai um. Um vai um ocorre sempre quando uma soma de dois algarismos é superior ou igual a 10 e um modo de se detectar isso é analisando a quantidade de caracteres da lookup table após o algarismo indexado.
7+7
7654321065432109876543210
|_________| |
+11 |_____________|
>10
Se a quantidade de algarismos após o algarismo indexado for maior que 10 quer dizer que uma soma superior ou igual a 10 ocorreu, isso é, um vai um foi gerado e deve ser propagado.
No outro caso, para somas menores que 10, a quantidade de algarismos após o algarismo indexado é sempre menor que 10, pois, como sabemos, o resultado é obtido na string numérica final:
2+5
210432109876543210
|_________| |
+11 |______|
<10
Quando um vai um é propagado, o resultado da soma subsequente é deslocado em uma unidade, isso é, o comportamento de um vai um é o mesmo que a adição de mais um placeholder.
67
+ 24
-----
||_ 7+4
| |_ 7654321032109876543210
| |_________| |
| + 11 |___+10___|
|_ 6+2 ____________________|
| |
| v
|_ 16543210109876543210
|_________|
| + 11
v
vai um
resultado: 91
Na soma 7+4 sabemos que o resultado é 11 e que após o deslocamento, temos mais de dez caracteres, o que indica a presença de um. A propagação do vai um ocorre obtendo-se o décimo caractere após o deslocamento e o acrescentando como placeholder na soma subsequente. No esquema acima esse caractere é o 1 e veja como ele entra à esquerda da soma 6+2 para acrescentar ao resultado uma unidade.
Esse conceito se espande para números com qualquer quantidade de algarismos:
678
+ 084
-------
|||_ 8+4
|| |_ 87654321032109876543210
|| |_________| |
|| + 11 |___+10___|
||_ 7+8 ____________________|
| | |
| | v
| |_ 276543210765432109876543210
| |_________| |
| + 11 |___+10___|
|_ 6+0 ____________________|
| |
| v
|_ 665432109876543210
|_________|
+ 11
resultado: 762
Um último exemplo mostrando o caso em que uma soma não propaga vai um:
104
+ 659
-------
|||_ 4+9
|| |_ 432108765432109876543210
|| |_________| |
|| + 11 |___+10___|
||_ 0+5 ____________________|
| | |
| | v
| |_ 30432109876543210
| |_________| |
| + 11 |sem vaium|
|_ 1+6
|_ 105432109876543210
|_________|
+ 11
resultado: 763
A soma 0+5 não gerou vai um porque não há mais de dez caracteres após o algarismo indexado.
Subtraindo dois algarismos
O ideal é se o processo de subtração fosse semelhante ao de adição, pois assim bastaria uma única sequência de código para realizar as duas operações. A boa notícia é que esses dois processos se assemelham bastante porém com a subtração um pouco mais trabalhosa. Veja:
4-3 XXXXXXXXX0123456789 |_________| + 11
Repare que a lookup table está invertida em relação à tabela de adição.
Bem, a substituição dos caracteres placeholders é um pouco tanto misteriosa:
ex: 4-6 432107890123456789 |_________| + 11
O primeiro algarismo é expandido que nem na adição. Já o segundo algarismo é expandido usando a sequência 0123456789 e o resultado é todos algarismos que vem logo após ele, sem incluí-lo. Em suma, o primeiro algarismo é expandido de forma decrescente entrando na sequência e o seguindo de forma crescente sem entrar na sequência.
ex: 4 - 6
9876543210 0123456789
^^^^^ ^^^
| _____|
| |
v v
43210 789 0123456789
|___________|
+ 11
Para se fazer 6-4=2, temos que inverter a ordem dos algarismos e fazer 4-6 no lugar. Esse método tem a peculiaridade de depender da ordem dos fatores pra se realizar a subtração. Esse detalhe será visto mais à frente quando falaremos do vai um negativo.
Outro exemplo:
ex: 3 - 3
9876543210 0123456789
^^^^ ^^^^^
| ____|
| |
v v
3210 456789 0123456789
|___________|
+ 11
Subtraindo dois números
Entendido a parte de subtração entre dois algarismos, agora vamos analisar a subtração entre dois números. Como sabemos, a subtração de dois números nada mais é que a subtração dos algarismos correspondentes dos números com o respectivo vai um negativo (ou borrow). Sempre ocorre um vai um negativo quando, matematicamente falando, o algarismo da direita é maior que o da esquerda, como em 4-6. O resultado é obtido após o acréscimo de dez unidades no algarismo da esquerda, como ocorre no método de subtração aprendido na escola:
24
- 16
----
||_ 4-6 = 14-6 = 8
|_ 2-1(-1) = 0
^^^^
borrow
Então, nesse caso, quando se faz 4-6, o resultado não é -2 e sim 8, pois 14-6=8.
Como esse método considera a ordem inversa dos algarismos, um borrow é gerado se o número da esquerda é maior que o da direita.
ex: 6-4 (o mesmo que 4-6, matematicamente)
5432104567890123456789
|_________| |
+11 |__________|
>10
resultado: 8
O esquema para se verificar se ocorreu borrow é o mesmo utilizado para verificar um carry: conta-se dez posições após o resultado e se existir alguma coisa lá então um vai um negativo é gerado. Entenda aqui o motivo em que a ordem dos algarismos importa, pois devido a forma de como a expansão é feita, esse método consegue nos dizer se ocorreu ou não um vai um.
Vejamos um exemplo de subtração numérica com propagação de vai um negativo:
247
- 602
-------
|||_ 7-2
|| |_ 6543210234567890123456789
|| |_________| |
|| + 11 |___+10___|
|| |
||_ 4-0 ____________________|
| | |
| | v
| |_ 5321001234567890123456789
| |_________| |
| + 11 |___+10___|
| |
|_ 2-6 ____________________|
| |
| v
|_ 51067890123456789
|_________|
+ 11
|resultado| = 355
Outro exemplo:
1099
- 1234
-------
|||_ 9-4
|| |_ 8765432104567890123456789
|| |_________| |
|| + 11 |___+10___|
|| |
||_ 9-3 ____________________|
| | |
| | v
| |_ 587654321034567890123456789
| |_________| |
| + 11 |___+10___|
| |
|_ 0-2 ____________________|
| | |
| | v
| |_ 3234567890123456789
| |_________|
| + 11
|_ 1-1
|_ 01234567890123456789
|_________|
+ 11
|resultado:| 0135
Para esse método funcionar corretamente sempre devemos subtrair do menor número o maior, isso é, o menor número sempre deve ser o primeiro. Para decidirmos qual número é maior ou menor que o outro devemos ter algum outro método para realizarmos comparações. Esse é o nosso próximo assunto.
Comparação de números em sed
Para se realizar a subtração com o método visto sempre utiliza-se o menor número como primeiro fator, e para isso, é preciso um algoritmo que retorne o menor número entre dois números dados. A primeira intuição é que, retirando os zeros iniciais, o número com menor quantidade de algarismo é o menor entre eles.
<5897,~147899, \ <589,7~1478,9 | <58,97~147,89 > desloca-se a vírgula para esquerda <5,897~14,789 | <,5897~1,4789 /
O processo acima encontra o menor/maior número entre dois números simplesmente verificando o número de algarismos de cada um. Se no fim do processo, que é quando a vírgula encontra o < ou o caractere ~, a vírgula estiver entre os algarismos de um número, esse número é o maior.
Esse processo é feito assim no sed:
:cmp1 s/^\(<[^,]*\)\([^,]\),\([^~]*~[^,]*\)\([^,]\),/\1,\2\3,\4/ tcmp1
Trocando em miúdos:
s/^(<[^,]*) ([^,]), ([^~]*~[^,]*) ([^,]),/ \1,\2\3,\4/
^^^^^^^^^^^^ ^^^^^^ ^^^^^^^^^^^^ ^^^^^ ^^^^^^^^^
[1] [2] [3] [4] [5]
Em [1], salvamos em \1 tudo antes da vírgula do primeiro número. Em [2], um dígito do primeiro número é obtido, mas se esse “dígito” for a vírgula, o processo termina (não casa). Em [3], salvamos tudo após a vírgula do primeiro número mais tudo antes da vírgula do segundo número. Em seguida, em [4], obtemos um dígito do segundo número. Por fim, em [5], andamos com a vírgula para a esquerda nos dois números. O loop termina quando a vírgula encontrar o sinal de menor (<,) ou o til (~,).
Agora, vamos analisar a outra situação que é quando os números têm a mesma quantidade de algarismos. A lógica aqui é comparar somente o algarismo mais à esquerda que se difere nos números.
<4567,~4321,~ <456,7~432,1~ <45,67~43,21~ <4,567~4,321~ <,4567~,4321~
O algarismo mais à esquerda que se difere no dois números é o 5 e o seu corresponde é o 3. Como 5 > 3, concluímos que o número 4567 é maior que o 4321.
Essa comparação é feita assim:
s/$/;,0123456789/ /^<\([^~]*\)\([^~]\)[^~]*~\1\(.\)[^;]*;.*\3.*\2/ s/</>/
Se a segunda expressão regular casar, então o sinal de menor é trocado pelo de maior. O sinal no início é para indicar se o primeiro número é maior ou menor igual que o segundo.
No fim dos números, inclui-se uma lookup table que será usada para se realizar a comparação dos algarismos. Os algarismos correspondentes ficam em \3 e em \2 e se o conteúdo desses retrovisores estiverem em sequência, o primeiro número é maior, gerando uma inversão dos sinais. Como queremos o menor número sempre à esquerda, utilizamos a seguinte linha em sed para realizar essa tarefa:
s/^>\([^~]*~\)\([^~]*~\)/>\2\1/
Veja o que acontece quando fazemos 12345-67 no sedsed [2]:
PATT:<12345,~67,~$ HOLD:$ COMM::cmp1 COMM:s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/ PATT:<1234,5~6,7~$ HOLD:$ COMM:t cmp1 COMM:s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/ PATT:<123,45~,67~$ HOLD:$ COMM:t cmp1 COMM:s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/ PATT:<123,45~,67~$ HOLD:$ COMM:t cmp1 COMM:s/$/;,0123456789/ PATT:<123,45~,67~;,0123456789$ HOLD:$ COMM:/^<\([^~]*\)\([^~]\)[^~]*~\1\(.\)[^;]*;.*\3.*\2/ s/</>/ PATT:>123,45~,67~;,0123456789$ HOLD:$ COMM:s/^>\([^~]*~\)\([^~]*~\)/>\2\1/ PATT:>,67~123,45~;0123456789$
A primeira linha destacada representa a entrada formatada. A segunda é o fim do processo de comparação, e nesse caso, vemos que o primeiro número é maior que o segundo. Na terceira linha destacada, o sinal inicial ‘<‘ é trocado pelo ‘>’ devido ao primeiro número ser o maior entre eles. Já na última linha ocorre a troca de posições entre o maior número e o menor, sendo que o menor número sempre deve ficar à esquerda.
O script: addsub.sed
Para fixar o que aprendemos nada melhor que um script que realiza adição e subtração entre dois números. Ele foi baseado inteiramente no bc.sed[1] e demais detalhes sobre ele podem ser conferidos no código do script ou também na sua visualização pelo sedsed[2].
#!/bin/sed -f
# [addsub.sed]
# Soma e subtrai dois números usando o sed.
#
# [Autor]
# Marcos Paulo Ferreira (daemonio)
# undefinido gmail com
# https://daemoniolabs.wordpress.com/
#
# [Uso]
# $ chmod +x addsub.sed
# $ echo '1234+56789' | ./addsub.sed
# 58023.
# $ echo '1234-56789' | ./addsub.sed
# -055555.
#
# obs: a operação deve ser sempre entre
# números inteiros positivos, ou seja,
# da forma a+b ou a-b, a>=0 e b>=0.
#
# Versão 1.0 by daemonio @ Fri Mar 1 00:59:02 BRT 2013
#
# Formata a entrada.
# <NUM1,~NUM2,~SINAL
s/\([0-9]*\)\(.\)\([0-9]*\)/<\1,~\3,~\2/
# Desloca as vírgulas a fim de se
# encontrar o menor número.
:cmp1
s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/
t cmp1
# Compara os números.
s/$/;,0123456789/
/^<\([^~]*\)\([^~]\)[^~]*~\1\(.\)[^;]*;.*\3.*\2/ s/</>/
# Coloca o menor número à esquerda.
s/^>\([^~]*~\)\([^~]*~\)/>\2\1/
# Formato para addsub deve ser do tipo:
# NUM1~SINAL0NUM2,.~;LOOKUP
# Acrescenta sinal de menor no resultado se
# o segundo número é maior e a operação é
# subtração.
s/\(<,[^~]*\)~\([^~]*\)~-/\1~-0\2~-/
# Retira as vírgulas.
s/..\([^~]*\)~\([^,]*\),\([^~]*\)~/\1~\2\3,.~/
# Adiciona as lookup tables de acordo com a
# operação.
s/~+;.*/~;9876543210;9876543210/
s/~-;.*/~;0123456789;9876543210/
# Realiza soma e subtração.
:addsub1
s/\(.\{0,1\}\)\(~[^,]*\)\([0-9]\)\(\.*\),\([^;]*\)\(;\([^;]*\(\3[^;]*\)\).*X*\1\(.*\)\)/\2,\4\5\9\8\7\6/
s/,\([^~]*~\).\{10\}\(.\)[^;]\{0,9\}\([^;]\{0,1\}\)[^;]*/,\2\1\3/
/^~.*~;/ !b addsub1
# Formata a saída.
:endbin
s/.\([^,]*\),\([0-9.]*\).*/\1\2/
# EOF
O script só aceita entradas do tipo a+b e a-b, sendo a e b inteiros positivos. Essa limitação é para se evitar o jogo de sinais para se decidir qual será o sinal do resultado. Veremos esse jogo de sinais no próximo tópico da série.
Vamos testar o script:
$ echo '0123456789-9876543210' | ./addsub.sed -09753086421. $ echo '0123456789-9876543210' | bc -9753086421 $ echo '32232456679786978567543620757589+8796521243135231135879869069886' | ./addsub.sed 41028977922922209703423489827475. $ echo '32232456679786978567543620757589+8796521243135231135879869069886' | bc 41028977922922209703423489827475
O script não está completo porque ainda não há uma verificação de sinais adequada e a saída não está completa. Melhoraremos esse código também no próximo tópico da série.
Conclusão
Nessa parte, vimos como somar e subtrair dois números. Vimos que esses dois processos podem ser feitos com a mesma sequência de código, o que facilita em muito a programação. No próximo tópico veremos como somar e subtrair dois números decimais (ex: 0.44 + 0.12) e estenderemos os conceitos vistos aqui para que eles se apliquem em qualquer caso.
Referências
[1] dc.sed by Greg Ubben (Acessado em: Março/2013)
http://sed.sourceforge.net/grabbag/scripts/dc.sed
[2] sedsed by Aurélio Jargas (Acessado em: Março/2013)
http://aurelio.net/projects/sedsed/
[3] Overview of How the dc.sed Script Works by Greg Ubben (Acessado em: Março/2013)
http://sed.sourceforge.net/grabbag/scripts/dc_overview.htm
Dæmonio Labs 