programación : c (1)aplicaciones.cimat.mx/.../files/jbhayet/files/clase1_0.pdf · 2018. 10....

Programación : C (1)

Dr. J.B. Hayet

CENTRO DE INVESTIGACIÓN EN MATEMÁTICAS

Agosto 2013

,J.B. Hayet Programación, Agosto 2013 1 / 61

Outline

1 Presentación de la clase

2 Los datos en C y en la máquina


Presentación de la clase

Outline





Programa/evaluación

1 C (∼ 4-8 sesiones)2 C++ (∼ 10 sesiones).3 Algoritmica. . .

4 Temas selectos. . .

Tipo Frecuencia Porcentaje de la evaluación finalTareas ≈ en cada sesión 40 %

Proyecto(s) uno 30 %Examenes dos 30 %



Preguntas y ayudant́ıa

Información sobre la clase en:http://www.cimat.mx/~jbhayet/CLASES/PROGRAMACION/,

tareas y clases en pdfs,

notificaciones, errata sobre las tareas. . .

Dudas

Google group cimat-90spa1 arrobasegooglegroups.com (Facebook?)

Ayudante o profesor.

Mail; tel;

Lista de correo


http://www.cimat.mx/~jbhayet/CLASES/PROGRAMACION/


Tareas

Llegan en la tarde de la clase ≈ 15h.1 semana para terminarlas (redondeado al d́ıa siguiente):

jueves 7 octubre, 15h45 -> jueves 14 octubre, 23h59.

Penalidad por retraso: -0.25pt/d́ıa y sólo si se habráavisado al ayudante del retraso.Cuidado a no acumular retraso. . .

[email protected]



Tareas

Formato:

ProgT##_ABCD

con ## el número de la tarea y ABCD sus iniciales

Preferentemente comprimido (.zip, .tar.gz..)

