Representação e Aritmética em Ponto Flutuante

Prévia do material em texto

Representação e 
Aritmética em Ponto 
Flutuante
35T12 – Sala 3G4
Bruno Motta de Carvalho
DIMAp – Sala 15 – Ramal 227
DIM04042
Sistemas de Representação 
de Números no Computador
 Representação de números inteiros
 Dado um número inteiro n≠0, ele possui uma 
única representação na base 
    onde os                     são inteiros satisfazendo 
 Por exemplo, 712 é representado por
n=∓n
−k n−k1n−1 n0=∓n0 
0 n1 
1
n
−k 
k

ni , i=0,−1,−k
0ni  e  n−k≠0
712=2×1001×1017×102=71210  ou 
712=1×290×281×271×260×250×24
1×230×220×210×20=10110010002
DIM04043
Representação de Números 
Reais
 Representação em ponto fixo: 
representação usada por muitos 
computadores nas décadas de 60 e 70
 Dado um número real x≠0, ele pode ser 
representado por
 Exemplo: 1997.16 na base  =10
x=∓∑
i=k
n
xi 
−i ,  onde  kn  e  0x i
1997.16=∓∑
i=−3
2
xi 
−i
             =1×1039×1029×1017×1001×10−16×10−2
DIM04044
Representação em Ponto 
Flutuante
 Mais flexível que a representação em ponto fixo
 Padrão nos dispositivos atuais (IEEE 754)
 Dado um número real x≠0, ele pode ser 
representado por                 onde   é a base do 
sistema de numeração, d é a mantissa e e é o 
expoente e d é um número em ponto fixo 
 onde geralmente k=1, e se x≠0, então d1≠0; 
0≤ di <  , i=1,2,...,t, sendo t a quantidade de 
dígitos significativos ou precisão do sistema, e 
 ≤ d < 1 e ­m ≤ e ≤ M
x=∓d×e ,
d=∓∑
i=k
n
d i 
−i ,
DIM04045
Representação em Ponto 
Flutuante
 D1≠0 caracteriza o sistema de números em 
ponto flutuante como normalizado
 O número 0 pertence a qualquer sistema e 
pode ser representado com mantissa igual 
a 0 e e= ­m
 Exemplos: 0.35, ­5.172, 0.0123, 5391.3, 
0.0003
DIM04046
Representação em Ponto 
Flutuante
 Sistema de representação de números em 
ponto flutuante normalizados
   com                       onde 
 Exemplos: 0.35, ­5.172, 0.0123, 5391.3, 
0.0003
 Represente os números acima usando o 
sistema 
F  , t , m , M  ,
±0.d1 d2d t×
e , d1≠0  e −meM
F 10,3 ,2 ,2
DIM04047
Mudança de Base
 Máquinas ou humanos podem usar bases diferentes 
para representar o mesmo número
 Mudar as representações dos números
 1.101 e 0.110 da base 2 para a base 10
 13, 0.75 e 3.8 da base 10 para a base 2
 53.7 da base 10 para a base 2
         da base 2 para a base 10
 Mudanças de bases diferentes de 10 podem ser feitas 
usando­se a base 10 como uma base intermediária
110.10
DIM04048
Representação de Números 
no Sistema 
 Números reais podem ser representados por 
uma reta contínua. Um sistema de números de 
ponto flutuante representa pontos discretos na 
reta real
 Quantos e quais números podem ser 
representados no sistema F(2,3,1,2)?
F  , t , m , M 
DIM04049
Representação de Números 
 Exemplos
Somente pontos discretos 
na reta de números reais 
podem ser representados 
no computador
DIM040410
Padrão IEEE 754
 Criado em 1985, se tornou um padrão para 
aritmética de ponto flutuante
 Implementado na grande maioria das CPUs
 Padrões para arredondamento, underflow e 
overflow
 Somente números na forma x/2k podem ser 
representados exatamente. Outros números 
têm representações com repetições de 
seqüências de bits, como
1/3 0.0101010101[01]…2
1/5 0.001100110011[0011]…2
DIM040411
Padrão IEEE 754
 Números representados por ­1sM2E, onde s 
(MSB) é o bit do sinal, M (frac) é um valor 
fracional na faixa [1.0,2.0) e E (exp) é o 
expoente da base 2
 Precisões 
