4. TP 4
Calculs avec entiers et réels

Dans ce TP nous abordons les calculs avec des nombres entiers et des nombres réels au travers de trois exemples :

4.1. Suite de Fibonacci

Ecrire un programme assembleur (fib_nasm.asm) qui permet de calculer les valeurs de la suite de Fibonacci pour $n$ dans l'intervalle [1, 60] de façon non récursive. On rappelle que :

On utilisera la FPU pour réaliser les calculs sur les réels. Donnez trois versions de la fonction :

  1. // ===================================================================
  2. // Program: fib.c
  3. // Date: July 2020
  4. // Author: Jean-Michel Richer
  5. // Email: jean-michel.richer@univ-angers.fr
  6. // ===================================================================
  7. // Description:
  8. //   This program computes the fibonacci numbers using integers,
  9. //   float or double.
  10. //
  11. //   It is intended to be translated in 32 bits x86 assembly
  12. //   language.
  13. // ===================================================================
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <sstream>
  17. #include <cstdint>
  18. using namespace std;
  19.  
  20. typedef int32_t i32;
  21. typedef int64_t i64;
  22. typedef float    f32;
  23. typedef double   f64;
  24.  
  25. // Global variable
  26. int N = 1;
  27.  
  28. /**
  29.  * Generic function that computes fibonacci(n)
  30.  * @param n integer
  31.  * @return Fibonacci(n)
  32.  */
  33. template<class T>
  34. T fib(int n) {
  35.     T *array = new T [ n+1 ];
  36.    
  37.     array[0] = 0;
  38.     array[1] = 1;
  39.    
  40.     for (int i = 2; i <= n; ++i) {
  41.         array[i] = array[ i-1 ] + array[ i-2 ];
  42.     }
  43.    
  44.     T v = array[ n ];
  45.    
  46.     delete [] array;
  47.    
  48.     return v;
  49. }
  50.  
  51. string list[] = {
  52. "0",
  53. "1",
  54. "1",
  55. "2",
  56. "3",
  57. "5",
  58. "8",
  59. "13",
  60. "21",
  61. "34",
  62. "55",
  63. "89",
  64. "144",
  65. "233",
  66. "377",
  67. "610",
  68. "987",
  69. "1597",
  70. "2584",
  71. "4181",
  72. "6765",
  73. "10946",
  74. "17711",
  75. "28657",
  76. "46368",
  77. "75025",
  78. "121393",
  79. "196418",
  80. "317811",
  81. "514229",
  82. "832040",
  83. "1346269",
  84. "2178309",
  85. "3524578",
  86. "5702887",
  87. "9227465",
  88. "14930352",
  89. "24157817",
  90. "39088169",
  91. "63245986",
  92. "102334155",
  93. "165580141",
  94. "267914296",
  95. "433494437",
  96. "701408733",
  97. "1134903170",
  98. "1836311903",
  99. "2971215073",
  100. "4807526976",
  101. "7778742049",
  102. "12586269025",
  103. "20365011074",
  104. "32951280099",
  105. "53316291173",
  106. "86267571272",
  107. "139583862445",
  108. "225851433717",
  109. "365435296162",
  110. "591286729879",
  111. "956722026041",
  112. "1548008755920",
  113. "2504730781961",
  114. "4052739537881",
  115. "6557470319842",
  116. "10610209857723",
  117. "17167680177565",
  118. "27777890035288",
  119. "44945570212853",
  120. "72723460248141",
  121. "117669030460994",
  122. "190392490709135",
  123. "308061521170129",
  124. "498454011879264",
  125. "806515533049393",
  126. "1304969544928657",
  127. "2111485077978050",
  128. "3416454622906707",
  129. "5527939700884757",
  130. "8944394323791464",
  131. "14472334024676221",
  132. "23416728348467685",
  133. "37889062373143906",
  134. "61305790721611591",
  135. "99194853094755497",
  136. "160500643816367088",
  137. "259695496911122585",
  138. "420196140727489673",
  139. "679891637638612258",
  140. "1100087778366101931",
  141. "1779979416004714189",
  142. "2880067194370816120",
  143. "4660046610375530309",
  144. "7540113804746346429",
  145. "12200160415121876738",
  146. "19740274219868223167",
  147. "31940434634990099905",
  148. "51680708854858323072",
  149. "83621143489848422977",
  150. "135301852344706746049",
  151. "218922995834555169026",
  152. "354224848179261915075",
  153. ""
  154. };
  155.  
  156.  
  157. /**
  158.  * main function
  159.  */
  160. int main(int argc, char *argv[]) {
  161.    
  162.     if (argc > 1) N = atoi( argv[1] );
  163.     if (N <= 1) N = 1;
  164.     if (N > 100) N = 100;
  165.    
  166.     std::cout.setf(ios::fixed);
  167.     std::cout.setf(ios::showpoint);
  168.     std::cout.precision(1);
  169.  
  170.     i32 fibi;
  171.     i64 fibl;
  172.     f32 fibf;
  173.     f64 fibd;
  174.    
  175.     // compute and print n and fibonacci(n)
  176.     for (int i = 1; i <= N; ++i) {
  177.         fibi = fib<i32>(i);
  178.         fibl = fib<i64>(i);
  179.         fibf = fib<f32>(i);
  180.         fibd = fib<f64>(i);
  181.        
  182.         cout << "i=" << setw(2) << i << " ";
  183.        
  184.         ostringstream ioss, loss, foss, doss;
  185.         ioss << fibi;
  186.         loss << fibl;
  187.         foss << fixed << setprecision(0) << fibf;
  188.         doss << fixed << setprecision(0) << fibd;
  189.  
  190.         cout << setw(22) << ioss.str() << " ";
  191.         cout << setw(22) << loss.str() << " ";
  192.         cout << setw(22) << fixed << setprecision(0) << foss.str() << " ";
  193.         cout << setw(22) << fixed << setprecision(0) << doss.str() << " ";
  194.                
  195.         if (ioss.str() != list[i]) {
  196.             cout << " I ";
  197.         }
  198.        
  199.         if (loss.str() != list[i]) {
  200.             cout << " L ";
  201.         }
  202.  
  203.         if (foss.str() != list[i]) {
  204.             cout << " F ";
  205.         }
  206.        
  207.         if (doss.str() != list[i]) {
  208.             cout << " D ";
  209.         }
  210.        
  211.         cout << " " << list[i];
  212.         cout << endl;
  213.     }  
  214.    
  215.     return EXIT_SUCCESS;
  216. }
  217.  

