****************************************** Clase 18: Representación de Punto Flotante ****************************************** **Bibliografía de la Clase** * Numerical Linear Algebra. L.N. Trefethen. Chapter 3, Lecture 13: ``Floating Point Arithmetic`` * What Every Computer Scientist Should Know About Floating Point Arithmetic [FloatP]_. Introducción ------------ * Los computadores no pueden representar los números reales (`\mathbb{R}`) o los números complejos (`\mathbb{C}`) de manera exacta. * Muchas aplicaciones requieren de números que se mueven en rangos **muy** grandes [LargeN]_: .. math:: \text{Número de bits de un disco duro de } 500 [Gb]: 500 \times 10^{9} \text{Número estimado de átomos en el "universo observable": } 10^{80} \text{Número de células en el cuerpo humano: } 10^{14} \text{Tamaño promedio de un átomo simple: 1 angstrom = } 10^{-10} [m]. \text{ Para medir tamaño de núcleos y partículas } \rightarrow \text{ fermi}= 10^{-15} [m] \text{1 googol}: 10^{100} \approx 70! * Los computadores aproximan los `\mathbb{R}` mediante el sistema de **números de punto flotante**, utilizando un número finito de bits para lr representación. * Se pueden representar números ``suficientemente grandes y pequeños``. El estándar IEEE 754 permite: .. math:: 1,79 \times 10^{308} 2,23 \times 10^{-308} Números de Punto Flotante ------------------------- Recordemos primeramente la representación científica: .. math:: a \times 10^b a: \text{ coeficiente, significando o mantisa} b: \text{ exponente } **Ejemplo:** .. math:: 42 = 4,200 \times 10^{1} 1024 = 1,024 \times 10^{3} -0.0625 = -6.250 \times 10^{-2} La representación de punto flotante tiene una **base** `\beta` y una **precisión** `p`. Si `\beta = 10` y `p=3`, el número 0,1 es: .. math:: 0,1 \rightarrow 1,00 \times 10^{-1} Si `\beta = 2` y `p=24`, el número decimal 0.1 no puede ser representado exactamente, pero es aproximadamente: .. math:: 1,10011001100110011001101 \times 2^{-4} .. topic:: Representacion de Números de Punto Flotante [FloatP]_: En general, un número de punto flotante será representado como: .. math:: \pm d,dd\ldots d \times \beta^{e} donde `d,dd\ldots d` es denominado el significando, mantisa o fracción que tiene `p` dígitos, y `e` es el exponente . Más precisamente: .. math:: \pm d_0, d_1 d_2 \ldots d_{p-1} \times \beta^e \text{ representa el número:} \pm ( d_0 + d_1 \beta^{-1} + \ldots + \ldots d_{p-1} \beta^{-(p-1)})\beta^{e}, \ \ (0 \leq d_i < \beta) Por lo tanto: * Hay `\beta^{p}` posibles significandos * `e_{max} - e_{min} + 1` posibles exponentes * número de bits necesarios para la representación: `\lceil log_2 (e_{max} - e_{min} + 1) \rceil + \lceil log_2 (\beta^p) \rceil + 1`. El `+1` es para el bit del signo. .. COMIENZO COMENTARIO ***************** .. Considerar un sistema ideal de números de punto flotante, tal que: .. .. * El sistema consiste en un subconjunto discreto `\mathbb{F}` de los números reales `\mathbb{R}` determinados por: .. .. * un entero `\beta \geq 2`: base .. .. * un entero `t \geq 1`: precisión .. * Los elementos de `\mathbb{F}` corresponde al número 0 junto con los números que tienen la siguiente forma: .. .. math:: .. .. x = \pm (\frac{m}{\beta^{t}})\beta^{e} .. .. `m` es un entero en el rango `1 \leq m \leq \beta^{t}` y `e \in \mathbb{Z}`. .. .. * Equivalentemente se puede restringir: `\beta^{t-1} \leq m \leq \beta^{t}-1 \Rightarrow` la elección de `m` es única. .. .. * `\pm (\frac{m}{\beta^{t}})` corresponde a la mantisa de `x` y `e` corresponde al exponente. .. FIN COMENTARIO ************************************************************** La representación punto flotante no es necesariamente única: .. math:: 0,01 \times 10^1 \ \ = \ \ 1,00 \times 10^{-1} \ \ = \ \ 0,1 Si el primer dígito del significando o mantisa es distinto de cero (`d_0 \neq 0`), se dice que la representación está **normalizada** `\Rightarrow` representación única. 1 **Ejercicio en clases 1** * Si `\beta=2 , p=3 , e_{min}=-1` y `e_{max}=2` ¿cuántos números punto flotante normalizados se pueden representar? **Ejercicio Propuesto** * Explicar como es la representación del 0 en la representación de punto flotante (`+0` y `-0` en el estándar IEEE 754). Estándar IEEE 754 ~~~~~~~~~~~~~~~~~ Las dos representaciones más usadas de representación de punto flotante están definidas en el estándar 754 de la `IEEE `_: * presición simple: `\beta=2 , p=24, e_{min}=-126, e_{max}=127`, 8 bits para el exponente. * presición doble: `\beta=2 , p=53, e_{min}=-1022, e_{max}=1023`, 11 bits para el exponente. **Ejemplo: Presición Doble** .. image:: _static/ieee754.png :align: center :scale: 100 :alt: caption * 64 bits para la representación **normalizada** : 1 bit para el signo, 11 bits para el exponente y 52 bits para la mantisa. * Si el bit del signo es 0 el número es positivo, y si el bit es 1, el número es negativo. * Uso de ``biased exponent``. El bias es 1023 y se debe restar al exponente: .. topic:: Exponente El exponente puede ser positivo o negativo, por lo tanto se utiliza la ``biased representation``. En la presición simple, el bias es 127, y en la presición doble, el bias es 1023. Esto significa que si `k` es el valor del exponente obtenido (obtenido de los 8 u 11 bits), el valor del exponente en la representación de punto flotante es `k - 127` (o `k - 1023`). **Ejercicio en clases 2** Considerar 1 bit para el signo, 4 bits para el exponente y 3 bits para la mantisa (normalizada). .. math:: (-13,9)_{(10)} = - (1,101)_2 \times 2^{(11)_2} * ¿Cómo queda la representación binaria si se tiene un ``biased exponent``? Por lo tanto, la representación de punto flotante se puede expresar: .. math:: (signo) (1 + \sum_{i=1}^{52}b_i 2^{-i}) \times 2^{exponente - 1023} .. En detalle, un número perteneciente a `\mathbb{F}` puede ser representado de la siguiente manera: .. .. .. literalinclude:: codigo/fp.py .. :language: python .. :linenos: .. .. .. .. math:: .. .. m_i \in \{ 0,1, \ldots , \beta -1 \} .. .. \pm \sum \limits_{k=1}^{t} m_i \beta^{-i} \times \beta^{(\pm \sum_{j=1}^s e_j \beta^{j})} = .. .. \pm \left ( m_1 \frac{1}{\beta}+ m_2 \frac{1}{\beta^2} + \ldots + m_t \frac{1}{\beta^t} \right ) \times \beta^{\pm (e_1 \beta^1 + e_2 \beta^2 + \ldots + e_s \beta^{s})} .. .. note:: Se dice que la representación de punto flotante de un número está **normalizada** si el primer dígito de la mantisa es distinto de 0, por lo tanto, en el sistema binario es 1. En el estándar IEEE 754 no se almacena aquel valor, por ese motivo se suma 1 a la mantisa. **Ejemplo** Representación del número 23, usando el estándar IEEE 754 de presición simple: 32 bits, 1 bit para el signo, 8 bits para el exponente y 23 bits para la mantisa: .. math:: (23)_{10}= \mathop{0}_{signo}\ \ \ \ \ \mathop{1\ 1\ 0\ 0\ 0\ 0\ 0\ 1}_{exponente} \ \ \ \ \mathop{0\ 1\ 1\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0}_{mantisa} \text{ bias: } 127 \text{exponente: } 2^0 + 2^1 + 2^7 = 131 \rightarrow \text{ exponente }= 131 - 127 = 4 (23)_{10} = \left (1 + 0\times \frac{1}{2} + 1 \times \frac{1}{4} + 1 \times \frac{1}{8}+ 1 \times \frac{1}{16} + 0 \times \frac{1}{32} + \ldots + 0 \times \frac{1}{2^{23}}\right) \times 2^4 (23)_{10} = \frac{16 +4+2+1}{16} \times 2^4 Se puede revisar `acá `_. .. **Ejemplo** .. .. Representación del número 23, usando el estándar IEEE 754 de presición simple: 32 bits, 1 bit para el signo, 8 bits para el exponente y 23 bits para la mantisa: .. .. .. math:: .. .. (23)_{10}= \mathop{1}_{signo}\ \ \ \ \ \mathop{1\ 1\ 0\ 0\ 0\ 0\ 0\ 1}_{exponente} \ \ \ \ \mathop{0\ 1\ 1\ 1\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0}_{mantisa} .. .. \text{ bias: } 127 .. .. \text{exponente: } 2^0 + 2^1 + 2^7 = 131 \rightarrow \text{ exponente }= 131 - 127 = 4 .. .. (23)_{10} = \left (1 + 0\times \frac{1}{2} + 1 \times \frac{1}{4} + 1 \times \frac{1}{8}+ 1 \times \frac{1}{16} + 0 \times \frac{1}{32} + \ldots + 0 \times \frac{1}{2^{23}}\right) \times 2^4 .. .. (23)_{10} = \frac{16 +4+2+1}{16} Gaps ~~~~ Debido a la representación de punto flotante, existen espacios (``gaps``) entre los números, por ejemplo, en el estandar IEEE 754 de **doble precisión**, el intervalo [1,2] es representado por el subconjunto discreto: .. math:: 1, \ 1 + 1\times 2^{-52}, 1+ 2\times2^{-52}, 1 + 3\times 2^{-52}, \ldots, 2 \ \ \ (\bigstar) El intervalo `[2,4]\Rightarrow (\bigstar) \times 2`: .. math:: 1 \times 2, \ [1 + 1\times 2^{-52}] \times 2, [1+ 2\times2^{-52}] \times 2, [1 + 3\times 2^{-52}] \times 2, \ldots, 2 \times 2 2, \ 2 + 2 \times 2^{-52}, 2+ 2\times 2 \times 2^{-52}, 2 + 3 \times 2 \times 2^{-52}, \ldots, 4 = 2, \ 2 + 1\times 2^{-51}, 2+ 2\times 2^{-51}, 2 + 3 \times 2^{-51}, \ldots, 4 * En general: .. math:: [2^{j},2^{j+1}] \text{ se representa por: } (\bigstar) \times 2^{j} El espacio entre números adyacentes son (de cierta forma) nunca mayores que `2^{-52}\approx 2.22 \times 10^{16}`. Parece despreciable la cifra, pero en algoritmos mal construídos se tornan inestables! Machine Epsilon --------------- Sea `p=t=` presición. El número **machine epsilon** está definido por: .. math:: \epsilon_{machine}=\frac{1}{2}\beta^{1-t} Este número corresponde a la mitad de la distancia entre 1 y el siguiente número punto flotante. En otras palabras, `\epsilon_{machine}` es tan grande como los espacios entre los números de punto flotante. .. topic:: Propiedad 1 Sea `\mathbb{F}` el conjunto de los números de representación de punto flotante. `\forall x \in \mathbb{R}, \exists \ x' \in \mathbb{F} \text{ tal que } \lvert x-x'\rvert \leq \epsilon_{machine}\lvert x \rvert` El estándar IEEE 754 para precisión doble y simple, especifica que el `\epsilon_{machine}` es `2^{-24} \approx 5.96\times 10^{-8}` y `2^{-53}\approx 1.11\times 10^{-16}`, respectivamente. Sea `fl: \mathbb{R} \rightarrow \mathbb{F}` una función que entrega la aproximación de punto flotante más cercana a un número real, para lo cual se tiene la siguiente desigualdad: .. math:: \forall x \in \mathbb{R}, \exists \epsilon , | \epsilon | \leq \epsilon_{machine}, \text{ tal que } fl(x)=x(1 + \epsilon) Es decir, la diferencia entre el numero real y su representación de punto flotante más cercana es siempre menor que `\epsilon_{machine}`, en términos relativos. Aritmética de Punto Flotante ---------------------------- No sólo se representan los números reales, sino que además se realizan cálculos con ellos. En un computador los cálculos matemáticos se reducen a: `+, -, \times, /`. * Matematicas: Operaciones en `\mathbb{R}` * Computador: Operaciones en `\mathbb{F} \rightarrow` operaciones de punto flotante: `\oplus ,\ominus ,\otimes , \oslash` Un computador debe estar construido considerando el siguiente principio de diseño: .. .. math:: .. .. \text{ Sea } x,y \text{ números arbitrarios de punto flotante } x,y \in \mathbb{F} .. .. \text{ Sea } \ast \text{ alguna de las operaciones } +, -, \times, / , \text{ y sea } \circledast \text{ la operación análoga en punto flotante } .. topic:: Propiedad 2 Sea `x,y` números arbitrarios de punto flotante `x,y \in \mathbb{F}`. Sea `\ast` alguna de las operaciones `+, -, \times, /`, y sea `\circledast` la operación análoga en punto flotante .. math:: x\circledast y =fl(x\ast y) De la Prop. 1 y Prop. 2 se puede concluir que un computador tiene una simple y poderosa propiedad: .. topic:: Axioma Fundamental de Aritmética de Punto Flotante Para todo `x,y \in \mathbb{F}`, existe `\epsilon` con `\lvert\epsilon \rvert \leq \epsilon_{machine}`, tal que .. math:: x\circledast y =fl(x\ast y)(1+\epsilon) **References** .. [FloatP] David Goldberg. What Every Computer Scientist Should Know About Floating Point Arithmetic. ACM Computing Surveys, 1991. .. [LargeN] `Wikipedia, Large Numbers `_