Simples (8 exp bits, 23 frac bits)
Dupla (11 exp bits, 52 frac bits)
Estendida (15 exp bits, 63 frac bits)
s exp frac
DIM040412
Codificação no Padrão IEEE 
754
 exp 000…0 and exp 111…1
 Expoente é codificado com um bias
Exp: valor sem sinal do campo exp
Bias: valor do bias
• Precisão simples: 127 (Exp:1...254, E:­126...127)
• Precisão dupla: 1023 (Exp:1...2046, E:­1022...1023)
 Frac codificado com um 1 inicial implícito
M=1.xxx...x2
• xxx...x: bits de frac
• Mínimo quando frac é 000...0 (M=1.0) e máximo 
quando frac é 111...1 (M=2.0­)
DIM040413
Padrão IEEE 754 – 
Codificação Normalizada
 exp ≠ 00...0 and exp ≠ 11...1 
 Float F = 15213.0;
 1421310 = 111011011011012 = 1.11011011011012 X 213
 M=1.11011011011012 , Frac=1110110110110100000000002
 Expoente: E = 13, bias = 127, exp = 140 = 100001100
Floating Point Representation (Class 02):
Hex: 4 6 6 D B 4 0 0 
Binary: 0100 0110 0110 1101 1011 0100 0000 0000
140: 100 0110 0
15213: 1110 1101 1011 01
DIM040414
Padrão IEEE 754 – 
Codificação Não­Normalizada
 Exp = 00...0
 Expoente E = ­bias +1 
 M = 0.xx...x2
 Casos:
Exp=00...0, frac=00...0 – representa o valor 
0 (valores diferentes para +0 e ­0) 
Exp=00...0, frac=≠00...0  – representam 
números pequenos próximos de 0.0, 
perdendo precisão a medida que ficam 
menores (underflow “gradual”)
DIM040415
Padrão IEEE 754 – Valores 
Especiais
 exp = 11...1
 Casos:
 Exp = 111…1, frac=00...0
• Representa o valor infinito ∞, operações 
que geram overflow (positivo ou 
negativo), por exemplo 1.0/0.0 = ­1.0/­0.0 
= +∞ , 1.0/­0.0 = ­∞
Exp = 111…1, frac ≠ 00...0
• Not­a­number (NaN), representando 
casos onde nenhum valor numérico pode 
ser determinado, como srqt(­1) ou ∞ ­∞
DIM040416
Padrão IEEE 754
NaNNaN
+∞−∞
−0
+Denorm +Normalized­Denorm­Normalized
+0
DIM040417
Arredondamento em 
Ponto Flutuante
 Arredondar um número   por outro com um 
número de dígitos significativos, consiste em 
encontrar um número   , pertencente ao sistema 
de numeração, tal que        seja o menor possível
 Dado   , seja    sua representação em             
adotando arredondamento. Se         , então        , 
se não for, então escolhemos    e    tais que
x
x
∣x−x∣
x x F  , t , m , M 
x=0 x=0
s e
∣x∣=s×e , onde −11−12 
−ts1−12 
−t
DIM040418
Arredondamento em 
Ponto Flutuante
 Se    está fora do intervalo             o número não 
pode ser representado no sistema. Caso 
contrário pode­se calcular 
    e truncar o resultado em   dígitos, obtendo 
[−m , M ]
t
e
s1
2

−t
=0.d1 d 2d t d t1
x=sinal x 0.d1 d 2d t ×
e
DIM040419
Arredondamento em 
Ponto Flutuante
 Considere o sistema F(10,3,5,5). Represente os 
números x1=1234.56, x2=­0.00054962, 
x3=0.9995, x4=123456.7, x5=­0.0000001
 Os valores permitidos para s são
 Para x1=1234.56 temos
10−11−12 10
−3s1−12 10
−3
0.09995s0.9995
x1=1234.56⇒∣x1∣=0.123456×10
4
s1
2
10−3=0.1234560.0005=0.123956
x1=0.123×10
4
DIM040420
Operações Aritméticas 
em Ponto Flutuante
 Como arredondamentos são feitos após cada 
