TD 6 C++: références, static, Arithmétique 2048 bits

Rappels

• Page du Cours
• Procédure de rendu
• Pour vérifier le rendu de ce TD: test.sh

Exercice 1:

1. Complétez le fichier 1.1.cc avec l'implémentation des constructeurs de la classe Uint2048 ci-dessous (télécharger: 1.1.h) :

   using uint64 = unsigned long long;
   
   class Uint2048 {
    public:
     Uint2048();
     Uint2048(int x);
   
     bool operator<(Uint2048 other);
     Uint2048 operator+(Uint2048 other);
   
     void Print();
   
    private:
     uint64 u_[32];
   };

   Vérifiez avec:

   rm 1.tar.gz; wget --no-cache http://fabien.viger.free.fr/cpp/td6/1.tar.gz
   tar xf 1.tar.gz
   make 1.1

   RENDU: 1.1.cc
   
   
2. Copiez 1.1.h et 1.1.cc dans 1.2.h et 1.2.cc (n'oubliez pas de changer le #include "1.1.h"), et ajoutez un opérateur de comparaison <.
   Vous pourrez notamment vous inspirer de l'opérateur + déjà fourni dans la classe.
   
   Test: make 1.2
   
   RENDUS: 1.2.h et 1.2.cc
   
   
3. Copiez 1.2.h et 1.2.cc dans 1.3.h et 1.3.cc et ajoutez tous les mot-clés const qui sont sensés.
   
   Test: make 1.3
   
   Ensuite, essayez de passer des arguments par référence au lieu de copie. Quel est l'impact sur le temps de calcul (quand on fait make 1.3)?
   
   RENDU: 1.3.h, 1.3.cc
   
   
4. On veut maintenant comptabiliser le nombre total d'additions efféctuées dans l'ensemble des classes Uint2048 par notre programme (pour debugger, par exemple).
   Comment faire? Copiez 1.3.h et 1.3.cc dans 1.4.h et 1.4.cc et ajoutez une fonction NumAdditions qui renverra ce nombre.
   Indice: static
   
   Cette fonction peut-elle être const? Pourquoi?
   
   Test: make 1.4
   
   RENDUS: 1.4.h, 1.4.cc
   
   
5. Copiez tout dans 1.5.h et 1.5.cc et ajoutez et implémentez l'opérateur - (soustraction).
   Vous pourrez vous inspirer du +, mais attention c'est un peu plus compliqué.
   
   Test: make 1.5
   
   RENDUS: 1.5.h, 1.5.cc
   
   
6. (*) Copiez tout dans 1.6.h et 1.6.cc et ajoutez et implémentez l'opérateur * (multiplication), qui devra marcher en O(2048²).
   Notamment, l'algo naïf suivant est beaucoup trop lent pour calculer a * b. Trouvez mieux!

   Uint2048 result(0);
   Uint2048 one(1);
   Uint2048 counter(0);
   while (counter < a) {
     result = result + b;
     counter = counter + one;
   }
   return result;

   Test: make 1.6
   
   RENDUS: 1.6.h, 1.6.cc
   
   
7. (***) Copiez tout dans 1.7.h et 1.7.cc et ajoutez et implémentez l'opérateur / (division entière). En O(2048²) également.
   
   Test: make 1.7
   
   RENDUS: 1.7.h, 1.7.cc
   
   

Exercice 2:

1. Simulez l'execution du code suivant dans votre tête. Quel sera l'affichage?
   
   
   
   RENDU: 2.1.txt qui contiendra 3 lignes, suivant le format:

   5,6,7
   8,9,10
   11,12,13

   en remplaçant, bien sûr, les valeurs des entiers!
   
   Vérifiez avec:

   rm 2.1.test.sh; wget --no-cache http://fabien.viger.free.fr/cpp/td6/2.1.test.sh
   bash 2.1.test.sh