Calculando com o sed – Parte II

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.

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 (&lt,) 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

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s