Aritmética de precisão arbitrária – o algoritmo CLA

As unidades aritméticas de processamento imbuídas nos processadores dos computadores realizam operações sobre um intervalo limitado de valores. Nas arquitecturas de 64-bit, por exemplo, é possível realizar operações aritméticas sobre números que variam entre -9223372036854775808 e 9223372036854775807. Apesar de constituírem valores elevados, existem problemas que requerem a aplicação de operações aritméticas sobre valores que se encontram fora desse intervalo. Por estes motivos, são implementadas livrarias com funções capazes de lidar número de precisão arbitrária (ver por exemplo GMP ou BigInteger). Em ambos os casos, os números de precisão arbitrária são armazenados em vectores de bytes, os quais suportam valores entre -128 e 127. Se considerarmos o byte como um número sem sinal, os seus valores podem variar desde 0 até 255.

Pretendo apresentar uma pequena discussão sobre o processo de adição de dois números de precisão arbitrária, considerando a representação dos números como vectores de bytes. Enfatizo o algoritmo CLA (Carry lookahed) por me parecer um algoritmo facilmente paralelizável.

Comecemos por considerar uma base arbitrária b>1. Qualquer número pode ser representado na forma

x=\alpha_nb^n+\alpha_{n-1}b^{n-1}+\cdots+\alpha_1b+\alpha_0

onde 0\le\alpha_i\le b-1 são aquilo que poderemos designar por dígitos. Caso pretendamos representar um número de precisão arbitrária por um vector de bytes, cada entrada i do vector pode consistir num dígito \alpha_i que toma valores no intervalo compreendido entre 0 e 255. Por exemplo, o número 9526, decomposto em

9526=37\times 256+54

admite a representação vectorial

\begin{tabular}{|c|c|}\hline 54 & 37\\ \hline\end{tabular}

Sejam x e y dois números cujas representações na base b são da forma

\begin{matrix}x=\alpha_nb^n+\alpha_{n-1}b^{n-1}+\cdots+\alpha_1b+\alpha_0\\y=\beta_mb^m+\beta_{m-1}b^{m-1}+\cdots+\beta_1b+\beta_0\end{matrix}

onde podemos supor, sem perda de generalidade, que m\le n. A propriedade distributiva permite-nos escrever

x+y=\alpha_nb^n+\alpha_{n-1}b^{n-1}+\cdots+\alpha_{m+1}b^{m+1}+\left(\alpha_m+\beta_m\right)b^m+\left(\alpha_{m-1}+\beta_{m-1}\right)b^{m-1}+\cdots+\left(\alpha_1+\beta_1\right)b+\left(\alpha_0+\beta_0\right)

Vejamos entre que valores variam as expressões \alpha_i+\beta_i. Sabemos que valem as desigualdades 0\le\alpha_i\le b-1 e 0\le\beta_i\le b-1. Segue-se daqui que

0\le\alpha_i+\beta_i\le 2b-2=1\times b+(b-2)

Assim,

\alpha_i+\beta_i=\delta b+\gamma_i

onde \delta\in\lbrace 0,1\rbrace e 0\le\gamma_i\le b-2. Vemos que, para determinar a representação da soma de dois números dadas as suas representações individuais, é suficiente aplicar o algoritmo da soma habitual. Este processa-se do seguinte modo.

Começamos por calcular a soma dos dígitos de ordem mais baixa, nomeadamente,

\alpha_0+\beta_0=\delta_0 b+\gamma_0

De seguida, para todos os valores de i desde 0 até m, calculamos

\alpha_i+\beta_i=\delta_i b+\gamma_i'

e fazemos

\gamma_i=\gamma_i'+\delta_{i-1}

Para o dígitos com ordens i superiores a m, fazemos sucessivamente

\alpha_i+\delta_{i-1}=\delta_i+\gamma_i

enquanto i\le n e \delta_i\ne0. Se, no final, tivermos \delta_n=1, acrescentamos o dígito 1 com ordem n+1. Este procedimento permite-nos escrever a representação da soma x+y na forma

x+y=\delta_n b^{n+1}+\gamma_n b^n+\cdots+\gamma_1 b+\gamma_0

