cours_6.md

title: "Récursivité"
date: "2023-10-31"

Nombres à virgule (1/3)

Comment manipuler des nombres à virgule?

$$0.1 + 0.2 = 0.3.$$

Facile non?

. . .

Et ça?

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    float a = atof(argv[1]);
    float b = atof(argv[2]);
    printf("%.10f\n", (double)(a + b));
}

. . .

Que se passe-t-il donc?

Nombres à virgule (2/3)

Nombres à virgule fixe

+-------+-------+-------+-------+-----+----------+----------+----------+----------+ |

$2^3$

|

$2^2$

|

$2^1$

|

$2^0$

| . |

$2^{-1}$

|

$2^{-2}$

|

$2^{-3}$

|

$2^{-4}$

| +-------+-------+-------+-------+-----+----------+----------+----------+----------+ | 1 | 0 | 1 | 0 | . | 0 | 1 | 0 | 1 | +-------+-------+-------+-------+-----+----------+----------+----------+----------+

Qu'est-ce ça donne en décimal?

. . .

$$2^3+2^1+\frac{1}{2^2}+\frac{1}{2^4} = 8+2+0.5+0.0625=10.5625.$$

Limites de cette représentation?

. . .

• Tous les nombres > 16.
• Tous les nombres < 0.0625.
• Tous les nombres dont la décimale est pas un multiple de 0.0625.

Nombres à virgule (3/3)

Nombres à virgule fixe

• Nombres de
  $0=0000.0000$
  à
  15.9375=1111.1111
  .
• Beaucoup de "trous" (au moins
  0.0625
  ) entre deux nombres.

Solution partielle?

. . .

• Rajouter des bits.
• Bouger la virgule.

Nombres à virgule flottante (1/2)

Notation scientifique

• Les nombres sont représentés en terme:
  • Une mantisse
  • Une base
  • Un exposant

\underbrace{22.1214}_{\mbox{nombre}}=\underbrace{221214}_{\mbox{mantisse}}\cdot {\underbrace{10}_{\mbox{base}}}{\overbrace{^{-4}}^{\mbox{exp.}}},

. . .

On peut donc séparer la représentation en 2:

• La mantisse
• L'exposant

Nombres à virgule flottante (2/2)

Quel est l'avantage?

. . .

On peut représenter des nombres sur énormément d'ordres de grandeur avec un nombre de bits fixés.

Différence fondamentale avec la virgule fixe?

. . .

La précision des nombres est variable:

• On a uniquement un nombre de chiffres significatifs.
  123456\cdot 10^{23}+ 123456\cdot 10^{-23}.

Quel inconvénient y a-t-il?

. . .

Ce mélange d'échelles entraîne un perte de précision.

Nombres à virgule flottante simple précision (1/4)

Aussi appelés IEEE 754 single-precision binary floating point.

Spécification

• 1 bit de signe,
• 8 bits d'exposant,
• 23 bits de mantisse.

(-1)^{b_{31}}\cdot 2^{(b_{30}b_{29}\dots b_{23})_{2}-127}\cdot (1.b_{22}b_{21}\dots b_{0})_{2},

Calculer la valeur décimale du nombre ci-dessus

Nombres à virgule flottante simple précision (2/4)

. . .

\begin{align} \mbox{exposant}&=\sum_{i=0}^7 b_{23+i}2^i=2^2+2^3+2^4+2^5+2^6=124-127,\ \mbox{mantisse}&=1+\sum_{i=1}^{23}b_{23-i}2^{-i}=1+2^{-2}=1.25,\ &\Rightarrow (-1)^0\cdot 2^{-3}\cdot 1.25=0.15625 \end{align}

Nombres à virgule flottante simple précision (3/4)

Quel nombre ne peux pas être vraiment représenté?

. . .

Zéro: exception pour l'exposant

• Si l'exposant est 00000000 (zéro)
  (-1)^{\mbox{sign}}\cdot 2^{-126}\cdot 0.\mbox{mantisse},
• Sinon si l'exposant est 00000001 à 11111110
  \mbox{valeur normale},
• Sinon 11111111 donne NaN.

Nombres à virgule flottante simple précision (4/4)

Quels sont les plus petits/grands nombres positifs représentables?

. . .

\begin{align} 0\ 0\dots0\ 0\dots01&=2^{-126}\cdot 2^{-23}=1.4...\cdot 10^{-45},\ 0\ 1\dots10\ 1\dots1&=2^{127}\cdot (2-2^{-23})=3.4...\cdot 10^{38}. \end{align}

