Ponto_Flutuante

Prévia do material em texto

AULA 0 Representac¸a˜o em ponto flutuante
Quando pedimos ao computador para armazenar um nu´mero, o valor de fato armazenado sera´ provavel-
mente uma aproximac¸a˜o para o valor original. Isso acontece porque o computador utiliza, na representac¸a˜o
de qualquer nu´mero, apenas um nu´mero finito de dı´gitos, de modo que apenas um subconjunto finito dos
nu´meros reais e´ representa´vel de forma exata.
Representac¸a˜o cientı´fica normalizada
Para introduzir o modo da representac¸a˜o nume´rica em computadores, comecemos com a representac¸a˜o ci-
entı´fica normalizada ou RCN. Nesta representac¸a˜o, podemos representar qualquer nu´mero real (de forma
padronizada) movendo a vı´rgula para a esquerda (ou direita) ate´ obtermos uma forma composta de uma
parte fraciona´ria (menor que 1 em mo´dulo; com primeiro dı´gito na˜o-nulo) vezes um certa poteˆncia de 10. Veja
figura (a).
732, 5051 0, 7 3 2 5 0 5 1
�0, 005612
�
� 5 6 1 2
Representac¸a˜o cientı´fica normalizada
0,�
103
10�2
�
�
primeiro dı´gito e´ zero
primeiro dı´gito
apo´s o zero e´ na˜o-nulo
(normalizado)
poteˆncias de 10
Figura (a): Dois exemplos de RCN.
Representac¸a˜o nume´rica em ponto flutuante
Da RCN para a representac¸a˜o nume´rica computacional real e´ simples. De fato, a representac¸a˜o que vamos
usar, chamada de ponto flutuante, e´ uma RCN onde a quantidade de dı´gitos na parte fraciona´ria e´ pre´-fixada. Ale´m
disso, as poteˆncias possı´veis da base nume´rica utilizada tambe´m devem estar num intervalo pre´-fixado.
De maneira geral, dado um nu´mero real x, sua representac¸a˜o em ponto fluturante, denotada por flpxq, e´
dada por
flpxq ≔ �0, d1d2 � � � dn � βe, (1)
1
2 AULA 0. REPRESENTAC¸A˜O EM PONTO FLUTUANTE
onde
(a) β e´ a base;
(b) 0, d1d2 � � � dn e´ amantissa, isto e´, a representac¸a˜o fraciona´ria de x com n dı´gitos (ou dı´gitos significativos)
na base β (vamos sempre supor que a mantissa esta´ normalizada, isto e´, ou d1 � 0 ou di � 0 para todo
i);
(c) a caracterı´stica e´ o expoente e P Z, com �m   e   M.
Os paraˆmetros pβ, n,m, Mq definem, para uma ma´quina em particular, quais sa˜o os nu´meros repre-
senta´veis nesta ma´quina. De maneira geral F � Fpβ, n,m, Mq representara´ o conjunto de nu´meros repre-
senta´veis nesta ma´quina. Como observado na introduc¸a˜o, F sera´ um conjunto finito.
Exemplo 0.1. [GL96] Numa ma´quina que opera com Fp2, 3, 0, 2q, os nu´meros na˜o-negativos representa´veis sa˜o:
0, 100� 20 0, 100� 21 0, 100� 22
0, 101� 20 0, 101� 21 0, 101� 22
0, 110� 20 0, 110� 21 0, 110� 22
0, 111� 20 0, 111� 21 0, 111� 22
os quais, convertidos para base decimal, sa˜o:
1{2 1 2
5{8 5{4 5{2
6{8 6{4 6{2
7{8 7{4 7{2
Veja figura (b). Note que os nu´meros em ponto flutuante na˜o precisam ser igualmente espac¸ados.
0 0, 5 1 2
Figura (b): Exemplo de nu´meros na˜o-negativos representa´veis (em vermelho) numa ma´quina que opera
com Fp2, 3, 0, 2q.
�
Embora possamos ter valores diferentes para a base β, por exemplo β � 2 como no exemplo acima (e
com frequeˆncia nas ma´quinas reias) neste texto vamos usar, por simplicidade, apenas β � 10.
3
Arredondamento e truncamento
Ao converter um nu´mero real para sua representac¸a˜o em ponto flutuante, as limitac¸o˜es na mantissa podem
introduzir dois tipos de erros, chamados de arrendondamento e truncamento. Essas noc¸o˜es ficam mais claras
atrave´s de um exemplo.
Exemplo 0.2. [RdRL97] Considere uma ma´quina, por exemplo, que opere no sistema Fp10, 3, 5, 5q. Os nu´meros, nesse
caso, sera˜o representados na seguinte forma:
0, d1d2d3 � 10e, 0 ¤ d j ¤ 9, d1 � 0, e P r�5, 5s.
Agora, dado qualquer x P R, muito provavelmente flpxq sera´ uma aproximac¸a˜o de x. Por exemplo, dado x ≔
235, 89 � 0, 23589 � 103, como esse nu´mero tem mais de 3 algarismos, ha´ duas possibilidades para representar esse
nu´mero nesta ma´quina:
(a) podemos simplesmente desprezar do quarto dı´gito em diante, obtendo flpxq � 0, 235� 103;
(b) ou podemos desprezar do quarto dı´gito em diante, pore´m aumentando o terceiro dı´gito caso o quarto dı´gito
desprezado seja maior ou igual a 5. Nesse caso, flpxq � 0, 236� 103.
�
De maneira geral, se x ≔ 0, d1d2 � � � dndn�1 � � � � 10e (na base 10) e´ um nu´mero em RCN que vai ser
representado em ponto flutuante numa ma´quina que opera com n dı´gitos significativos, enta˜o temos duas
possibilidades:
(a) no arredondamento, temos que
flpxq �
$
&
%
0, d1d2 � � � dn � 10e � 0, 1� 10e�n�1, se dn�1 ¥ 5,
0, d1d2 � � � dn � 10e, se dn�1   5;
(2)
(b) no truncamento, temos que flpxq � 0, d1d2 � � � dn � 10e.
Overflow e underflow
Como o conjunto F dos nu´meros representa´veis numama´quina e´ finito, existe ummenor nu´mero emmo´dulo
representa´vel e um maior nu´mero em mo´dulo representa´vel nessa ma´quina. Denotemos esses nu´meros por
m e M, respectivamente. O que acontece se tentarmos usar nesse computador um nu´mero x � 0 tal que
|x| ¡ M ? Bem, isso pode ocasionar um erro de execuc¸a˜o, o qual chamamos de overflow. De maneira
similar, se |x|   m, pode ocorrer um underflow.
Exemplo 0.3. [RdRL97] Considere uma ma´quina igual a` do exemplo 0.2, isto e´, que opere no sistema Fp10, 3, 5, 5q. E´
fa´cil constatar que o menor nu´mero (em valor absoluto) representado nesta ma´quina e´: m ≔ 0, 100 � 10�5 � 10�6,
enquanto o maior nu´mero (em valor absoluto) e´ M ≔ 0, 999� 105 � 99900. Teremos um overflow para x ≔ 0, 345 � 109 e
um underflow para x ≔ 0, 875 � 10�7. �
4 AULA 0. REPRESENTAC¸A˜O EM PONTO FLUTUANTE
Geralmente o underflow e´ convertido em zero e a execuc¸a˜o prosegue sem problemas. Por outro lado, a`s
vezes, podemos evitar a ocorreˆncia de overflow apenas com uma reorganizac¸a˜o das contas.
Exemplo 0.4. [Ste96] Considere o problema da calcular
z ≔
a
x2 � y2,
onde x ≔ 1060 e y ≔ 1. Numa ma´quina com Fp10, 4, 9, 99q, ao calculamormos x2 ocorrera´ overflow e a consequente
interrupc¸a˜o da execuc¸a˜o. Pore´m, se definirmos
s ≔ max
 
|x|, |y|
(
� 1060,
enta˜o podemos obter o valor de z da seguinte forma:
z � s
� x
s
	2
�
�y
s
	2
� 1060
d
12 �
�
1
1060
2
� 1060
a
12 � 02 � 1060,
a qual e´ uma aproximac¸a˜o razoa´vel, dado que 1 ! 1060. �
Erro absoluto e relativo
Para estabelecer o nı´vel de precisa˜o das representac¸o˜es nume´ricas em computadores emgeral, e da representac¸a˜o
em ponto flutuante em particular, e´ necessa´rio ter alguma medida de erro. Suponha que, apo´s ou durante
a aplicac¸a˜o de um me´todo nume´rico, obtemos o valor nume´rico u¯, aproximac¸a˜o do valor nume´rico exato u.
Com relac¸a˜o a` precisa˜o de tal aproximac¸a˜o, definimos:
(a) o erro absoluto, denotado eabs, por
eabs ≔ |u¯� u|;
(b) o erro relativo, denotado erel, por
erel ≔
�
�
�
�
u¯� u
u
�
�
�
�
,
para u � 0.
Quando o erro relativo for pequeno ele sera´ pro´ximo de |pu¯ � uq{u¯|, o que de certa forma justifica o uso
desta expressa˜o como a definic¸a˜o de erro relativo em algumas refereˆncias. Isso pode ser verificado cha-
mando α ≔ pu� u¯q{u e verificando que pu� u¯q{u¯ � α{p1� αq � α, se α � 0.
Como uma medida de precisa˜o, o erro absoluto pode ser enganoso e o erro relativo mais significativo,
na medida em que este u´ltimo leva em considerac¸a˜o a magnitude dos valores.
Exemplo 0.5. [BF01] Queremos aproximar p por p¯ onde
5
(a) p ≔ 0, 3000 � 101 e p¯ ≔ 0, 3100 � 101; aqui o erro absoluto e´ 0, 1;
(b) p ≔ 0, 3000 � 10�3 e p¯ ≔ 0, 3100 � 10�3; aqui o erro absoluto e´ 0, 1 � 10�4;
(c) p ≔ 0, 3000 � 104 e p¯ ≔ 0, 3100 � 104; aqui o erro absoluto e´ 0, 1 � 103.
Note que no item (b) os valores envolvidos sa˜o pequenos e, por essa razao, o erro e´ pequeno. Ja´ no item (c) os
valores envolvidos sa˜o grandes, de modo que o erro e´ grande. Contudo, o erro relativo nos treˆscasos e´ de 0, 333¯3�10�1,
o que nos da´ uma ide´ia que em todos os casos as aproximac¸o˜es sa˜o equivalentes. �
No entanto, em problemas reais, apenas o valor aproximado u¯ e´ conhecido, de modo que e´ impossı´vel
obter o valor exato do erro, seja ele absoluto ou relativo.
Estimativa do erro no truncamento (e no arredondamento)
Estimativas podem ser feitas para o erro relativo quando usamos truncamento ou arrendondamento. Vejamos o
primeiro caso. Vamos supor umama´quina operando com Fp10, nq. Nesse caso, dado x ≔ 0, d1d2 � � � dndn�1 � � ��
10e (em RCN), enta˜o:
flpxq � 0, d1d2 � � � dn � 10e.
Assim, temos:
�
�
�
�
x� flpxq
x
�
�
�
�
�
�
�
�
�
0, d1d2 � � � dndn�1 � � � � 10e � 0, d1d2 � � � dn � 10e
0, d1d2 � � � � 10e
�
�
�
�
�
�
�
�
�
0, dn�1dn�2 � � � � 10e�n
0, d1d2 � � � � 10e
�
�
�
�
�
�
�
�
�
0, dn�1dn�2 � � �
0, d1d2 � � �
�
�
�
�
� 10�n.
Como d1 � 0, o valor mı´nimo do denominador e´ 0, 1. Logo,
�
�
�
�
x� flpxq
x
�
�
�
�
¤
1
0, 1 � 10
�n
� 10�n�1.
Do mesmo modo, um limite para o erro relativo quando se utiliza o me´todo de arrendondamento para
n dı´gitos e´ 0, 5 � 10�n�1 (veja o exercı´cio 0.5).
AULA 1 Aritme´tica de ponto flutuante
Ale´m de saber como o computador armazena os valores numericos, e´ importante saber como ele realiza as
contas com esses nu´meros. Seguindo o modelo em [BF01], vamos apresentar uma descric¸a˜o aproximada da
aritme´tica computacional, embora suficiente para exemplificar os problemas que podem aparecer.
De maneira geral, dados dois nu´meros reais x, y, denotamos por
x` y ≔ fl
�
flpxq � flpyq
	
, xa y ≔ fl
�
flpxq � flpyq
	
,
xb y ≔ fl
�
flpxq � flpyq
	
, x
 y ≔ fl
�
flpxq � flpyq
	
(1.1)
a aritme´tica computacional que vamos usar. As operac¸o˜es correspondem, respectivamente a`s operac¸o˜es
exatas �,�,�,�. Observe que, de acordo com (1.1), para realizar operac¸o˜es nesse aritme´tica, precisamos:
(a) realizar a aritme´tica exata nas representac¸o˜es em ponto flutuante de x e y, e enta˜o,
(b) converter o resultado do item anterior para sua representac¸a˜o em ponto flutuante.
O segundo item se faz necessa´rio pois na˜o e´ verdade que todo resultado de uma operac¸a˜o entre nu´meros
em ponto flutuante va´ ser tambe´m um nu´mero em ponto flutuante.
Exemplos de aritme´tica computacional
Para que as contas possam ser efetuadas em aritme´tica de ponto flutuante, ale´m de saber o sistema F que a
ma´quina opera, e´ necessa´rio estipular se a ma´quina usa arredondamento ou trucamento.
Exemplo 1.1. [RdRL97] Suponha uma ma´quina que opera com Fp10, 4q com arredondamento. Dados x ≔ 0, 937� 104 e
y ≔ 0, 1272� 102, temos
x ` y � fl
�
0, 937� 104 � 0, 1272� 102
	
� fl
�
0, 937� 104 � 0, 001272� 104
	
� fl
�
0, 938272� 104
	
� 0, 9383� 104,
x b y � fl
�
�
0, 937� 104
�
�
�
0, 1272� 102
�
	
� fl
�
0, 937� 0, 1272� 106
	
� fl
�
0, 1191864� 106
	
� 0, 1192� 106.
�
Exemplo 1.2. [BF01] Suponha uma ma´quina que opera com Fp10, 5q com truncamento. A tabela abaixo lista todas as
operac¸o˜es computacionais para x ≔ 5{7 e y ≔ 1{3. Note que flpxq � 0, 71428� 100 e flpyq � 0, 33333� 100.
11
12 AULA 1. ARITME´TICA DE PONTO FLUTUANTE
operac¸a˜o resultado valor real erro absoluto erro relativo
x ` y 0, 10476� 101 22{21 0, 190� 10�4 0, 182� 10�4
x a y 0, 38095� 100 8{21 0, 238� 10�5 0, 625� 10�5
x b y 0, 23809� 100 5{21 0, 524� 10�5 0, 220� 10�4
x 
 y 0, 21428� 101 15{7 0, 571� 10�4 0, 267� 10�4
Como o maior erro relativo foi da ordem de 10�4 e estamos trabalhando com 5 dı´gitos, os resultados das contas
sa˜o aproximac¸o˜es roaza´veis. No entanto, e´ possı´vel escolher nu´meros para os quais os erros ficam grandes. De fato, se
u ≔ 0, 714251, v ≔ 98765, 9 e w ≔ 0, 111111� 10�4,
enta˜o:
operac¸a˜o resultado valor real erro absoluto erro relativo
x a u 0, 30000� 10�4 0, 34714� 10�4 0, 471� 10�5 0, 136
px a uq ` w 0, 27000� 101 0, 31243� 101 0, 424 0, 136
px a uq b w 0, 29629� 101 0, 34285� 101 0, 465 0, 136
u` v 0, 98768� 105 0, 98766� 105 0, 161� 101 0, 163� 10�4
�
As leis da aritme´rica podem falhar no caso de operac¸o˜es aritme´ticas em ponto flutuante. Por exemplo,
podemos perder a associatividade.
Exemplo 1.3. [Fra07] Considere uma ma´quina que opera com Fp10, 3q e arredontamento. Note que:
$
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
&
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
%
p11, 4` 3, 18q ` 5, 05 � fl
�
fl
�
0, 114� 102 � 0, 318� 101
�
� 0, 505� 101
�
� fl
�
0, 146� 102 � 0, 505� 101
�
� 0, 197� 102 p� 19, 7q,
11, 4` p3, 18` 5, 05q � fl
�
0, 114� 102 � fl
�
0, 318� 101 � 0, 505� 101
��
� fl
�
0, 114� 102 � 0, 823� 101
�
� 0, 196� 102 p� 19, 6q,
de modo que
p11, 4` 3, 18q ` 5, 05 � 11, 4` p3, 18` 5, 05q.
�
As operac¸o˜es aritme´ticas em ponto flutuante tambe´m na˜o sa˜o, necessariamente, distribuitivas.
13
Exemplo 1.4. [Fra07] Considere novamente uma ma´quina que opera com Fp10, 3q e arredontamento. Note que:
$
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
&
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
%
3, 18b p5, 05` 11, 4q � fl
�
0, 318� 101 � fl
�
0, 505� 101 � 0, 114� 102
��
� fl
�
p0, 318� 101q � p0, 165� 102q
�
� 0, 525� 102 p� 52, 5q,
p3, 18b 5, 05q ` p3, 18b 11, 4q � fl
�
fl
�
0, 318� 101 � 0, 505� 101
�
� fl
�
0, 318� 101 � 0, 114� 102
��
� fl
�
0, 161� 102 � 0, 363� 102
�
� 0, 524� 102 p� 52, 4q.
donde
3, 18b p5, 05` 11, 4q � p3, 18b 5, 05q ` p3, 18b 11, 4q.
�
Evitando erros
Os exemplos acima sugerem que mesmo em casos simples, diferentes maneiras de fazer uma mesma conta
no computador pode alterar o resultado final. A seguir, como esse fato pode conduzir a valores com distintos
graus de precisa˜o.
Exemplo 1.5. [BF01] Considere o problema de avaliar o polinoˆmio f pxq ≔ x3 � 6, 1x2 � 3, 2x� 1, 5 no ponto x � 4, 71,
usando uma ma´quina que opera com Fp10, 3q e arredondamento. Os valores que sera˜o necessa´rios para o ca´lculo sa˜o
apresentados na tabela abaixo.
x2 x3 6, 1x2 3, 2x
Exato 22, 1841 104, 487111 135, 32301 15, 072
Fp10, 3q � arredondamento 22, 2 105 135 15, 1
Vejamos, por exemplo, como foram calculados as parcelas x2 e x3. Nesse caso, primeiro calculamos
x2 � x b x � fl
�
4, 71 � 4, 71
�
� fl
�
22, 1841
�
� 22, 2.
para depois avaliar
x3 � px b xq b x � fl
�
22, 2 � 4, 71
�
� fl
�
104.562
�
� 105.
Portanto, para calcular f pxq usando a aritme´tica computacional, fazemos
f p4, 71q �
�
�
105a 135
�
` 15, 1
	
` 1, 5 � �13, 4.
Por outro lado, fazendo a conta exata, obtemos facilmente o valor f p4, 71q � �14, 263899. Agora, sabendo o valor
exato, e´ possı´vel calcular o erro relativo:
�
�
�
�
�
f pxq � fl� f pxq�
f pxq
�
�
�
�
�
�
�
�
�
�
�14, 263899� 13, 4
�14, 263899
�
�
�
�
� 0, 06.
14 AULA 1. ARITME´TICA DE PONTO FLUTUANTE
Esse erro pode ser diminuido apenas alterando a forma de se calcular o polinoˆmio. Usando uma fatorac¸a˜o em
camadas, note que
f pxq � x3 � 6, 1x2 � 3, 2x� 1, 5 �
�
�
x � 6, 1
�
x� 3, 2
	
x� 1, 5.
Logo, fazendo as contas em camadas, temos
f p4, 71q �
�
�
4, 71a 6, 1
�
b 4, 71` 3, 2
	
b 4, 71` 1, 5 � �14, 3,
cujo erro relativo e´
�
�
�
�
�
f pxq � fl� f pxq�
f pxq
�
�
�
�
�
�
�
�
�
�
�14, 263899� 14, 3
�14, 263899
�
�
�
�
� 0, 0025.
Isso significa uma reduc¸a˜o demais de 95%. Isso sugere que, ao avaliar um polinoˆmio, devemos sempre usar a
forma fatorada em camadas. �
Cancelamento subtrativo e a perda de dı´gitos significativos
Um efeito nume´rico que ocorre com frequeˆncia e´ o chamado cancelamento subtrativo. E´ o que acontece
quando tentamos subtrair dois nu´meros muito pro´ximos.
Exemplo 1.6. [Dat10] Considere a subtrac¸a˜o x � y, onde:
x ≔ 0, 54617 e y ≔ 0, 54601.
O valor correto e´ x � y � 0, 00016. No entanto, numa ma´quina que opera com Fp10, 4q e arredondamento, temos
xa y � fl
�
0, 5462� 100 � 0, 5460� 100
�
� 0, 0002,
cujo erro relativo e´
�
�
�
�
px � yq � px a yq
x � y
�
�
�
�
� 0, 25 (muito grande).
�
Emmuitos casos, e´ possı´vel evitar o cancelamento subtrativo apenas com uma reorganizac¸a˜o das contas.
Exemplo 1.7. [Dat10] Considere o problema de encontrar as raı´zes da equac¸a˜o
x2 � 105x� 1 � 0.
De acordo com a fo´rmula de Bhaskara, as raı´zes x1, x2 sa˜o dadas por:
x1 ≔
105 �
?
1010 � 4
2
e x2 ≔
105 �
?
1010 � 4
2
.
Agora, numa ma´quina que opera com Fp10, 8q com arredondamento, os valores acima se tornam:
x1 � 105 (boa aproximac¸a˜o) e x2 � 0 (errado).
15
O valor de x2 esta´ errado pois houve cancelamento subtrativo, ja´ que 105 �
?
1010 � 4. De fato, o valor exato e´
x2 � 0, 000010000000001 (corretamente arredondado com 11 dı´gitos significativos).
Por outro lado, usando as fo´rmulas alternativas
x1 � �
b� sinalpbq
?
b2 � 4ac
2a
e x2 �
c
ax1
,
obtemos
x1 � 100000, 00 e x2 � 0, 00001000,
as quais sa˜o uma boa aproximac¸a˜o. �