Exercice 4.1

Pour quelle valeur de $n$ les entiers ne sont-ils plus suffisants pour obtenir un résultat correct ? même question avec les réels simple et double précision ?

 n   Fibonacci(n) 
 F 29   514_229 
 F 30   832_040 
 F 31   1_346_269 
 F 32   2_178_309 
 F 33   3_524_578 
 F 34   5_702_887 
 F 35   9_227_465 
 F 36   14_930_352 
 F 37   24_157_817 
 F 38   39_088_169 
 F 39   63_245_986 
 F 40   102_334_155 
 F 41   165_580_141 
 F 42   267_914_296 
 F 43   433_494_437 
 F 44   701_408_733 
 F 45   1_134_903_170 
 F 46   1_836_311_903 
 F 47   2_971_215_073 
 F 48   4_807_526_976 
 F 49   7_778_742_049 
 F 50   12_586_269_025 
 F 51   20_365_011_074 
 F 52   32_951_280_099 
 F 53   53_316_291_173 
 F 54   86_267_571_272 
 F 55   139_583_862_445 
 F 56   225_851_433_717 
 F 57   365_435_296_162 
 F 58   591_286_729_879 
 F 59   956_722_026_041 
 F 60   1_548_008_755_920 
 F 61   2_504_730_781_961 
 F 62   4_052_739_537_881 
 ...   ... 
 F_87   679_891_637_638_612_258 
 F_88   1_100_087_778_366_101_931 
 F_89   1_779_979_416_004_714_189 
 F_90   2_880_067_194_370_816_120 
 F_91   4_660_046_610_375_530_309 
 F_92   7_540_113_804_746_346_429 
 F_93   12_200_160_415_121_876_738 
 F_94   19_740_274_219_868_223_167 
 F_95   31_940_434_634_990_099_905 
 F_96   51_680_708_854_858_323_072 
 F_97   83_621_143_489_848_422_977 
 F_98   135_301_852_344_706_746_049 
Termes de la suite de Fibonacci

4.2. Développement limité