operação aritmética, as operações de adição, 
subtração, divisão e multiplicação não são 
associativas nem distributivas, ao contrário de 
quando usadas com números reais
 Considerando um sistema com base 10 e 3 
dígitos significativos
11.43.185.05  e 11.43.185.05
3.18×11.4
5.05
 e  3.18
5.05
×11.4
3.18×5.0511.4 e  3.18×5.053.18×11.4
0.3330.3330.333
10 vezes
 e 3.31
DIM040421
Efeitos Numéricos
 Além dos erros causados por arredondamentos 
em operações aritméticas, alguns efeitos afetam 
a qualidade dos cálculos, como cancelamento, 
propagação de erros, instabilidade numérica e 
mal condicionamento
 O cancelamento ocorre na subtração de dois 
números quase iguais, pois o expoente 
permanece o mesmo e os dígitos iniciais são 
todos zero, perdendo­se dígitos significativos do 
resultado
9.876−9.875
9.876=0.9937806599×102  e 9.875=0.9937303457×102
9.876−9.875=0.0000503142×102=0.5031420000×10−2
DIM040422
Cancelamento
 Como resolver o problema? Neste caso 
podemos usar a identidade abaixo para 
obtermos um resultado preciso
 Exemplo: resolva a equação
 x− y=
x−y
 x y
9.876−9.875=
1
9.876−9.875
=0.5031418679×10−4
x 2−1634x2=0 x=1634±1634
2
−42
2
=817±667487
x1=817816.9987760=0.1633998776×10
3  e  x2=817−816.9987760=0.1224000000×10
−2
x1×x 2=2 x 2=
1
0.1633998776×103
=0.1223991125×10−2DIM040423
Propagação de Erros
 A propagação de erros ocorre quando uma ou mais 
somas parciais têm o expoente maior que a soma final
e−x=∑
k=0
∞
−1k x
k
k !
e−5.25=0.10000−0.52500×101  
0.13781−0.241170.31654−0.332360.29082−0.218110.14314×102  
−0.834970.43836−0.2092 2×1010.915 32−0.369650.13862×100  
−0.48 5160.15 919×10−1−0.4 91640.14339×10−2−0.396200.10401×10−3
−0.26003×10−40.62050−0.14163×10−50.30982×10−6
=0.65974×10−2
s=∑
k=1
n
ak ,
s1=a1,   sk=sk−1ak ,   k=2,3, , n
DIM040424
Propagação de Erros
 Mas o valor correto com cinco dígitos 
significativos é 
 Podemos recalcular o valor usando a identidade   
         e a fórmula 
e5.25=0.19057×103e−5.25= 1
0.19057×103
=0.52475×10−2
e−x= 1
e x
e x=∑
k=0
∞ x k
k !
e−5.25=0.52475×10−2
DIM040425
Instabilidade Numérica
 Se um resultado intermediário é contaminado por 
um erro de arredondamento, este erro pode 
influenciar todos os resultados subseqüentes que 
dependem deste valor, propagando, assim, os 
erros de arredondamento
 Entretanto, os erros de arredondamento, podem, 
em alguns casos, cancelar­se uns com os outros 
parcialmente ou totalmente, resultando em um 
erro desprezível no final. Algoritmos com esta 
propriedade são chamados estáveis
DIM040426
Instabilidade Numérica
 A instabilidade numérica ocorre quando os erros 
intermediários têm uma influência muito grande no 
resultado final I n=e−1∫
0
1
xn ex dx
I n=e
−1 {[ xn ex ]0
1
−∫
0
1
n x n−1 ex dx },  ou seja 
I n=1−n I n−1 ,   n=1,2, ,
Como  I 0=e
−1
∫
0
1
ex dx=e−1e−1=0.6321,  temos 
I 0=0.6321, I 1=0.3679 I 2=0.2642 I 3=0.2074
I 4=0.1704 I 5=0.1480 I6=0.1120 I 7=0.2160
DIM040427
Instabilidade Numérica
 Entretanto o resultado de I7 está errado, já que
 Observe que a seqüência In é decrescente. Neste caso, 
usando a relação de recorrência anterior o erro cresce 
de acordo com o fator n a cada passo. A relação de 
recorrência é instável, mas a relação inversa pode não 
ser, vejamos:
 Não temos o valor de In, para n > 0, mas sabemos que   