Asunto del mail: el mismo formato (ProgT##_ABCD).



Tareas

Usar código estándar (compatibilidad) para facilitar laevaluación. . .

Unas soluciones : CodeBlocks, KDevelop, Dev-c++, Anjuta,Eclipse, XCode, QtCreator. . . (ver sesión práctica)



Alrededor de la clase

Asistencia a seminarios.

Asistencia a clases de inglés.

El semestre va a ser pesado.Organizar bien su tiempo. Ser pragmático.Guardarse tiempo para actividades extra-escolares. . .


Los datos en C y en la máquina

Outline





Tipos de datos

Memoria de la computadora: serie de bytes (octetos, en general),que se pueden direccionar; cada byte con dirección única enmemoria (identificada por número en 32 bits, en máquinas 32 bits).

#4

Memoria de 512 Mo

#536870911#536870910#536870909

#0#1#2#3



Tipos de datos

byte 6= bit,

addressable unit of data storage large enough to hold anymember of the basic character set of the executionenvironment,

viene de “to bite” y la y es para no confundir con bit,

en general, 1 byte = 1 octeto = 8 bits.



Tipos de datos

Para verificar, busca el archivo limits.h en tu sistema:

Bidarray[~][15:47]>more /usr/include/i386/limits.h

#ifndef _I386_LIMITS_H_

#define _I386_LIMITS_H_

#include

#include

#define CHAR_BIT 8 /* number of bits in a char */



Tipos de datos

Máquinas procesan varios bytes al mismo tiempo(depende de sus registros): esos paquetes de bytes son loswords.

Hoy, en la mayoŕıa de los casos, son de 32 bits pero hay más ymás máquinas de 64 bits.En general, los sistemas k-bits tienen registros y buses de kbits (hardware), y sistemas de explotación que manipulandirecciones en memoria de k bits (software). Se puede teneruna máquina 64-bits y un OS 32-bits. Pero no al revés.



Tipos de datos

En programación en C/C++

el tipo define dos cosas : el numero de octetos que se va ausar para el dato y la manera de usar cada uno de losoctetos;

los tipos elementales son los caracteres, enteros yflotantes (para números reales);no hay estándar en cuanto al tamaño de los tipos.



sizeof

En C/C++, función que da el numero de bytes necesarios parael tipo/la variable pasado en argumento,

sizeof(int),

sizeof(x), donde x es una variable.



Datos

This is what is guaranteed about sizes of fundamental types:

1 == sizeof(char)


En una máquina 32 bits t́ıpica

Tipo Tamaño (en bytes) Rango de valoreschar 1 [−128, 127]short 2 [−32768, 32767]

int 4 [−2147483648, 2147483647]long 4 [−2147483648, 2147483647]float 4 [1.18× 10−38, 3.4× 1038]

double 8 [2.2× 10−308, 1.8× 10308]long double 10 [1.18× 10−4932, 3.4× 104932]apuntadores 4 [0, 232 − 1]

unsigned : sólo valores positivos, adaptar el rango enconsecuencia.



En una máquina 64 bits

Todav́ıa no hay estándar único! (LLP64/LP64)

Tipo Tamaño (en bytes)char 1short 2

int 4long 4/8

long long 8apuntadores 8

Ejemplo :

Windows 64 : long de 32 bits (ex: Window 7),

Unix 64 : long de 64 bits (ex: MacOS X, Linux. . . ).



Tipos enteros

Para representar un subconjunto de N (“unsigned”).Representación de los positivos en base 2, sobre n bits

a =n−1∑i=0

ai2i .

¿Rango?

Ejemplos:

unsigned int sobre 32 bits : [0,4 294 967 295]

unsigned short sobre 16 bits : [0, 65 535]



Tipos enteros

Para representar un subconjunto de Z:

s a

n-11Si tenemos un tipo entero con n bits (8, 16, 32. . . ):

Signo con el bit de peso fuerte : s = 0 para positivos (aśıse puede identificar fácilmente si es positivo o negativo).Los positivos representados en base 2 sobre n − 1 bits,

a =n−2∑i=0

ai2i .

¿Negativos ?,

J.B. Hayet Programación, Agosto 2013 21 / 61


Tipos enteros

¿Representar negativos ?

Nos gustaŕıa pasar rápido de un entero a su negativo.Nos gustaŕıa que −(−a) = a, que a + (−a) = 0.Nos gustaŕıa tener operaciones aritméticas rápidas;idealmente, sustracción ES adición, no queremos tener casos:

a + (−b) = a − b

Representación signo+valor absoluto. ¿Problemas ?



Tipos enteros

Signo+valor absoluto :

el opuesto se saca muy rápidamente, pero. . .

un número y su opuesto no suman a cero. . .

las adiciones de enteros signados no funcionan tal cual. . .



Tipos enteros

Representación complemento a uno.

a =n−1∑i=0

(1− ai)2i = 2n − 1− |a|.

Operación reversa : igual. . .

¿Problemas ?

Hay dos representaciones para cero.

(-2) + 1 = ?

2 + (-1) = ?



Tipos enteros

Representación complemento a uno mas uno (complemento ados),

a =n−1∑i=0

(1− ai)2i + 1 = 2n − |a|.

Operación reversa : igual. . .

No distinción entre substracción y adición.Representación única de 0.

¿Rango función de n ?

¿Cómo se representan 131 y -131 en un short ?



Tipos enteros

Complemento a dos:

cálculo rápido: después del primer uno (a excluir), tomar elcomplemento a uno de todos los d́ıgitos,

en la adición, detección de overflow , ¿una manera rápidade detectarla ?

En un procesador, hay registros que guardan (1) el acarreo en laoperación actual, (2) el status de overflow o no.



Representación de reales

ds

1

a

n-1-p p

Punto fijo : se usa cuando uno quiere trabajar con una precisiónabsoluta dada.

Representación :z = sa + d2−p.

¿Rango?

No hay soporte de reales a punto fijo por default en C(libreŕıas especializadas).



Reales en punto fijo

Ejemplo : Representar 78.3125 (decimal) con n = 16 y p = 6.



Reales en punto fijo : mas y menos

+ Permiten precisión arbitraria, la que quieras (o que quiera tucliente/jefe).

+ Rápido (fundamentalmente similar a enteros).

- No muy flexible.

- Se gasta espacio para pequeños números o números con pocascifras después del punto.

- “Consume” muchos bits : para resolución de 165536

≈ 1.5 10−5se necesitan 16 bits después del punto !



Reales flotantes

n-1-q

s

1

k m

q

Norma IEEE 754.Representación :

f = s.m.be

e = k − (2q−1 − 1) ; 0 ≤ m < bAmbigüedad ?



Reales flotantes

n-1-q

s

1

k m

q

Elemento Signo Exponente Mantisafloat 1 8 23

double 1 11 52



Reales flotantes

Mantisa normalizada : un sólo d́ıgito no nulo antes de lacoma (=1 si b = 2)

1.0101001

8.8178582

En binario, tenemos efectivamente 24/53 bits pararepresentarla con 1 ≤ m < 2 y b = 2, el carácter 1 estáimpĺıcito

f = s.(1 + m.2−(n−1−q)).2e

Rango del exponente :

−2q−1 + 1 ≤ e ≤ 2q−1



Reales flotantes

Ejemplo : representar todos los reales flotantes positivos conb = 2, q = 2, n = 5.

¿Representar 0?



Flotantes : casos especiales

La norma IEEE 754 define tres números adicionales : NaN ,+∞, −∞ que permite manejar operaciones de tipo 1/0. . .¿Como representarlos, ademas del 0 ?

Solución : usar los dos valores extremos posibles delexponente para representarlos. Caso de los float :

e = k − 127 m f−126 ≤ e ≤ 127 0 ≤ mf < 223 ±1.m × 2e

128 0 ±∞128 6= 0 NaN−127 0 ±0−127 6= 0 ±0.m × 2−126




Caso de los double :

e = k − 1023 m f−1022 ≤ e ≤ 1023 0 ≤ mf < 252 ±1.m × 2e

1024 0 ±∞1024 6= 0 NaN−1023 0 ±0−1023 6= 0 ±0.m × 2−1022




Observar el valor binario de número que representa 0.

Los casos de ±∞ y NaN corresponden a exponente a 11111....Con exponente nulo y mantisa no nula, son números enunderflow (subdesbordamiento , no normalizados).



Flotantes : ĺımites

Desbordamiento (overflow), subdesbordamiento (underflow).

Redondeos.



Flotantes : el crash de Ariane 5



Flotantes : el crash de Ariane 5

El primer Ariane 5 explotó en 1996 (500 millones de dólaresevaporados) porque los sensores inerciales dejaron de enviardatos : estaban reseteando por un fallo debido a unaexcepción no procesada.Esta excepción fue generada por un desbordamiento(overflow) : una velocidad estaba guardada como double (64bits), y estaba convertida a un short en un pedazo deprograma. Los ensayos hab́ıan sido hechos con datos de Ariane4 (que era menos rápida). Hubo una excepción pero no hab́ıamecanismo para tratarla.

Más información aqúı.


http://en.wikipedia.org/wiki/Ariane_5_Flight_501


Flotantes : redondeo

Todos los reales no pueden representarse correctamente : porejemplo, 0.1 (decimal) necesita una infinidad de d́ıgitos en unsistema binario !




i n t main ( ) {

fo r ( double x = 0 ; x != 0 . 3 ; x += 0 . 1 ) ;

}




Varias maneras de redondear un real x tal que x− ≤ x ≤ x+, con x−y x+ reales flotantes en una representación dada

Hacia −∞.Hacia +∞.Hacia 0.

Hacia el más cercano (en caso de igualdad, tomar el flotantede mantisa par).




Redondeo correcto en operaciones artimeticas: mismo resultadoque si calculas el resultado exacto y luego redondeas. La normaimpone el redondeo correcto con el mismo modo para la adición, lasubstracción, la multiplicación, la división y la ráız cuadrada.




Con redondeo correcto, llegamos a poder dar un intervalo parael resultado exacto de cada operación.

Portabilidad.

Operaciones como log o cos no incluidas en la norma.




En 1991, una bateŕıa Patriot se activó para interceptar un Scud,durante la Primera Guerra del Golfo. El cálculo de la fecha dentrodel sistema de navegación del misil estaba hecho por mútiples de 1

10

de segundos. Llevaba en consecuencia una aproximaciónredondeada de un décimo de segundo, sobre 24 bits :209715.2−21, error de 10−7 segundos cada décimo de segundos. Labateŕıa hab́ıa sido prendido como 100 horas antes. . . Erroracumulado 0.34s (demasiado). Balance : 28 muertos.



Flotantes : doble redondeo

Considera x = 1.0110100000001 .

Redondeado mas cercano de x a 9 bits : y = 1.01101000

Redondeado mas cercano de y a 5 bits : z = 1.0110

Redondeado mas cercano de x a 5 bits : z ′ = 1.0111 !!

Puede ser un problema con los FPUs de los procesadores x86 quetrabajan internamente con doble precisión extendida (64 bits demantisa) que es luego convertida a doble precisión.

Problema sólo con redondeo al mas cercano.

http://www.vinc17.org/research/extended.en.html


http://www.vinc17.org/research/extended.en.html


Flotantes : representabilidad

En double, el flotante normalizado más pequeño representablees x = 1.0× 2−1022.Considera y = (1 + 2−52)× 2−1022, ¿es representable ?Ahora considera x − y , ¿como está representado ?Que pasaŕıa con :

i f ( x!=y )z = 1 . 0/ ( x−y ) ;

Hacer los tests sobre x − y !i f ( f a b s ( x−y)> e p s i l o n )

z = 1 . 0/ ( x−y ) ;



Flotantes

#i n c l u d e #i n c l u d e i n t main ( ) {

f l o a t f = pow ( 2 . 0 , −2 3 ) ;f l o a t a = ( 1 . 0 )∗ pow (2 ,−125);f l o a t b = (1.0+ f )∗pow (2 ,−125) , z ;i f ( a!=b )

f p r i n t f ( s t d e r r , ”a and b have d i f f e r e n t r e p r e s e n t a t i o n s \n” ) ;e l s e

f p r i n t f ( s t d e r r , ”a and b have same r e p r e s e n t a t i o n s \n” ) ;f p r i n t f ( s t d e r r , ” V a l s : %e %e %e\n” , a , b , f ) ;f l o a t d = a−b ;z = 1 . 0 f /d ;uns igned i n t i d = ∗( uns igned i n t ∗)&d ;f p r i n t f ( s t d e r r , ” D i f f : %e \n” , d ) ;f p r i n t f ( s t d e r r , ” D i f f : %x \n” , i d ) ;

uns igned i n t i z = ∗( uns igned i n t ∗)& z ;f p r i n t f ( s t d e r r , ” D i f f i n v : %e \n” , z ) ;f p r i n t f ( s t d e r r , ” D i f f i n v : %x \n” , i z ) ;r e t u r n 0 ;

},

