Adição e subtração
Capítulo 4: Jean Pierre Descamps; Géry Jean Antoine Bioul; Gustavo D.Sutter
Synthesis of Arithmetic Circuits – New Jersey, John Wiley & Sons, 2006.
Introdução
•
Adição é usada como uma operação primitiva para computar as maioria
das funções aritméticas.
•
Para minimizar o tempo de computação várias idéias tem sido propostas.
– Uma delas consiste em modificar o algoritmo clássico tal que o tempo
de computação de cada vai-um seja mínimo; a complexidade no tempo
ainda é proporcional a n, mas essa constante de proporcionalidade é
menor.
– Uma outra abordagem baseia-se em diferentes sistemas de
numeração; em vez de adicionar dois números de n dígitos na base B,
dois números na base Bs de n/s dígitos são considerados.
– Vários algoritmos, diferentes dos clássicos e geralmente baseados em
alguma estrutura em árvore, tem sido propostos. Se o paralelismo
implícito for considerado, atinge-se um tempo de execução proporcional
a log n.
Adição de números naturais
Algoritmo básico. Considerar as representações base B de dois números de n dígitos:
x  xn1.Bn1  xn2 .Bn2  ... x0 .B0
y  yn1.Bn1  yn2 .Bn2  ... y0 .B0
O seguinte algoritmo computa a representação de z = z + y + cin de n+1 dígitos.
Algoritmo 4.1:
q(0) := c_in;
for i in 0..n-1 loop
if x(i) + y(i) + q(i) > B-1 then q(i+1) := 1; else q(i+1) := 0;
end if;
z(i) := (x(i) + y(i) + q(i)) mod B;
end loop;
z(n) := q(n);
Como q(i+1) é uma função de q(i) o tempo de execução do algoritmo
anterior é proporcional a n.
Modificação do algoritmo para reduzir o tempo de execução:
- definir duas funções binárias de duas variáveis, a saber, funções
de propagação (p) e geração (g):
p(a,b) = 1 se a + b = B-1,
g(a,b) = 1 se a + b > B-1,
p(a,b) = 0 caso contrário;
g(a,b) = 0 caso contrário.
- o vai-um q i+1 pode ser calculado assim:
if p( x(i), y(i) ) = 1 then q(i+1) := q(i); else q(i+1) := g( x(i),y(i) ); end if;
Algoritmo com geração e
propagação de vai-um
Algoritmo 4.2:
-- computação das condições de geração e propagação:
for i in 0..n-1 loop g(i):= g(x(i),y(i));p(i) := p(x(i),y(i));
end loop;
-- computação do vai-um:
q(0) := c_in;
for i in 0..n-1 loop
if p(i)=1 then q(i+1):= q(i); else q(i+1):= g(i); end if;
end loop;
-- computação das soma:
for i in 0..n-1 loop z(i):= (x(i)+y(i)+q(i)) mod B; end loop;
z(n):= q(n);
Algoritmo mais rápido
-- computação do vai-um:
q(0) := c_in;
for i in 0..n-1 loop
if p(i)=1 then q(i+1):= q(i); else q(i+1):= g(i); end if;
end loop;
Exemplo: q(0) = c_in
q(1) = g(0)v p(0).q(0)
q(2) = g(1)v p(1).q(1)
q(2) = g(1) v g(0).p(1) v q(0).p(0).p(1)
....
q(i) = g(i-1)v p(i-1).q(i-1)
v = or
. = and
Ou seja, os valores de q(1), q(2),...,q(n) podem ser calculados em
paralelo:
i  1.2,...,n : q (i )  g (i  1) 
g (i  2). p (i  1) 
g (i  3). p (i  2). p (i  1) 
g (i  4). p (i  3). p (i  2). p (i  1) 
...
g (0). p (1).....p (i  1) 
q (0). p (0). p (1).....p (i  1)
Algoritmo mais rápido (cont.)
Algoritmo 4.3:
--computação das condições de geração e propagação:
for i in 0..n-1 loop g(i):= g(x(i).y(i)); p(i):= p(x(i).y(i));
end loop;
-- computação do vai-um:
q(0) := c_in;
for i in 1..n loop
q(i):= g(i-1) or g(i-2)*p(i-1) or ... or g(0)*p(1)*...* p(i-1) or q(0) * p(0) * p(1)* ... * p(i-1);
end loop;
-- computação da soma
for i in 0..n-1 loop z(i) := (x(i) + y(i) + q(i)) mod B; end loop;
z(n) := q(n);
O algoritmo 4.3 consiste de 3 iterações cujas operações podem ser executadas em
paralelo, pois q(i) depende apenas de x, y e c_in, mas não de vai-um anteriores.
Não obstante, a execução de
q(i):= g(i-1) or g(i-2)*p(i-1) or ... or g(0)*p(1)*...* p(i-1) or q(0) * p(0) * p(1)* ... * p(i-1);
implica na computação de uma função de (2.i+1) variáveis.
Para simplificação, dois novos conceitos são introduzidos: dot operation e funções
de geração e propagação generalizadas.
Dados 2 vetores binários e 2 elementos ai =(ai 0, ai 1) e ak = (ak0, ak1) um dot
operation define uma função de B22  B22
em B22 :
ai  ak  (ai 0  ak 0 . ai1 , ai1.ak1 )
Exemplo:
ai  ( g1 , p1 ) e ak  ( g0 , p0 )
( g1 , p1 )  ( g0 , p0 )  ( g1  g0 . p1 , p1. p0 )
Funções de geração e propagação generalizadas.
Dadas as funções de geração e de propagação g(i) e p(i), para i {0,1,...,n  1}
as funções de geração e propagação generalizadas g(i:i-k) e p(i:i-k), para
i {0,1,...,n  1} e k {0,1,...,i}
são assim definidas:
( g (i : i  k ), p(i : i  k ))  ( g (i), p(i))  ( g (i  1), p(i  1))
 ( g (i  2), p(i  2))  ... ( g (i  k ), p(i  k ))
