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 :

le calculs des nombres de la suite de Fibonacci (cf. vidéo exercice 1)
un développement limité (cf. vidéo exercice 2)
le calcul des racines d'une équation du second degré (cf. vidéo exercice 2)

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 :

$fib(0) = 0$
$fib(1) = 1$
$fib(n) = f ib(n − 1) + f ib(n − 2)$

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

une première version calculant avec des entiers (fib_int)
une seconde avec des réels 32 bits (fib_flt)
et enfin une troisième avec des réels 64 bits (fib_dbl)

CODE
fib.cpp

// ===================================================================
// Program: fib.c
// Date: July 2020
// Author: Jean-Michel Richer
// Email: jean-michel.richer@univ-angers.fr
// ===================================================================
// Description:
//   This program computes the fibonacci numbers using integers,
//   float or double.
//
//   It is intended to be translated in 32 bits x86 assembly
//   language.
// ===================================================================
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdint>
using namespace std;
 
typedef int32_t i32;
typedef int64_t i64;
typedef float    f32;
typedef double   f64;
 
// Global variable
int N = 1;
 
/**
 * Generic function that computes fibonacci(n)
 * @param n integer
 * @return Fibonacci(n)
 */
template<class T>
T fib(int n) {
    T *array = new T [ n+1 ];
    
    array[0] = 0;
    array[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        array[i] = array[ i-1 ] + array[ i-2 ];
    }
    
    T v = array[ n ];
    
    delete [] array;
    
    return v;
}
 
string list[] = {
"0",
"1",
"1",
"2",
"3",
"5",
"8",
"13",
"21",
"34",
"55",
"89",
"144",
"233",
"377",
"610",
"987",
"1597",
"2584",
"4181",
"6765",
"10946",
"17711",
"28657",
"46368",
"75025",
"121393",
"196418",
"317811",
"514229",
"832040",
"1346269",
"2178309",
"3524578",
"5702887",
"9227465",
"14930352",
"24157817",
"39088169",
"63245986",
"102334155",
"165580141",
"267914296",
"433494437",
"701408733",
"1134903170",
"1836311903",
"2971215073",
"4807526976",
"7778742049",
"12586269025",
"20365011074",
"32951280099",
"53316291173",
"86267571272",
"139583862445",
"225851433717",
"365435296162",
"591286729879",
"956722026041",
"1548008755920",
"2504730781961",
"4052739537881",
"6557470319842",
"10610209857723",
"17167680177565",
"27777890035288",
"44945570212853",
"72723460248141",
"117669030460994",
"190392490709135",
"308061521170129",
"498454011879264",
"806515533049393",
"1304969544928657",
"2111485077978050",
"3416454622906707",
"5527939700884757",
"8944394323791464",
"14472334024676221",
"23416728348467685",
"37889062373143906",
"61305790721611591",
"99194853094755497",
"160500643816367088",
"259695496911122585",
"420196140727489673",
"679891637638612258",
"1100087778366101931",
"1779979416004714189",
"2880067194370816120",
"4660046610375530309",
"7540113804746346429",
"12200160415121876738",
"19740274219868223167",
"31940434634990099905",
"51680708854858323072",
"83621143489848422977",
"135301852344706746049",
"218922995834555169026",
"354224848179261915075",
""
};
 
 
/**
 * main function
 */
int main(int argc, char *argv[]) {
    
    if (argc > 1) N = atoi( argv[1] );
    if (N <= 1) N = 1;
    if (N > 100) N = 100;
    
    std::cout.setf(ios::fixed);
    std::cout.setf(ios::showpoint);
    std::cout.precision(1);
 
    i32 fibi;
    i64 fibl;
    f32 fibf;
    f64 fibd;
    
    // compute and print n and fibonacci(n)
    for (int i = 1; i <= N; ++i) {
        fibi = fib<i32>(i);
        fibl = fib<i64>(i);
        fibf = fib<f32>(i);
        fibd = fib<f64>(i);
        
        cout << "i=" << setw(2) << i << " ";
        
        ostringstream ioss, loss, foss, doss;
        ioss << fibi;
        loss << fibl;
        foss << fixed << setprecision(0) << fibf;
        doss << fixed << setprecision(0) << fibd;
 
        cout << setw(22) << ioss.str() << " ";
        cout << setw(22) << loss.str() << " ";
        cout << setw(22) << fixed << setprecision(0) << foss.str() << " ";
        cout << setw(22) << fixed << setprecision(0) << doss.str() << " ";
                
        if (ioss.str() != list[i]) { 
            cout << " I ";
        }
        
        if (loss.str() != list[i]) { 
            cout << " L ";
        }
 
        if (foss.str() != list[i]) {
            cout << " F ";
        }
        
        if (doss.str() != list[i]) {
            cout << " D ";
        }
        
        cout << " " << list[i];
        cout << endl;
    }   
    
    return EXIT_SUCCESS;
}
 

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 ?

Termes de la suite de Fibonacci
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

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 :

CODE
limited_dev.c

// ==================================================================
// Program : limited_dev.c
// Date : October 2020
// Author: Jean-Michel RICHER
// Email : jean-michel.richer@univ-angers.fr
// ==================================================================
// Description : calcul du développement limité de 1/(1-x) quand
//  x est proche de 0. 
//   1/(1-x) = 1 + x + x^2 + x^3 + ... + x^N
//Prendre par exemple x=0.2 et N = 9.
// ==================================================================
#include <stdio.h>
#include <stdlib.h>
 
float x = 0.2;
int N = 8;
 
/**
 * calcul de x^n
 */
float puissance(float x, int n) {
   float result = 1;
   while (n > 0) {
      result *= x; 
      --n;
   }
   return result;
}
 
/**
 * Fonction principale
 */
int main(int argc, char *argv[]) {
    if (argc > 1) N = atoi( argv[1] );
    if (argc > 2) x = atof( argv[2] );
    
    float sum = 1.0;
    for (int i = 1; i <= N; ++i) {
        sum += puissance(x, i);
    } 
    
    printf("sum=%f\n", sum);
    
    return EXIT_SUCCESS;
}
 
 

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 :

$x_1 = (-b + √Δ)/{2a}$
$x_2 = (-b - √Δ)/{2a}$

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 :

CODE
roots_poly.c

// ==================================================================
// Program : roots_poly.c
// Date : October 2020
// Author: Jean-Michel RICHER
// Email : jean-michel.richer@univ-angers.fr
// ==================================================================
// Description : calcul des racines de l'équation ax^2 + bx + c = 0
// ==================================================================
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
float a = 1.0;
float b = 2.0;
float c = 1.0;
float delta, x1, x2;
 
/** 
 * Fonction principale
 */
int main(int argc, char *argv[]) {
    if (argc > 1) a = atof( argv[1] );
    if (argc > 2) b = atof( argv[2] );
    if (argc > 3) c = atof( argv[3] );
    
    delta = b*b - 4*a*c;
 
    if (delta < 0.0) {
        printf("pas de solution dans R\n");
    } else {
        x1 = (-b + sqrt(delta))/(2*a);
        x2 = (-b - sqrt(delta))/(2*a);
        printf("racines %g et %g\n", x1, x2);
        printf("(x + %g)*(x + %g) = %g x^2 + %g x + %g\n", -x1, -x2, a, b, c);
    }
    return EXIT_SUCCESS;
}
 
 

Page de Jean-Michel Richer

4. TP 4Calculs avec entiers et réels

4.1. Suite de Fibonacci

4.2. Développement limité

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

4. TP 4
Calculs avec entiers et réels