J.B. Hayet Programación, Agosto 2013 48 / 61


Flotantes

Macaye[CLASE1][15:38]>./test2

a and b have different representations

Vals: 2.350989e-38 2.350989e-38 1.192093e-07

Diff : -2.802597e-45

Diff : 80000002

Diff inv : -inf

Diff inv : ff800000

Interpretación ?



Flotantes : error absoluto al redondeo

Es el error sobre el último d́ıgito de la mantisa. Notando r el númerode d́ıgitos después del punto, en el caso del redondeo al máscercano, en base b

(b/2)× b−r−1 × be .



Flotantes : ulp

Es el error que se hace medido en el último d́ıgito (unit in thelast place). Por ejemplo, si z está representado por d .dd . . . dd × be ,el error en ulps es

|d .dd . . . dd − (z/be)|br

Si r = 3, b = 10, cuál es el error en ulps por aproximar.0314159 por 3.140× 10−2 ? por 3.142× 10−2 ?Un redondeo al más cercano tiene como error máximo .5 ulp.



Flotantes : error relativo

(Valor exacto − Valor representado)/(Valor exacto)

Pregunta : ¿a qué error relativo corresponde un redondeo al máscercano (.5 ulp) ?Los valores están entre be y b × be , entonces el valor relativo es :

1