Combien de chiffres significatifs en décimal?

. . .

• 24 bits (
  23 + 1
  ) sont utiles pour la mantisse, soit
  2^{24}-1
  :
  • La mantisse fait
    \sim2^{24}\sim 10^7
    ,
  • Ou encore
    \sim \log_{10}(2^{24})\sim 7
    .
• Environ sept chiffres significatifs.

Nombres à virgule flottante double précision (64bits)

Spécification

• 1 bit de signe,
• 11 bits d'exposant,
• 52 bits de mantisse.

. . .

Combien de chiffres significatifs?

• La mantisse fait
  \sim 2^{53}\sim10^{16}
  ,
• Ou encore
  \sim \log_{10}(2^{53})\sim 16
  ,
• Environ seize chiffres significatifs.

Plus petit/plus grand nombre représentable?

. . .

• Plus petite mantisse et exposant:
  \sim 2^{-52}\cdot 2^{-1022}\sim 4\cdot 10^{-324}
  ,
• Plus grande mantisse et exposant:
  \sim 2\cdot 2^{1023}\sim \cdot 1.8\cdot 10^{308}
  .

Précision finie (1/3)

Erreur de représentation

• Les nombres réels ont potentiellement un nombre infini de décimales
  • 1/3=0.\overline{3}
    ,
  • \pi=3.1415926535...
    .
• Les nombres à virgule flottante peuvent en représenter qu'un nombre fini.
  • 1/3\cong 0.33333
    , erreur
    0.00000\overline{3}
    .
  • \pi\cong3.14159
    , erreur
    0.0000026535...
    .

On rencontre donc des erreurs de représentation ou erreurs d'arrondi.

. . .

Et quand on calcule?

• Avec deux chiffres significatifs \begin{align} &8.9+(0.02+0.04)=8.96=9.0,\ &(8.9+0.02)+0.04=8.9+0.04=8.9. \end{align}

. . .

Même pas associatif!

Précision finie (2/3)

Erreur de représentation virgule flottante

(1.2)_{10} = 1.\overline{0011}\cdot 2^0\Rightarrow 0\ 01111111\ 00110011001100110011010.

Erreur d'arrondi dans les deux derniers bits et tout ceux qui viennent ensuite

\varepsilon_2 = (00000000000000000000011)_2.

Ou en décimal

\varepsilon_{10} = 4.76837158203125\cdot 10^{-8}.

Précision finie (3/3)

Comment définir l'égalité de 2 nombres à virgule flottante?

. . .

Ou en d'autres termes, pour quel

\varepsilon>0

(appelé epsilon-machine) on a

1+\varepsilon = 1,

pour un nombre à virgule flottante?

. . .

Pour un float (32 bits) la différence est à

2^{-23}=1.19\cdot 10^{-7},

Soit la précision de la mantisse.

Comment le mesurer (par groupe)?

. . .

float eps = 1.0;
while ((float)1.0 + (float)0.5 * eps != (float)1.0) {
    eps = (float)0.5 * eps;
}
printf("eps = %g\n", eps);

Erreurs d'arrondi

Et jusqu'ici on a encore pas fait d'arithmétique!

Multiplication avec deux chiffres significatifs, décimal

(1.1)_{10}\cdot (1.1)_{10}=(1.21)_{10}=(1.2)_{10}.

En continuant ce petit jeu:

\underbrace{1.1\cdot 1.1\cdots 1.1}_{\mbox{10 fois}}=2.0.

Alors qu'en réalité

1.1^{10}=2.5937...

Soit une erreur de près de 1/5e!

. . .

Le même phénomène se produit (à plus petite échelle) avec les float ou double.

And now for something completely different

\Huge La récursivité

La factorielle: Code impératif

• Code impératif

int factorial(int n) {
    int f = 1;
    for (int i = 1; i < n; ++i) {
        f *= i;
    }
    return f;
}

Exemple de récursivité (1/2)

La factorielle

int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}

. . .

Que se passe-t-il quand on fait factorial(4)?

. . .

On empile les appels

+----------------+----------------+----------------+----------------+ | | | | factorial(1) | +----------------+----------------+----------------+----------------+ | | | factorial(2) | factorial(2) | +----------------+----------------+----------------+----------------+ | | factorial(3) | factorial(3) | factorial(3) | +----------------+----------------+----------------+----------------+ | factorial(4) | factorial(4) | factorial(4) | factorial(4) | +----------------+----------------+----------------+----------------+

Exemple de récursivité (2/2)