O algoritmo da soma apresentado não pode ser realizado em paralelo uma vez que o cálculo de cada dígito \gamma_i depende do valor de \delta_{i-1} que resulta da soma dos dígitos de ordem inferior.

No algoritmo CLA, associamos a cada dígito adicionado duas variáveis lógicas. A primeira, indica se o resultado da soma de dois dígitos \alpha_i+\beta_i irá resultar num valor de \delta_i=1, isto é, irá resultar num transporte, independentemente de receber ou não um transporte das somas dos dígitos anteriores. A segunda, indica se a soma dos dígitos irá propagar um valor de transporte unitário para o dígito seguinte caso receba um transporte do dígito anterior. Ora, a soma \alpha_i+\beta_i incorre num transporte sempre que \alpha_i+\beta_i\ge b. Por seu turno, a mesma soma incorre numa propagação se \alpha_i+\beta_i=b-1. É claro que se uma soma gerar um transporte então não pode propagar uma vez que

\alpha_i+\beta_i\le 1\times b + b-2

Se designarmos por G_i a variável que indica se a soma dos dígitos de ordem i geram, por P_i a variável que indica se a soma dos dígitos da mesma ordem propagam e por C_i o transporte que o dígito de ordem i recebe do dígito anterior, podemos escrever

C_i=G_{i-1}\lor \left(G_{i-2}\land P_{i-1}\right)\lor\left(G_{i-3}\land P_{i-2}\land P_{i-1}\right)\lor\cdots

Não é difícil constatar que P_i assume o valor lógico verdadeiro se se verificar a expressão

\alpha_i\oplus\beta_i=b-1

onde o sinal \oplus representa a operação lógica ou exclusivo sobre os bits que definem os respectivos dígitos. Alternativamente, dá-se propagação caso a soma dos dígitos módulo b seja igual a b-1. Por outro lado, como \alpha_i<b então, se

\alpha_i+\beta_i=b+\gamma_i

então

b+\gamma_i-\beta_i<b

ou

\gamma_i<\beta_i

Do mesmo modo mostramos que \gamma_i<\alpha_i. Segue-se da propriedade da soma que G_i assume o valor lógico verdadeiro apenas quando

\alpha_i+\beta_i\ \text{mod}\ b<\alpha_i

Estas ideias permitem desenvolver um algoritmo para calcular o valor do dígito de ordem i dado por \gamma_i da soma x+y. Para o efeito, começamos por fazer

\gamma_i=\alpha_i+\beta_i \text{mod}\ b

Avaliamos G_{i-1}. Se o seu valor lógico for verdadeiro então aumentamos \gamma_i em uma unidade (módulo b). Caso contrário, avaliamos o valor lógico de P_{i-1}. Se este valor for falso, paramos o processo e \gamma_i já contém o valor correcto para o dígito de ordem i da soma x+y. Se o valor for verdadeiro, avaliamos G_{i-2}. Se este valor for verdadeiro, incrementamos \gamma_i. Caso contrário, avaliamos P_{i-2} que, sendo falso, termina o processo. Se P_{i-2} for verdadeiro, o processo repete-se.

Como exemplo, consideremos duas representações,

\begin{tabular}{|c|c|c|c|}\hline 240 & 123 & 230 & 45\\ \hline\end{tabular}

e

\begin{tabular}{|c|c|c|c|}\hline 27 & 132 & 64 & 9\\ \hline\end{tabular}

Pretendemos determinar o dígito de ordem 2 da sua soma. Começamos por avaliar a primeira aproximação para \gamma_2. Temos

\gamma_2\equiv 38\ \text{mod}\ 256

Avaliamos a soma dos dígitos de ordem 1 em 132+123=255 para concluirmos que o dígito de ordem 1 não gera mas propaga. Neste caso, temos de avaliar a soma dos dígitos anteriores módulo 256. Ora, 240+27\equiv 11 módulo 256 e 11 < 240. Como o dígito de ordem 1 gera então teremos de incrementar \gamma_2, ficando \gamma_2=39.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática com as etiquetas , , , , . ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s