2b−r−1 ≤ 1

2ulp ≤ b

2b−r−1.

Un error de redondeo estará siempre mayorado por 12b−r (precisión

maquina �).



Flotantes : calcular diferencias

Cuidado al calcular diferencias, en particular con magnitud muydiferentes. Ejemplo: 2.15× 1012 − 1.25× 10−5 :

Usar mas d́ıgitos y luego redondear :

x = 2.15× 1012y = 0.0000000000000000125× 1012

x − y = 2.1499999999999999875× 1012

Usar número de d́ıgitos fijos (y pues redondear ya desde elprincipio)

x = 2.15× 1012y = 0.00× 1012

x − y = 2.15× 1012

Shift del operando más pequeño.



Flotantes : operaciones aritmeticas

Las adiciones/substracciones se hacen :

Alineando todo sobre el número de exponente mayor (shift delos bits).

Aplicando operación aritmética sobre la mantisa.

Eventualmente re-alineando todo para normalizar.




Otro caso, 10.1− 9.93

x = 1.01× 101y = 0.99× 101

x − y = 0.02× 101

Error : 30 ulps ! (y cada d́ıgito es incorrecto !)




El problema es el de la cancelación : la diferencia puede eliminarcantidad de digits confiables (los de pesos mas altos), dejando losque son los menos confiables, porque han sido contaminados poroperaciones de redondeo ! Efecto amplificador !