La factorielle

int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}

. . .

Que se passe-t-il quand on fait factorial(4)?

. . .

On dépile les calculs

+----------------+----------------+----------------+----------------+ | 1 | | | | +----------------+----------------+----------------+----------------+ | factorial(2) | 2 * 1 = 2 | | | +----------------+----------------+----------------+----------------+ | factorial(3) | factorial(3) | 3 * 2 = 6 | | +----------------+----------------+----------------+----------------+ | factorial(4) | factorial(4) | factorial(4) | 4 * 6 = 24 | +----------------+----------------+----------------+----------------+

La récursivité (1/4)

Formellement

• Une condition de récursivité - qui réduit les cas successifs vers...
• Une condition d'arrêt - qui retourne un résultat

Pour la factorielle, qui est qui?

int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}

La récursivité (2/4)

Formellement

• Une condition de récursivité - qui réduit les cas successifs vers...
• Une condition d'arrêt - qui retourne un résultat

Pour la factorielle, qui est qui?

int factorial(int n) {
    if (n > 1) { // Condition de récursivité
        return n * factorial(n - 1);
    } else {     // Condition d'arrêt
        return 1;
    }
}

La récursivité (3/4)

Exercice: trouver l'

\varepsilon

-machine pour un double

. . .

Rappelez-vous vous l'avez fait en style impératif plus tôt.

. . .

double epsilon_machine(double eps) {
    if (1.0 + eps != 1.0) {
        return epsilon_machine(eps / 2.0);
    } else {
        return eps;
    }
}

La récursivité (4/4)

\footnotesize

Exercice: que fait ce code récursif?

void recurse(int n) {
    printf("%d ", n % 2);
    if (n / 2 != 0) {
        recurse(n / 2);
    } else {
        printf("\n");
    }
}
recurse(13); 

. . .

recurse(13): n = 13, n % 2 = 1, n / 2 = 6,
    recurse(6): n = 6, n % 2 = 0, n / 2 = 3,
        recurse(3): n = 3, n % 2 = 1, n / 2 = 1,
            recurse(1): n = 1, n % 2 = 1, n / 2 = 0.

// affiche: 1 1 0 1

. . .

Affiche la représentation binaire d'un nombre!

Exercice: réusinage et récursivité (1/4)

Réusiner le code du PGCD avec une fonction récursive

Étudier l'exécution

42 = 27 * 1 + 15
27 = 15 * 1 + 12
15 = 12 * 1 + 3
12 = 3  * 4 + 0

Exercice: réusinage et récursivité (2/4)

Réusiner le code du PGCD avec une fonction récursive

Étudier l'exécution

42 = 27 * 1 + 15   |   PGCD(42, 27) 
27 = 15 * 1 + 12   |   PGCD(27, 15) 
15 = 12 * 1 +  3   |   PGCD(15, 12) 
12 =  3 * 4 +  0   |   PGCD(12,  3) 

Exercice: réusinage et récursivité (3/4)

Réusiner le code du PGCD avec une fonction récursive

Étudier l'exécution

42 = 27 * 1 + 15   |   PGCD(42, 27) 
27 = 15 * 1 + 12   |   PGCD(27, 15) 
15 = 12 * 1 +  3   |   PGCD(15, 12) 
12 =  3 * 4 +  0   |   PGCD(12,  3) 

Effectuer l'empilage - dépilage

. . .

PGCD(12,  3)    |     3
PGCD(15, 12)    |     3
PGCD(27, 15)    |     3
PGCD(42, 27)    |     3

Exercice: réusinage et récursivité (4/4)

Écrire le code

. . .

int pgcd(int n, int m) {
    if (n % m > 0) {
        return pgcd(m, n % m);
    } else {
        return m;
    }
}

La suite de Fibonacci (1/2)

Règle

\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2),\quad \mathrm{Fib}(0)=0,\quad \mathrm{Fib}(1)=1.

Exercice: écrire la fonction

\mathrm{Fib}

en récursif et impératif

. . .

En récursif (6 lignes)

int fib(int n) {
    if (n > 1) {
        return fib(n - 1) + fib(n - 2);
    } 
    return n;
}

La suite de Fibonacci (2/2)

Et en impératif (11 lignes)

int fib_imp(int n) {
    int fib0 = 1;
    int fib1 = 1;
    int fib  = n == 0 ? 0 : fib1;
    for (int i = 2; i < n; ++i) {
        fib  = fib0 + fib1;
        fib0 = fib1;
        fib1 = fib;
    }
    return fib;
}