On rappelle qu'en mathématiques, un développement limité d'une fonction en un point est une approximation polynomiale de cette fonction au voisinage de ce point.

Ecrire un programme assembleur (limited_dev_nasm.asm) qui calcule l'expression suivante sous forme d’un développement limité :

$$ 1/(1-x) = 1 + x + x^2 + x^3 + ... + x^n $$

Cette formule fonctionne lorsque $x$ est proche de 0, on pourra essayer avec $x = 0.2$ par exemple et déterminer à partir de quelle valeur de $n$ on peut s'arrêter car $n$ ne modifie plus la précision du calcul.

Voici à qui correspond le code à traduire :

  1. // ==================================================================
  2. // Program : limited_dev.c
  3. // Date : October 2020
  4. // Author: Jean-Michel RICHER
  5. // Email : jean-michel.richer@univ-angers.fr
  6. // ==================================================================
  7. // Description : calcul du développement limité de 1/(1-x) quand
  8. //  x est proche de 0.
  9. //   1/(1-x) = 1 + x + x^2 + x^3 + ... + x^N
  10. //Prendre par exemple x=0.2 et N = 9.
  11. // ==================================================================
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14.  
  15. float x = 0.2;
  16. int N = 8;
  17.  
  18. /**
  19.  * calcul de x^n
  20.  */
  21. float puissance(float x, int n) {
  22.    float result = 1;
  23.    while (n > 0) {
  24.       result *= x;
  25.       --n;
  26.    }
  27.    return result;
  28. }
  29.  
  30. /**
  31.  * Fonction principale
  32.  */
  33. int main(int argc, char *argv[]) {
  34.     if (argc > 1) N = atoi( argv[1] );
  35.     if (argc > 2) x = atof( argv[2] );
  36.    
  37.     float sum = 1.0;
  38.     for (int i = 1; i <= N; ++i) {
  39.         sum += puissance(x, i);
  40.     }
  41.    
  42.     printf("sum=%f\n", sum);
  43.    
  44.     return EXIT_SUCCESS;
  45. }
  46.  
  47.  

4.3. Solutions d'un polynôme du second degré

Ecrire un programme assembleur (roots_poly_nasm.asm) qui permet de trouver les solutions à valeurs dans $R$ d'une équation du second degré $ax^2 + bx + c = 0$. On utilisera la FPU pour réaliser les calculs. On rappelle qu'il faut calculer le discriminant $Δ = b^2 − 4ac$, puis si $Δ ≥ 0$, on trouvera des solutions réelles :

On utilisera l'instruction fcomip st0, st1 afin de réaliser une comparaison entre $Δ$ et 0.

On rappelle que pour trouver ces formules, il suffit en fait de résoudre l'équation en l'écrivant $X^2 - K = 0$, avec $X = x + {b}/{2a}$.

On en déduit donc que $x = -{b}/{2a} ±√{K}$.

Voici le code C à traduire en assembleur :

  1. // ==================================================================
  2. // Program : roots_poly.c
  3. // Date : October 2020
  4. // Author: Jean-Michel RICHER
  5. // Email : jean-michel.richer@univ-angers.fr
  6. // ==================================================================
  7. // Description : calcul des racines de l'équation ax^2 + bx + c = 0
  8. // ==================================================================
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <math.h>
  12.  
  13. float a = 1.0;
  14. float b = 2.0;
  15. float c = 1.0;
  16. float delta, x1, x2;
  17.  
  18. /**
  19.  * Fonction principale
  20.  */
  21. int main(int argc, char *argv[]) {
  22.     if (argc > 1) a = atof( argv[1] );
  23.     if (argc > 2) b = atof( argv[2] );
  24.     if (argc > 3) c = atof( argv[3] );
  25.    
  26.     delta = b*b - 4*a*c;
  27.  
  28.     if (delta < 0.0) {
  29.         printf("pas de solution dans R\n");
  30.     } else {
  31.         x1 = (-b + sqrt(delta))/(2*a);
  32.         x2 = (-b - sqrt(delta))/(2*a);
  33.         printf("racines %g et %g\n", x1, x2);
  34.         printf("(x + %g)*(x + %g) = %g x^2 + %g x + %g\n", -x1, -x2, a, b, c);
  35.     }
  36.     return EXIT_SUCCESS;
  37. }
  38.  
  39.