Aritmética de ponto flutuante

Mar 14

Posted by

Opa pessoal! Depois das apresentações, um post com alguma coisa útil… ou não :P. Vou falar sobre algo em que trabalhei há um tempinho atrás na universidade e que acho muito interessante: o sistema de ponto flutuante. Para alguns esse assunto pode ser bastante massante, mas um conhecimento básico sobre ponto flutuante é de extrema importância para qualquer pessoa que trabalhe de forma séria com informática porque problemas derivados do seu uso eventualmente se tornam grandes armadilhas. Enfim… deixa eu parar com a enrolação :).

Os números de ponto flutuante (\mathbb{F}) são uma tentativa de representar os números reais (\mathbb{R}) nos computadores. Entretanto, dada a finitude inerente aos dispositivos computacionais, há perda de informação — e, portanto, \mathbb{F} é subconjunto próprio de \mathbb{R} — de modo que uma das maiores preocupações matemáticas ao se trabalhar com o sistema de ponto flutuante é a falta de fecho aritmético. Isso corresponde a dizer que, para \star \in \{+, -, \cdot, /\}, nem sempre é verdade que x \star y \in \mathbb{F}. De fato, isso é um problema. Afinal de contas, se o resultado de uma operação não é representável no conjunto de trabalho, a aritmética perde em robustez tornando-se inconsistente e, para todos os fins práticos, inútil.

Uma solução é redefinir os operadores sobre \mathbb{F} de tal forma a criar o fecho. A idéia é aplicar uma função (arredondamento) aos resultados para fazê-los “caber” no conjunto. Formalmente, seja \bigcirc:\mathbb{R} \rightarrow \mathbb{F}. Dizemos que \bigcirc é um arredondamento se obedece às seguintes propriedades:

  1. \forall \; x \in \mathbb{F} \Rightarrow \bigcirc(x) = x
  2. \forall \; x, y \in \mathbb{R} \text{ e } x \le y \Rightarrow \bigcirc(x) \le \bigcirc(y)

Ao contrário do que esse formalismo sugere, o significado de tais propriedades é bastante simples. A primeira delas estabelece que todos os elementos do conjunto dos números de ponto flutuante são fixados pela função de arredondamento. Ou seja, o arredondamento de um número de ponto flutuante é o próprio número. A segunda garante a preservação da relação de ordem (monoticidade), o que era de se esperar. Em conjunto, essas propriedades implicam no resultado mais importante a respeito da natureza do arredondamento: a característica de máxima qualidade. O que se quer dizer com isso é que \nexists \; y \in \mathbb{F} \; | \; y \in (\min\{\bigcirc(x), x\}, \max\{\bigcirc(x), x\}), ou seja, entre um número real e o seu ponto flutuante correspondente não existem intermediários pertencentes a \mathbb{F}.

Tudo bem, mas qual é a utilidade disso no estabelecimento de uma aritmética de ponto flutuante útil e robusta? Dado \star \in \{+, -, \cdot, /\}, seja \bullet \in \{\oplus, \ominus, \odot, \oslash\} o operador correspondente em \mathbb{F}. Nós definimos uma aritmética de ponto flutuante como:

\forall \; x, y \in \mathbb{F} \Rightarrow x \bullet y = \bigcirc(x \star y)

Nesse ponto aparece uma questão de ordem prática bastante relevante. Ora, se eu preciso aplicar a função \bigcirc ao resultado da operação \star, então de alguma forma eu precisarei representar este resultado na máquina. Mas, não é precisamente esse problema que estamos tentando resolver?! A circularidade é apenas aparente, entretanto. Com efeito, é possível mostrar que, se x e y estão armazenados em registradores com p dígitos de precisão, o valor exato da operação x \star y pode ser armazenado em um intermediário com p + 3 dígitos – para detalhes a respeito da técnica e do porquê de seu funcionamento, recomendo [1]. Procede-se então o arredondamento adaptando o resultado ao registrador ordinário de p dígitos.

Agora que nós definimos uma aritmética de ponto flutuante abstrata, é necessário concretizá-la. No contexto, isto significa que nós precisamos definir o comportamento da função \bigcirc, o que pode ser feito de 4 formas diferentes como descrito abaixo.

Round to zero