Error relativo en el peor de los casos :

(b−r − b−r−1)/b−r−1 = b − 1

Entonces el error absoluto puede ser de orden de magnitud tanelevado como el resultado !!! Puede ser útil añadir un d́ıgito aditivo(guard digit) para evitar esas situaciones (en este caso se muestraque el error relativo no puede ser mayor que 2�).




Considerar las fórmulas de las ráıces de polinomios de segundo grado

−b +√

b2 − 4ac2

,−b −

√b2 − 4ac2

Si a, b, c son redondeados y que ademas b2 >> ac , tenemosproblemas !Usar re-escritura de las formulas :

2c

−b −√

b2 − 4ac,

2c

−b +√

b2 − 4ac

Por cada caso (b > 0 o b < 0) hay una fórmula mas estable que laotra !




Qué es mejor : calcular x2 − y 2 o (x − y)(x + y) ? Por qué ?



Flotantes : en regla general

Si sabemos que va a haber problemas de cancelación, analizar elmétodo/algoritmo que usamos para eventualmente evitarlo(factorización. . . ). El orden de las operaciones importa ! Perdemosla asociatividad de las operaciones (adición/substracción), ladistributividad de la multiplicación sobre la adición.



Referencias

V. Lefèvre y P. Zimmermann, Arithmétique flottante, Rapportde recherches INRIA N.5105

The GNU C Library, online manual

David Goldberg.What every computer scientist should know about floating-pointarithmetic. ACM Computing Surveys, 23(1):5–48, March 1991.


http://www.gnu.org/software/libc/manual/html_mono/libc.htmlhttp://www.validlab.com/goldberg/paper.ps

Presentación de la claseLos datos en C y en la máquina

programación : c (1)aplicaciones.cimat.mx/.../files/jbhayet/files/clase1_0.pdf · 2018. 10....

Documents