Pile et récursivité

• sp est initialisé à 0x7FFFEFFC

Quelle est la valeur du registre sp au moment du ebreak ? (pour fib(3))

sp est de “retour” à sa valeur initiale, ici 0x7FFFEFFC. Les routines ont la responsabilité (ABI RISC-V) de rendre le pointeur de pile dans l’état où ils l’ont trouvé.

Combien de fois la première instruction de la routine fib est exécutée ?

• fib(0) et fib(1) ne font pas d’appel
• pour n>1, fib(n) appelle récursivement fib(n-1) et fib(n-2)

On a donc 5 appels en tout pour fib(3):

fib(3)
|- fib(2)
|  |- fib(1)
|  \- fib(0)
\-fib(1)

Au moment du ebreak, quel est le contenu des 48 octets en mémoire à partir de l’adresse 0x7FFFEFCC ?

Cette zone mémoire est dans la partie “libre” de la pile, on y trouve les reliquats des cadres d’appels des appels de routines précédents: les octets ne sont pas remis à zéro, mais simplement écrasés par de nouvelles valeurs.

Utilisez RARS pour inspecter la mémoire et avoir le détail des octets.

Quelle est la valeur du registre sp au moment du ebreak ? (pour fib(10))

Pareil, la valeur de sp est “inchangée” entre avant et et après.

Quelle est la valeur minimale prise par sp lors l’exécution (récursive) de fib ?

fib(10) appelle fib(9), qui appelle fib(8) et ainsi de suite jusqu’à fib(1). On a donc au cas le plus profond 10 appels imbriqués, chaque appel consomme 24 octets.

Ce qui donne: 0x7FFFEFFC - 10*24 = 0x7FFFEF0C

Combien de fois la première instruction de la routine fib est exécutée en tout (extra) ?

On peut dessiner l’arbre d’appel comme pour fib(3) mais à fib(10) ça devient gros. On nomme nfib(n) le nombre d’appels de fib(n).

• Selon l’implémentation de fib
  • nfib(0) = 1
  • nfib(1) = 1
  • pour n>1, nfib(n) = 1 + nfib(n-1) + nfib(n-2)
• Théorème: pour n>=0, nfib(n) = 2 * fib(n+1) - 1

Preuve par induction:

• nfib(0)
  = 2 * fib(1) - 1 // par hypothèse d’induction
  = 2 * 1 - 1 // par la définition mathématique de fib
  = 1
  Hypothèse vérifiée pour le cas n=0
• nfib(1)
  = 2 * fib(2) - 1 // par hypothèse d’induction
  = 2 * 1 - 1 // par la définition mathématique de fib
  = 1
  Hypothèse vérifiée pour le cas n=1
• nfib(n+1)
  = 1 + nfib(n) + nfib(n-1) // par l’implémentation de fib
  = 1 + (2 * fib(n+1) - 1) + (2 * fib(n) - 1) // par hypothèse d’induction
  = 2 * (fib(n+1) + fib(n)) - 1 // factorisation et simplification
  = 2 * fib(n+2) - 1 // par la définition mathématique de fib
  Hypothèse vérifiée pour le cas n>1

On calcule nfib(10) pour avoir la réponse:

• nfib(10) = 2 * fib(11) - 1 = 2 * 89 - 1 = 177 // on est bien content de pas l’avoir dessiné à la main

Flottants

Les 2^4 = 16 valeurs de binary4

• 0 00 0 +0 (cas spécial zéro)
• 0 00 1 +0b0.1 * 2^0 = 0b0.1 = 0.5 (dénormalisé)
• 0 01 0 +0b1.0 * 2^0 = 0b1 = 1
• 0 01 1 +0b1.1 * 2^0 = 0b1.1 = 1.5
• 0 10 0 +0b1.0 * 2^1 = 0b10 = 2
• 0 10 1 +0b1.1 * 2^1 = 0b11 = 3
• 0 11 0 +inf (cas spécial infini)
• 0 11 1 nan (cas spécial nan)
• 1 00 0 -0 (cas spécial zéro)
• 1 00 1 -0b0.1 * 2^0 = -0.5 (dénormalisé)
• 1 01 0 -0b1.0 * 2^0 = -1
• 1 01 1 -0b1.1 * 2^0 = -1.5
• 1 10 0 -0b1.0 * 2^1 = -2
• 1 10 1 -0b1.1 * 2^1 = -3
• 1 11 0 -inf (cas spécial infini)
• 1 11 1 nan (cas spécial nan)

Les valeurs

• -0.667 -> -0b0.101… arrondi au plus proche à -0b0.1 = -0.5, donc 1001
• 7/4 -> 0b1.11 équidistant entre 0b1.1 (1.5) et 0b10.0 (2), celui qui a le dernier chiffre à 0 gagne (le “pair” gagne), on prend donc 2, donc 0100 en binary4.
• 2.5 -> 0b10.1 équidistant entre 0b10 (2) et 0b11 (3), celui qui a le dernier chiffre à 0 gagne (le “pair” gagne), on prend donc 2 à nouveau, donc 0100 en binary4.
• pi -> 3.145, 0b11 (3) est plus proche que 0b100 (4), on prend 0b11, donc 0101: note on est à la frontière entre le plus grand nombre représentable et l’infini.

Plus de détails

Tous les nombres de 0 à 4 (inclus) par pas de 0.125. Cela peut aider à visualiser la droite (verticale ici) des nombres (mais si ça vous mélange, ignorez le)

0     = 0b000.000  |X: +zéro (0000)
0.125 = 0b000.001  |X
0.25  = 0b000.010  |X (équidistant, 0 gagne)
0.375 = 0b000.011  | X
0.5   = 0b000.100  | X: 0.5 (0001)
0.625 = 0b000.101  | X
0.75  = 0b000.110  |X (équidistant, 1 gagne)
0.875 = 0b000.111  |X
1     = 0b001.000  |X- 1 (0010)
1.125 = 0b001.001  |X
1.25  = 0b001.010  |X (équidistant, 1 gagne)
1.375 = 0b001.011  | X
1.5   = 0b001.100  | X: 1.5 (0011)
1.625 = 0b001.101  | X
1.75  = 0b001.110  |X (équidistant, 2 gagne)
1.875 = 0b001.111  |X
2     = 0b010.000  |X: 2 (0100)
2.125 = 0b010.001  |X
2.25  = 0b010.010  |X
2.375 = 0b010.011  |X
2.5   = 0b010.100  |X (équidistant, 2 gagne)
2.625 = 0b010.101  | X
2.75  = 0b010.110  | X
2.875 = 0b010.111  | X
3     = 0b011.000  | X: 3 (0101)
3.125 = 0b011.001  | X
3.25  = 0b011.010  | X
3.375 = 0b011.011  | X
3.5   = 0b011.100  |X: (équidistant avec 4, +inf gagne)
3.625 = 0b011.101  |X
3.75  = 0b011.110  |X
3.875 = 0b011.111  |X
4     = 0b100.000  |X
                   :X
                   :X
                   |X: +infini (0110)