In → 0 quando n → ∞
I n=1−n I n−1 ,   n=1,2, , I n−1=
1−I n
n
I 7e
−1 max0e1e
x
∫
0
1
xn dx 1
n1
=
1
8
DIM040428
Instabilidade Numérica
 Entretanto, setando I20=0 e calculando a relação de 
recorrência acima, obtemos I7=0.1123835, o 
resultado com todos os dígitos corretos
 Neste caso, deve se ter cuidado com o valor inicial 
setado, para que um número suficiente de iterações 
sejam feitas, diminuindo, assim, o erro da estimativa 
inicial
DIM040429
Mal Condicionamento
 Na resolução de um problema numérico, se cria 
um algoritmo para resolver um problema,a partir 
de dados de entrada
 Problemas cujos resultados dependem 
continuamente dos dados de entrada são ditos 
bem postos, em oposição aos problemas mal 
postos, mal condicionados ou críticos
DIM040430
Mal Condicionamento
 Por exemplo, resolva os sistemas lineares abaixo
 Uma pequena mudança nos dados de entrada 
gerou uma grande mudança na saída, isto é, 
esse é um problema mal­condicionado
 A interpretação geométrica desse resultado nos 
mostra quão sensível o problema é à mudanças 
nos dados de entrada
{x + y = 2x + 1.01y = 2.01 {
x + y = 2
x + 1.01y = 2.02
DIM040431
Mal Condicionamento
 Seja X o espaço dos dados, d(x,y) uma função 
de distância, e P um processo contínuo que 
transforma os dados x no resultado y, isto é, 
y=P(x), a definição de continuidade matemática 
exige que para cada  0, ∃ () > 0, tais que
 Quanto maior a função () puder ser escolhida, 
mais contínuo é o processo P
∣P  x −P x ∣   sempre que  ∣x−x∣
DIM040432
Mal Condicionamento
 O número de condição do problema indica se um 
problema é ou não mal condicionado
 Seja y=P(x), com P diferenciável. Então, a mudança 
em y causada pela mudança em x pode ser 
aproximada pelo diferencial de y. Logo, o 
comprimento de representa o número de condição de 
um problema num ponto x. O número de condição 
relativa é definido por
 Se cr ≤ 1 dizemos que o problema é relativamente 
bem condicionado
cr=
∣P'  x∣
∣P  x∣
DIM040433
Mal Condicionamento
 Calculando o número de condição relativa
 Para x=0 e x=1, cr = ∞, ou seja, ele é extremamente 
mal condicionado. No intervalo 0.1537 ≤ x ≤ 0.5360, 
cr ≤ 1  o problema de calcular f é bem condicionado
f  x = ln 1 / x 
−
1
8
f '  x=−1
8
 ln1/ x 
−
9
8 −1/ x2
1/ x
=
1
8x
 ln1 /x 
−
9
8
cr=
∣ f '  x ∣
∣ f  x∣
=
1
8x ln1/ x 
DIM040434
Mal Condicionamento
 Teoricamente, o termo mal condicionado é usado 
para modelos matemáticos e o termo instabilidade 
para algoritmos, mas na prática ambos são usados 
sem distinção
DIM040435
Efeitos Numéricos
DIM040436
Efeitos Numéricos
DIM040437
Efeitos Numéricos
DIM040438
Efeitos Numéricos
DIM040439
Efeitos Numéricos
DIM040440
Ariane 5
 Explodiu 37 segundos após o lançamento, 
com uma carga avaliada em 
US$500,000,000.00 
 Motivo: software calculava velocidade 
horizontal usando ponto flutuante, e 
convertia resultado para um inteiro com 16 
bits
 Software funcionou sem problemas para o 
Ariane 4, mas não para o Ariane 5 
DIM040441
Processamento Digital 
de Sinais
 Existem várias definições de quais tarefas 
Processamento de Imagens engloba, logo 
existem várias maneiras de classificar as 
etapas fundamentais em PI
 A figura do próximo slide mostra uma destas 
classificações, separando as fases em dois 
grupos, de acordo com a natureza de seus 
resultados
 Dependendo da aplicação, várias ou apenas 
uma das etapas da figura a seguir podem 
estar presentes em um sistema real