Este é o método de arredondamento mais simples que existe. Formalmente, a função round to zero \square_z : \mathbb{R} \rightarrow \mathbb{F} é definida como

\square_z(x) = sign(x) \; max \; \lbrace{y \in \mathbb{F} : y \le |x|\rbrace}

onde sign(x) é o que o próprio nome diz. Este arredondamento é o mais facilmente implementável. De fato, se \mathbb{F} tem precisão p, é suficiente descartar os dígitos além da posição p-1. Por causa disso, este método também é conhecido como truncagem.

Round toward minus infinity

Este é um dos modos de arredondamento pertencentes à classe dos direcionados. Um arredondamento direcionado deve resultar no ponto flutuante imediatamente anterior (ou posterior) ao número real correspondente. Formalmente, ele deve satisfazer uma das seguintes propriedades:

  1. x \in \mathbb{R} \Rightarrow \bigcirc(x) \le x
  2. x \in \mathbb{R} \Rightarrow \bigcirc(x) \ge x

Particularmente, o round toward minus infinity obedece a primeira propriedade e é definido por:

\bigtriangledown(x) = max \; \lbrace{y \in \mathbb{F} : y \le x\rbrace}

Note as semelhanças entre este modo e o round to zero. Apesar de parecerem idênticos, existe uma diferença sutil. Por exemplo, se nós tivermos um sistema de ponto flutuante com 2 dígitos de precisão e tentarmos arredondar -1.234 usando o round to zero, nós obteremos -1.23. Por outro lado, se usarmos o round to minus infinity, o resultado será -1.24. De forma geral, é verdade que \square_z(x) = sign(x) \; \bigtriangledown(|x|).

Round toward plus infinity

O round toward plus infinity é o análogo simétrico do round toward minus infinity. Portanto, este arredondamento satisfaz a segunda das duas propriedades citadas acima e é definido como:

\bigtriangleup(x) = min \; \lbrace{y \in \mathbb{F} : y \ge x\rbrace}

Note uma propriedade interessante dos arredondamentos direcionados: do que foi dito, nós podemos concluir que o intervalo [\bigtriangledown(x), \bigtriangleup(x)] é o menor cujos extremos são números em \mathbb{F} e contém x. Então, o diâmetro deste intervalo é o erro máximo cometido pela função arredondamento. Esta propriedade é usada na Aritmética Intervalar de Precisão Máxima.

Round to nearest

Uma metodologia mais inteligente de arredondamento é considerar o ponto médio \mu = \frac{1}{2}(\bigtriangledown(x)+\bigtriangleup(x)) do intervalo [\bigtriangledown(x), \bigtriangleup(x)]. Desta forma, se x < \mu, retorne \bigtriangledown(x), caso contrário, se x > \mu, então retorne \bigtriangleup(x). Se x = \mu, nós temos que decidir o que fazer. Esta decisão cria diferentes variantes do arredondamento. O round to nearest implementa exatamente esse método. Em geral, o erro cometido por este modo é menor que o dos outros.

Bem, por agora é isso :). Desculpe se tudo isso foi maçante. De fato, esta é uma abordagem muito teórica para um problema muito prático, mas eu gosto de alguma teoria antes das questões práticas. Isso ajuda a dar fundamentação a possíveis soluções. Em algum ponto no futuro irei escrever sobre o erro de arredondamento considerando o padrão de ponto flutuante IEEE 754 de um ponto de vista prático. Então, até a próxima… :)

Posted in Floating-Point Numbers, Scientific Computing

Leave a comment

Tags: ,

Introducing myself…

Mar 9

Posted by

Hi people!

My name is Rafael Barreto and I am an undergraduate in Computer Engineering at Federal University of Pernambuco (UFPE) in Brazil. I always wanted to have a blog to share stuff I find interesting, but I guess I do not have the discipline for it :P. Well, this is a try… let’s see if I can stand with it.

My main focus here is technical stuff, especially related to computing and math. However, I like literature and music a lot. So, it’s possible these themes appear here eventually.

I will try to keep it in english (despite I cannot guarantee this). Mainly because it makes the blog much more accessible and because I really need to practice my writing :P.

That’s it… enough of presentation… =P

Posted in Uncategorized

Leave a comment

Tags:

Newer Posts →