Baseado no cálculo paralelo de q(i) e nas funções generalizadas temos:
q(i+1) = g(i:i-k)V p(i:i-k).q(i-k).
Algoritmo com funções de geração e
propagação generalizadas
Algoritmo 4.4:
-- computação das condições de geração de propagação:
for i in 0..n-1 loop g(i) := g(x(i),y(i)); p(i):= p(x(i),y(i));
end loop;
-- computação das condições de geração e propagação generalizadas:
for i in 1..n loop
(g(i-1):0),p(i-1):0)):= (g(i-1),p(i-1)) dot (g(i-2),p(i-2)) dot ... dot (g(0),p(0));
end loop;
-- computação do vai-um:
q(0) := c_in;
for i in 1..n loop q(i) := g(i-1:0) or p(i-1:0)* q(0); end loop;
-- computação da soma:
for i in 0..n-1 loop z(i) := (x(i)+y(i)+q(i)) mod B; end loop;
z(n) := q(n);
A segunda iteração do algoritmo anterior
-- computação das condições de geração e propagação generalizadas:
for i in 1..n loop
(g(i-1):0),p(i-1):0)):= (g(i-1),p(i-1)) dot (g(i-2),p(i-2)) dot ... dot (g(0),p(0));
end loop;
pode ser realizada de várias formas.
Dado um conjunto de dados de entrada a(0), a(1),..., a(n-1) e um
operador associativo (dot), computar
b(0)  a(0),
b(1)  a(1)  a(0),
b(2)  a(2)  a(1)  a(0),
...
b(n  1)  a(n  1)  a(n  1)  ... a(1)  a(0)
Um algoritmo simples seria
b(0) := a(0); for i in 1..n-1 loop b(i):= a(i) dot b(i-1); end loop.
Não obstante, muitos algoritmos melhores tem sido propostos, dentre
os quais dois serão descritos a seguir.
Na definição de dot_procedure, os parâmetros são um número natural n ( o número
de dados de entrada) e dois vetores de n componentes (os dados de entrada e
saída).
Procedure dot_procedure (n: in natural;
a: in data_vector (0..n-1); b: out data_vector (0..n-1));
Assume-se que n é uma potência de 2 (se necessário, devem ser adicionados 0’s).
O primeiro algoritmo consiste em:
a) computar
c(0)  a(1)  a(0),
c(1)  a(3)  a(2) ,..., c((n / 2)  1)  a(n  1)  a(n  2);
b) chamar o dot_procedure com parâmetros n/2, c e d, tais que
d (0)  b(1),
d (1)  b(3), d (2)  b(5),..., d ((n / 2)  1)  b(n  1);
c) computar os componentes que faltam de b:
b(2)  a(2)  d (0), b(4)  a(4)  d (1) ,..., b(n / 2)  a(n  2)  d (n / 2)  2);
O esquema de computação para n = 16
Algoritmo Dot Procedure (1)
Algoritmo 4.5:
Procedure dot_procedure (n: in natural; a: in data_vector(0..n-1);
b: out data_vector(0..n-1)) is
c,d: data_vector(0..(n/2)-1);
begin
if n = 2 then b(0) := a(0); b(1) := a(1) dot a(0);
else
for i in 0..(n/2)-1 loop c(i):= a((2*i)+1 dot a(2*i);
end loop;
dot_procedure (n/2, c, d);
b(0) := a(0);
for i in 1..(n/2)-1 loop b(2*i) := a(2*i) dot d(i-1);
b((2*i) + 1) := d(i); end loop;
end if;
end dot_procedure;
Tempo de execução
Ambos os loops for são de dot operations que podem ser executados
em paralelo.
O tempo de execução total T(n) é igual a Tdot + T(n/2) + Tdot, com
T(2) = Tdot, tal que
T(n) = (2.(log2n)-1).Tdot.
n=16
Tdot
n=8
T(n/2)
n=4
n=2
Tdot
Temos log2n iterações, cada qual com 2.Tdot, com exceção
da última que tem apenas um Tdot, portanto:
T(n) = (2.(log2n)-1).Tdot.
Segundo algoritmo
O segundo algoritmo consiste em:
a) chamar dot_procedure com parâmetros n/2, a(0..(n/2)-1), e b(0..(n/2)-1);
b) chamar dot_procedure com parâmetros n/2, a((n/2)..n-1), e c, tal que
c(0)  a(n / 2), c(1)  a((n / 2)  1)  a(n / 2) ,
..., c((n / 2)  1)  a(n  1)  a(n  2)  ... a(n / 2);
c) computar os componentes que faltam de b,
b(n / 2)  c(0)  b((n / 2)  1),
b((n / 2)  1)  c(1)  b((n / 2)  1) ,
...
b(n  1)  c((n / 2)  1)  b((n / 2)  1);
Esquema de computação para n = 16
Algoritmo Dot Procedure (2)
Algoritmo 4.6:
Procedure dot_procedure (n: in natural; a: in data_vector(0..n-1);
b: out data_vector(0..n-1)) is
c: data_vector(0..(n/2)-1);
begin
if n = 2 then b(0) := a(0); b(1) := a(1) dot a(0);
else
dot_procedure (n/2, a(0..(n/2)-1), b(0..(n/2)-1);
dot_procedure (n/2, a((n/2)-1)..n-1), c);
for i in 1..(n/2)-1 loop b(i+n/2)) := c(i) dot b((n/2)-1);
end loop;
end if;
end dot_procedure;
Ambas as chamadas de procedimentos podem ser executadas em paralelo e os loops for são de dot
operations que podem ser executadas em paralelo.
O tempo de execução total T(n) é igual a T(n/2)+Tdot , com
T(2) = Tdot, tal que
T(n) = (log2n).Tdot.
Parallel-Prefix Addition
Algoritmo 4.7
a, b: data_vector (0..n-1, 0..1);
begin
-- computação de condições de geração e propagação
for i in 0..n-1 loop a(i,0) := g(x(i), y(i)); a(i,1):= p(x(i), y(i))); end loop;
-- computação de condições de geração e propagação generalizadas
dot_procedure (n, a, b);
-- computação de vai-um
q(0) := c_in;
for i in 1..n loop q(i) := b(i,0) or b(i,1)* q(0); end loop;
-- computação de soma
for i in 0..n-1 loop z(i) := (x(i) +y(i) + q(i) ) mod B; end loop;
z(n) := q(n);
• O algoritmo precedente é constituído de 3 iterações, cujas operações
podem ser executadas em paralelo, e uma chamada para o
dot_procedure cujo tempo de execução é proporcional a log(n).
•
Assim, para valores grandes de n, o tempo de execução do algoritmo
é praticamente proporcional a log(n).
• O tempo de execução logaritmico pode ser obtido por diferentes
algoritmos usando dois novos procedimentos
(carry_lookahead_procedure e carry_procedure).
Carry_lookahead_procedure
(preliminares)
procedure carry_lookahead_procedure (n: in natural; a: in data_vector (0..n-1,
0..1); c_in: in bit; q: out bit_vector (1..n));
computa os n vai-um’s q(1), q(2), ..., q(n), em função de n condições de
geração e propagação g(t) = a(t,0) e p(t) = a(t,1), e de c_in,
q (t )  a (t  1,0) 
a (t  2,0).a (t  1,1) 
...
a (0,0). a (1,1)....a (t  1,1) 
c _ in . a (0,1).a (1,1).....a (t  1,1)
t  {1,2,...,n}
Carry_procedure (preliminares)
procedure carry_procedure (n: in natural; b: in data_vector (0..n-1, 0..1); c_in:
in bit; q: out bit_vector (1..n));
Computa os n vai-um’s q(1), q(2), ..., q(n), em função de n condições de geração e
propagação generalizadas g(t:0) = b(t,0), p(t:0) = b(t,1) e de c_in:
q(t )  b(t 1,0)  c _ in . b(t  1,1)
Carry_lookahead_procedure
Assume que n pode ser fatorado sob a forma n = k.s. O algoritmo consiste em:
chamar k vezes o dot_procedure com parâmetros s, a(j.s .. j.s + s-1) e
c(j, 0..s-1), onde j {0,1, ..., k  1} tal que
c( j,0)  a( j.s)  ( g ( j.s), p( j.s)),
c( j,1)  a( j.s  1)  a( j.s)  ( g ( j.s  1 : j.s), p( j.s  1 : j.s),
...
c( j, s  1)  a( j.s  s  1)  a( j.s  s  2)  ... a( j.s)
 ( g ( j.s  s  1 : j.s), p( j.s  s  1 : j.s)
Carry-lookahead-procedure(cont.)
Chamar o carry_lookahead_procedure com parâmetros k, c(0..k-1,s-1), c_in e d, tal que
d ( j )  g ( j.s  1 : 0)  c _ in. p( j.s  1 : 0)  q( j.s)
c_in
Chamar k vezes o carry_procedure com parâmetros s-1, c(j, 0..s-2), d(j) e
e(j, 0..s-2), onde
j {0,1, ..., k  1} tal que
e( j, i)  ( g ( j.s  i : j.s)  q( j.s). p( j.s  i : j.s)  q( j.s  i  1)
carry_lookahead_procedure de 16 entradas
Algoritmo 4.8
procedure carry_look_ahead_procedure
(n: in natural; a: in data_vector (0..n-1, 0..1); c_in: in bit; q: out bit_vector (1..n))
is
c: data_vector (0..k-1, 0..s-1, 0..1); d bit_vector (0..k-1);
begin
for j in 0..k-1 loop dot_procedure (s, a(j*s..j*s+s-1), c(j, 0..s-1)); end loop;
carry_lookahead_procedure (k, c(0..k-1, s-1), c_in, d);
for j in 0..k-1 loop
carry_procedure (s-1, c(j, 0..s-2), d(j), e(j, 0..s-2));
end loop;
for j in 1..k-1 loop q(j*s) := d(j); end loop;
for j in 0..k-1 loop
for i in 0..s-2 loop q(j*s+i+1) := e(j,i); end loop;
end loop;
end carry_lookahead_procedure;
Carry_procedure
O carry_procedure computa:
q(t )  b(t  1,0)  c _ in.b(t  1,1)
(equação 4.10)
Procedure carry_procedure
(n: in natural; b: in data_vector (0..n-1, 0..1); c_in : in bit; q: out bit_vector
(1..n))
is begin
for t in 1..n loop q(t)= b(t-1,0) v c_in.b(t-1,1); end loop;
end carry_procedure;
Tempo de execução
Seja T(n) o tempo de execução de carry_lookahead_procedure, T1(n) o tempo de execução de
dot_procedure, e T2 o tempo de execução de qualquer equação 4.10 do carry_procedure.
As k chamadas ao dot_procedure podem ser executadas em paralelo, e o mesmo ocorre com as k
chamadas para carry_procedure. Além disso, dentro do carry_procedure a equação 4.10 pode
ser calculada em paralelo. Assim,
T (k.s)  T1 (s)  T (k )  T2
Assume-se que n = s1.s2 .... sm. O algoritmo obtido pelas chamadas recursivas de
carry_lookahead_procedure tem um tempo de computação que pode ser calculado como
segue:
T ( s1.s2 .....sm )  T1 ( s1 )  T ( s2 .....sm )  T2 ,
T ( s2 .....sm )  T1 ( s2 )  T ( s3 .....sm )  T2 ,
...
T ( sm 1.sm )  T1 ( sm 1 )  T ( sm )  T2 ,
T ( sm )  T1 ( sm )  T2 ,
Tal que
T (s1.s2 .....sm )  T1 (s1 )  T1 (s2 )  ... T1 (sm )  m.(T2 )
Em particular, se n = sm,
T (n)  m.(T1 (s)  T2 ), onde m  logs n
Carry_lookahead_addition
Algoritmo 4.9
a: data_vector (0..n-1, 0..1);
begin
-- computação de condições de geração e propagação
for i in 0..n-1 loop a(i,0) := g(x(i), y(i)); a(i,1):=p(x(i), y(i)); end loop;
-- computação de vai-um
carry_lookahead_procedure (n, a, c_in, q);
q(0) := c_in;
-- computação de soma
for i in 0..n-1 loop z(i) := (x(i)+y(i)+q(i)) mod B; end loop;
z(n): q(n);
end;
Adição de operandos longos
No caso de adições com operandos longos, é necessário quebrar os
operandos de n dígitos em fatias de s dígitos.
Um exemplo típico é a implementação de operações aritméticas de n
bits em microprocessadores de m bits, com m<n.
Como um número na base B, de n dígitos equivale a um número na
base Bs de n/s dígitos, pode ser usada uma versão modificada do
algoritmo 4.1,
natural_addition, que soma dois números de s dígitos.
Procedure natural_addition
(s: in natural;
carry : in bit;
x, y: in digit_vector (0..s-1);
next_carry: out bit;
z: out digit_vector (0..s1);
Adição de operandos longos
Então, o seguinte algoritmo computa x + y + cin.
Algoritmo 4.10
q:= c_in;
for i in 0..n/s-1 loop
natural_addition (s, q, x(i*s..(i*s)+s-1), y( i*s..(i*s) + s-1), q, z(i*s..(i*s)+s-1));
end loop;
z(n) := q;
n = 16, s = 4
i=0
i=1
...
i=n/s-1=16/4-1=3
x(0.4..0.4+3) = x (0..3)
x(1.4..1.4+3) = x (4..7)
.....
x(3.4 .. 3.4+3) = x (12..15)
y (0..3)
y (4..7)
.....
y (12..15)
z (0..3)
z (4..7)
.....
z (12..15)
Tempo de execução
Dependendo do procedimento natural_addition, o tempo de execução
é proporcional a (n/s).s = n ou (n/s).log s.
Observa-se que versões modificadas de outros algoritmos não diminui
esse tempo - todos eles incluem n comandos:
z(i) := (x(i) + y(i) + q(i)) mod B;
equivalente, em base Bs a n/s comandos
natural_addition (s, q(i), x(i*s..(i*s)+s-1), y (i*s..(i*s)+ s-1), not_used,
z(i*s..(i*s)+s-1));
Como os n/s comandos devem ser executados sequencialmente
(restrição de operandos longos), o tempo de execução deve ser
proporcional a (n/s).s = n ou (n/s).log(s).
Adição multioperando
Uma outra operação importante é a adição multioperando, que é a
computação de z  x ( 0)  x (1)  ...  x ( m1) onde todo x (i )
é um
número natural.
Assumir que a soma total não exceda n dígitos e que todos os operandos são
expressos em n dígitos. O seguinte algoritmo computa z.
Algoritmo: adição básica multioperando
Algoritmo 4.11
accumulator:= 0;
for j in 0..m-1 loop
natural_addition (n, 0, accumulator, x(j), not_used, accumulator);
end loop;
z := accumulator;
O tempo de execução é proporcional a m.n ou m.log n dependendo do
procedimento de natural_addition selecionado.
Algoritmo three-to-two
Um conceito interessante para execução de adições multioperando é o storedcarry encoding do resultado de uma adição de 3 operandos.
Assumir que um procedimento
procedure three-to-two (w, x, y: in natural; u, v: out natural);
seja definido, e que compute u e v tais que
w + x + y = u + v.
( 0)
(1)
( m1)
Então o seguinte algoritmo computa a soma z  x  x  ...  x
de m números naturais.
Algoritmo 4.12 :
three-to-two (x(0), x(1),x(2), u(0), v(0)));
for j in 3..m-1 loop
three-to-two (x(j), u(j-3), v(j-3), u(j-2), v(j-2));
end loop;
natural_addition (n, 0, u(m-3), v(m-3), not_used, z);
stored-carry_encoding
O procedimento three-to-two consiste em expressar a soma z de três números
naturais (w, x, y) em forma de par (u, v) de dois números naturais de tal
forma que z = u + v. Assumir que w, x, e y são números de n dígitos, e q_in
seja um número de 1 dígito. O seguinte algoritmo computa dois números de
n dígitos u e v e um número de 1 dígito q_out, tais que
w + x+ y + q_in = q_out.Bn + u + v.
Algoritmo 4.13 : stored-carry encoding
procedure stored-carry_encoding (w, x, y: in digit_vector (0..n-1); q_in: in digit;
u, v: out digit_vector (0..n-1); q_out: out digit) is
begin
q(0) := q_in;
for i in 0..n-1 loop
q(i+1) := (w (i) + x(i) + y(i))/B;
u(i) := (w(i) + x(i) + y(i)) mod B;
end loop;
v:= q(0..n-1); q_out:= q(n);
end stored-carry_encoding
O algoritmo stored-carry_encoding é similar ao algoritmo básico de adição.
Dois dígitos são computados a cada passo, e o primeiro, q(i+1), pode ser
considerado como um carry na base B.
Não obstante, q(i+1) não depende de q(i) tal que n passos de iteração possam
ser executados em paralelo. Em outras palavras, a cada passo o carry
q(i+1) é guardado ao invés de ser transferido para a próxima iteração. Por
essa razão, o par (u, v) é dito ser da forma stored-carry de z.
O seguinte algoritmo multioperando, onde x(j,i) significa x(j)(i), é deduzido dos
dois algoritmos anteriores (assumindo que z seja um número de n dígitos e
que todos os operandos sejam expressos em n dígitos).
Carry-save addition
Algoritmo 4.14 – carry-save addition
stored-carry_encoding (x (0, 0..n-1), x(1, 0..n-1), x(2, 0..n-1), 0, u(0, 0..n-1),
v(0, 0..n-1), not_used);
for j in 3..m-1 loop
stored-carry_encoding (x(j, 0..n-1), u(j-3, 0..n-1), v(j-3, 0..n-1), 0, u(j-2, 0..n-1),
v(j-2, 0..n-1), not_used);
end loop;
z(0):= u(m-3, 0);
natural_addition (n-1, 0, u(m-3, 1..n-1), v(m-3, 1..n-1), not_used, z(1..n-1));
O algoritmo acima é constituído de m-2 chamadas a stored-carry_encoding e
uma chamada ao procedimento de adição de (n-1) dígitos, tal que o tempo
de execução seja aproximadamente proporcional a m+n ou m+ log(n).
Adição longa multioperando
Uma adição longa multioperando pode ser executada combinando os
algoritmos 4.10 e 4.11.
Algoritmo 4.15
accumulator := 0;
for j in 0..m-1 loop
q:= 0;
for i in 0..n/s -1 loop
natural_addition(s, q, accumulator (i*s..(i*s)+s-1),
x(j,i*s.. (i*s)+s-1), q, accumulator (i*s.. (i*s) + s-1));
end loop;
end loop;
z:= accumulator;
O tempo de execução é proporcional a m.(n/s).s=m.n ou m.(n/s).log(s). O
stored-carry_encoding pode também ser usado. A redução de m
operandos de n dígitos para 2 operandos de n dígitos pode ser realizada,
quebrando cada operando de n dígitos em n/s operandos de s-dígitos e
chamando o procedimento stored-carry_encoding (m-2).(n/s) vezes.
Então, os operandos assim obtidos são somados.
Algoritmo 4.16 – carry-save long-multioperand addition
-- m-to-2 reduction
q:= 0;
for i in 0.. n/s -1 loop
stored-carry_encoding (x(0, i*s.. (i*s)+s -1), x(1, i*s.. (i*s) + s-1), x(2, i*s..(i*s) + s-1), q,
u(i*s.. (i*s) + s-1), v(i*s.. (i*s) + s-1), q);
end loop;
for j in 3..m-1 loop
q := 0;
for i in 0..n/s-1 loop
stored-carry_encoding (x(j, i*s..(i*s)+s-1), u(i*s..(i*s)+s-1), v(i*s..(i*s)+s-1), q, u(i*s..(i*s)+s1), v(i*s..(i*s)+ s-1), q);
end loop;
end loop;
-- 2-operand addition;
q:= 0;
for i in 0..n/s-1 loop
natural_addition (s, q, u(i*s..(i*s)+s-1), v(i*s..(i*s)+s-1), q, z(i*s.. (i*s)+s-1);
end loop;
A redução m-to-2 é realizada em (m-2).(n/s) passos e o tempo de execução de adição de
2 operandos é proporcional a (n/s).s = n ou (n/s).log s. O tempo de execução total é
aproximadamente proporcional a (n/s).(m+s) ou (n/s).( m + log s) ao invés de (n/s).m.s
ou (n/s).m.log.s.
Subtração de números naturais
• O seguinte algoritmo computa representação de n dígitos de z = x –
y – bin onde bin é o empresta um inicial, igual a 0 ou 1. Se z é
negativo, ou seja, z não é um número natural, o empresta um q(n)
de saída é igual a 1.
• Algoritmo 4.17
q(0) := b_in;
for i in 0..n-1 loop
if x(i) – y(i) – q(i) < 0 then q (i+1) := 1; else q(i+1) := 0;
end if; r(i) := (x(i) – y(i) –q(i)) mod B;
end loop;
negative:= q(n);
Subtração de inteiros
No caso de inteiros, os algoritmos de adição e subtração dependem da
particular representação.
Adição complemento de B:
Dados dois inteiros x e y, em complemento de B de n dígitos, e um carry cin
inicial igual a 0 ou 1, então z = x + y + cin é um inteiro em complemento de
B de n+1 dígitos.
Então os números naturais associados a x, y e z são R(x) = x mod Bn+1, R(y) =
y mod Bn+1, R(z) = z mod Bn+1, tais que
R( z)  ( x  y  cin ) modBn1  (R( x)  R( y)  cin ) modBn1
Assim, o algoritmo de adição consiste em representar x e y com n+1 dígitos e
somar os números naturais correspondentes, bem como o carry inicial,
módulo Bn+1 (isto é, sem levar em conta o carry de saída).
Algoritmo 4.18 – Adição complemento de B
if x(n-1) < B/2 then x(n) := 0; else x(n) := B-1; end if;
if y(n-1) < B/2 then y(n) := 0; else y(n) := B-1; end if;
natural_addition (n+1, c_in, x, y, not_used, z);
Exemplo: assumir que B = 10, n = 4, cin = 0, x = -2345, e y = -3674.
Ambos x e y são negativos tal que eles sejam representados por R(x) = - 2345
+ 104 = 7655 e R(y) = - 3674 + 104 = 6326.
Primeiro representamos x e y com 5 dígitos: R(x)= 97655 e R(y) = 96326.
Então somamos R(x) e R(y) módulo 105 : 97655 + 96326 mod105 =93981.
Como 9  B / 2  5 o inteiro representado é negativo e igual a 93981 – 105 =
-6019, que é a soma de x e y.
Mudança de sinal em complemento de B
(negação)
Dado um inteiro x em complemento de B de n dígitos, o negativo z = - x é um
inteiro em complemento de B de n+1 dígitos (na realidade, o único caso em
que o número –x não pode ser representado em n dígitos é quando x = -Bn /2
e –x = Bn /2; isto é, -x = 0.Bn + (B/2).Bn -1 + 0.Bn -2 + ... + 0.B0).
A computação da representação de –x é baseada na seguinte propriedade:
Propriedade 4.3: dados dois números naturais na base B de m dígitos,
a  am1Bm1  am2 Bm2  ... a0 B0
b  (B 1  am1 )Bm1  (B 1  am2 )Bm2  ... (B 1  a0 )B0
então,
b  Bm  a 1
Algoritmo 4.19 – mudança de sinal
em complemento de B
if x (n-1) < B/2 then x(n) := 0; else x(n) := B-1; end if;
for i in 0..n loop x’(i) := B-1-x(i); end loop;
natural_addition (n+1, 1, x’, 0, not_used, z);
Exemplo 1:
Assumir que B = 10, n = 4, x = 2345; x é positivo e representado por
R(x) = x = 2345.
Primeiro, representar x com 5 dígitos: R(x)= 02345. Então
complementar todos os dígitos de B -1 = 9, e adicionar 1:
(97654 +1) mod 105 = 97655.
O inteiro representado por 97655 é 97655 – 105 = -2345.
exemplos
Exemplo 2:
Se x = -5000 então a representação em 4 dígitos e x é 5000 e a de 5
dígitos é 95000. Complementando todos os dígitos e adicionando 1,
o resultado obtido é (04999 + 1) módulo 105 = 05000, que é a
representação do número positivo de 5000.
Exemplo 3:
Se x = 0 então a representação em 4 dígitos de x é 0000 e de 5
dígitos, 00000. Complementando todos os dígitos e adicionando 1 o
resultado obtido é (99999+1) mod 105 = 00000, que é a
representação positiva de 0.
Subtração complemento de B
Dados dois inteiros x e y de n dígitos e complemento de B, e um borrow bin igual
a 0 ou 1, então z = x – y – bin é um inteiro em complemento de B de n+1
dígitos.
Assumir que x e y são representados em n + 1 dígitos. Então os números
naturais associados a x, -y e z são R(x) = x mod Bn+1, R(-y) = (y’+1) mod Bn+1
e R(z) = z mod Bn+1, tais que
R( z)  ( x  y  bin ) modBn1  (R( x)  y'(1  bin )) modBn1
Assim o algoritmo consiste em representar x e y com n+1 dígitos, complementar
os dígitos de y e somar os números naturais correspondentes e o borrow de
entrada invertido, em módulo Bn+1.
Algoritmo 4.21. subtração em complemento de B
if x(n-1) < B/2 then x(n) := 0; else x(n) := B-1; end if;
if y(n-1) < B/2 then y(n) := 0; else y(n) := B-1; end if;
for i in 0..n loop y’(i) := B-1-y(i); end loop;
c_in := 1- b_in;
natural_addition (n+1, x, y’, c_in, z, not_used);
exemplo
Assumir que B = 10, n = 4, bin = 1, x = -2345, e y = 3674.
x é negativo e y positivo, tais que sejam representados por
R(x) = -2345 + 104 = 7655 e R(y) = y = 3674.
Primeiro representar x e y com 5 dígitos: R(x) = 97655 e R(y) = 03674.
Então, computar y’ = 96325, cin = 1 – bin = 0 e
(R(x) + y’ + cin ) mod 105 = (97655 + 96325) mod 105 = 93980.
O inteiro representado por 93980 é igual a 93980 – 105 = -6020, isto é,
-2345 – 3674 -1.
Detecção de overflow em
complemento de B
Em certos casos é necessário saber se o resultado é realmente um número de
n+1 dígitos e não um número de n dígitos.
Um caso típico é uma unidade aritmética de um computador de uso geral: ambos
os operandos e o resultado são números de n bits, e um flag de overflow é
acionado se o resultado não se enquadra em n bits.
Assumir que os algoritmos anteriores (adição, inversão e subtração) são
executados sem estender os operandos para n+1 bits:
1. considerar o caso da adição. Um overflow pode ocorrer quando ambos os
operandos tem o mesmo sinal. Primeiro observar que se x e y estão no
n
n
intervalo  B / 2  x, y  B / 2 então
 Bn  x  y  cin  2.(Bn / 2 1) 1  Bn 1
isto é
 Bn  x  y  cin  Bn
Ou seja, se x e y são positivos, a soma x + y + cin pode ser maior ou igual a
Bn/2. Se R(x) = x e R(y) = y, então, R(z) = (x + y+ cin) mod Bn, e de acordo
com a hipótese anterior
isto é
Bn / 2  x  y  cin  Bn
( B / 2).Bn1  x  y  cin  Bn
tal que
z(n)  0 e z(n  1)  B / 2
A conclusão é que a soma de dois números positivos, mais um carry inicial,
gera um número aparentemente negativo se somente n dígitos são
disponíveis
z (n  1)  B / 2
Se x e y são negativos, a soma x +y + cin pode ser menor que –Bn/2. Se R(x) =
Bn + x e R(y) = Bn + y, então R(z) = (2.Bn + x + y + cin) mod Bn, e de acordo
com a hipótese anterior
2.Bn  Bn  2.Bn  x  y  cin  2.Bn  Bn / 2.
isto é,
Bn  2.Bn  x  y  cin  Bn  (B / 2).Bn1
tal que
z(n)  1, z(n  1)  B / 2
A conclusão é que a soma de dois números negativos, mais um carry inicial,
gera um número aparentemente positivo se somente n dígitos são
disponíveis
z (n  1)  B / 2
•
Resumindo, a detecção de overflow é obtida observando o dígito de sinal
dos operandos e do resultado. Sob forma booleana:
add _ ovf  [(x(n  1)  B / 2)and( y(n  1)  B / 2)and( z (n  1)  B / 2)]
or[(x(n  1)  B / 2)and( y(n  1)  B / 2)
and( z (n  1)  B / 2)]
2. Já foi observado que quando se nega um número (mudança de sinal) a
única situação de overflow é quando x = -Bn/2, a saber x(n-1)=B-1 e x(n2)=...=x(0)=0.
O algoritmo de negação com n dígitos gera z = x. Novamente, basta observar
os dígitos de sinal de ambos os operandos e o resultado:
inv _ ovf  ( x(n  1)  B / 2)and( z(n  1)  B / 2)
3. Se uma subtração é realizada, um overflow pode ocorrer se um operando é
negativo e outro é positivo.
Nesse caso, a conclusão é que a diferença entre um número negativo e um
positivo, menos um borrow inicial, gera um número aparentemente positivo
se somente n dígitos são usados.
Como nos casos anteriores a detecção de overflow é obtida observando os
dígitos de sinal dos operandos e do resultado.
sub _ ovf  [(x(n  1)  B / 2)and( y(n  1)  B / 2)and( z (n  1)  B / 2 _]
or[ x(n  1)  B / 2)and( y(n  1)  B / 2)
and( z (n  1)  B / 2)]
Exemplos
1. Assumir que cin = 0, x = 2345 e y = 4674, e que o valor de x + y + cin
é computado. Então, R(x) = x = 2345 e R(y) = y = 4674. tais que
(R(x) + R(y) + cin ) mod 10000 = 7019, isto é, representação do
número negativo -2981.
2. Assumir que cin = 0, x = -4726 e y = -2174, e que o valor x +y + cin é
computado. Então, R(x) = 10000 – 4726 = 5274 e R(y) = 10000 –
2174 = 7826, tais que (R(x) + R(y) + cin) mod 10000 = 3100, isto é,
representação de um número positivo.
3. Computar a diferença entre x = 2345 e y = -4726 com bin = 0. As
representações correspondentes são R(x)= 2345 e R(y) = 10000 –
4726 = 5274, tais que y’= 4725 e (2345 + 4725 +1) mod 10000 =
7071, isto é, representação do número negativo -2929.
Sobre representação em
complemento de B reduzido
A extensão de sinal implica em duplicar o dígito de sinal.
Se B =2 não existe diferença em relação à representação não-reduzida.
Se x e y são números de n dígitos em complemento de B reduzido, então
 Bn1  x, y  Bn1
tal que
 2.Bn1  x  y  cin  2.Bn1e
Se B>2 e B é par, tal que
B  4 então
 2.Bn1  x  y  cin  2.Bn1
2.B n1  B n / 2
e
 Bn / 2  x  y  cin  Bn / 2 e  Bn / 2  x  y  bin  Bn / 2
Assim ambos x + y + cin e x – y- bin são números em complemento de B de n
dígitos. Existe overflow se o resultado não for um número na representação
de complemento de B reduzido, isto é, o dígito de sinal não pertence a {0,
B-1}. No caso de overflow negativo, o dígito negativo é igual a B-2 e 1 no
caso de overflow positivo.
Exemplos
Exemplo (B = 10, n =3, forma em complemento de 10 reduzido)
1. Assumir que cin = 0, x = 74, e y = 41, e que o valor de x+y é computado.
Então R(x) = x = 074 e R(y) = y = 041, tais que (R(x)+R(y)+cin) mod 1000 =
115, um número cujo dígito de sinal não pertence a {0,9}.
2. Assumir que cin = 0, x = -74, e y = -41, e que o valor x + y é computado.
Então, R(x) = 1000 -74 = 926 e R(y)= 1000 – 41 = 959, tais que (R(x) + R(y)
+ cin) mod 1000 = 885, um número cujo sinal não pertence a {0,9}. A
representação real é a forma não-reduzida de 885 -1000 = -115.
3.Computar a diferença entre x = 74 e y = -41, com bin = 0. As representações
são R(x) = x = 074 e R(y) = 1000 – 41 = 959, tal que y’ = 040 e
(074+040+1) mod 1000 = 115, um número cujo sinal não pertence a {0,9},
representando na realidade o número 115 na forma não-reduzida.
Excesso de E
Propriedades:
Dados dois inteiros x e y em excesso de E, um carry cin binário e um borrow bin,
então
R( x  y  c )  R( x)  R( y )  c  E ,
in
in
R( x  y  bin )  R( x)  R( y )  bin  E ,
R( x)   R( x)  2.E
Se x e y são dois números inteiros de n dígitos em excesso de E, e se z = x + y
+ cin é também um inteiro de n dígitos excesso de E, então o algoritmo direto
consiste em representar x e y com n+1 dígitos, somá-los com cin e subtrair E.
O resultado R(z) é um número natural de n+1 dígitos cujo primeiro dígito é 0.
Assumir que o procedimento natural_subtraction seja definido:
procedure natural_subtraction (s: in natural; borrow: in bit; x, y: in
digit_vector(0..s-1); next_borrow: out bit; z: out digit_vector(0..s-1));
Os seguintes algoritmos computam z = z + y + cin e z = x – y - bin.
Algoritmo 4.22 Adição excesso de E
x(n) := 0; y(n) := 0;
natural_addition (n+1, x, y, c_in, w, not_used);
natural_subtraction (n+1, w, E, 0, z, not_used);
if z(n) > 0 then overflow:= true; end if;
Algoritmo 4.23 subtração excesso de E
x(n) := 0; y(n) := 0;
natural_addition (n+1, x, E, 0, w, not_used);
natural_subtraction (n+1, w, y, b_in, z, not_used);
if z(n) > 0 then overflow:= true; end if;
Algoritmo mudança de sinal em
excesso de E (negação)
Algoritmo 4.24 Mudança de sinal em excesso de E
x(n) := 0;
E_by_2(0):= 0;
for i in 1..n loop E_by_2(i) := E(i-1); end loop;
natural_subtraction (n+1, E_by_2, x, 0, z, not_used);
if z(n) > 0 then overflow:= true; end if;
Exemplos
B = 0, n = 4, excesso de 5000
1.
assumir que cin = 0, x = 2345 e y = 1674, e que o valor de x + y + cin é
computado. Então, R(x) = 07345 e R(y) = 06674, tais que R(x) + R(y) +
cin – 05000 = 09019, isto é, representação de 4019.
2. assumir que cin = 0, x = -2345 e y = 1674, e que o valor de x + y + cin é
computado. Então, R(x) = 02655 e R(y) = 06674, tais que R(x) + R(y) +
cin – 05000 = 4329, isto é, representação de -671.
3. computar a soma de x = 2345 e y = 4726, com cin = 0. As representações
correspondentes são R(x) = 07345 e R(y) = 09726, tais que R(x) + R(y) +
cin – 05000 = 12071, resultando em overflow.
4. computar a diferença entre x = 2345 e y = 4726, com bin = 0. As
representações correspondentes são R(x) = 07345 e R(y) = 09726, tais
que R(x) - R(y) - bin + 05000 = 2619, representando -2381.
Exemplos (cont.)
5. computar a diferença entre x = -2345 e y = 4726, com bin = 0. As
representações correspondentes são R(x) = 02655 e R(y) = 09726,
tais que R(x) - R(y) - bin + 05000 = 97929 (módulo Bn+1 = 100000),
resultando em overflow.
6. computar o negativo de x = -5000. A correspondente representação
é igual a R(x) = 00000 tal que –R(x) + 2. 05000 = 10000, que resulta
em overflow.
Adição e subtração em sinal e
magnitude
Dados dois números inteiros x e y, então z = x + y + cin é um inteiro em
sinal e magnitude de n+1 dígitos. O seguinte algoritmo computa z:
Algoritmo 4.25
If sign (x) = sign(y) then a:= abs (x) + abs (y); else a:= abs(x) – abs(y);
end if;
if a < 0 then sign (z) := sign(y); abs(z) := -a ; else sign (z) := sign(x);
abs(z) := a; end if;
Algoritmo alternativo sinal e
magnitude
Algoritmo 4.26 adição em sinal e magnitude
abs_x := x (0..n-2) & 0; abs_y := y (0..n-2) & 0;
if x(n-1) = y (n-1) then
natural_addition (n, abs_x, abs_y, 0, a, not_used);
else
for i in 0..n-1 loop abs_y’ (i):= B-1-abs_y(i); end loop;
natural_addition (n, abs_x, abs_y’, 1, a, not_used);
end if;
if a(n-1) = B-1 then
z(n) := y(n-1) ;
for i in 0..n-1 loop a’(i) := B-1-a(i); end loop;
natural_addition (n, 0, a’, 1, z(0..n-1), not_used);
else
z(n) := x (n-1); z( 0..n-1):= a;
end if;
Exemplo
• (B=10, n=5). Assumir que x = + 2345 e y = - 7674. Primeiro
expressar os valores absolutos com cinco dígitos: abs(x) = 02345 e
abs(y) = 07674. Como os sinais são diferentes , computar 02345 +
92325 + 1 = 94671. O primeiro dígito é igual a 9, indicando um valor
negativo. O sinal do resultado é o mesmo do sinal de y e o valor
absoluto é 05328 +1 = 05329, tal que o resultado seja -5329.