Calculer sur des grands nombres

Dans l'article consacré à la classe ClockTime, il avait été mis en évidence la limite de fonctionnement de la fonction millis(), utilisée pour mesurer le temps écoulé, du fait que la valeur exprimée en millisecondes de celle-ci est codée sur un entier long non signé (sur 32 bits). De ce fait elle ne fonctionne que 49 j 17 h 8mn et 47,295 s (temps correspondant à la valeur 0xFFFFFFFF millisecondes). Si on veut mesurer le temps écoulé sur un intervalle de temps plus important, il faut procéder par une astuce consistant à programmer une fonction renvoyant une valeur entière non signée sur 48 bits, ce qui assure une durée de fonctionnement de 8919 ans.

Encore faudrait-il disposer d'un type de données permettant de manipuler des entiers sur 64 bits. Car, d'un façon inexpliquée, le type uint64_t ou long long ou double long ne fonctionne pas sur toutes les versions d'Arduino. Sans doute est-ce dû à la limite des registres du processeur utilisé.
Dans les applications scientifiques, en astronomie ou en physique des particules, il arrive souvent qu'il soit nécessaire d'effectuer des opérations sur des grands nombres dont la définition est très importante. Les types en virgule flottante comme float ou double permettent d'opérer sur des grand nombres, mais leur nombre de chiffres significatifs peut être insuffisants. D'autant que lors de calculs en série, les arrondis successifs cumulés peuvent introduire des erreurs importantes.

Dans cet article, il sera présenté une méthode pour implémenter le calcul arithmétique sur des grands nombres. Le principe de calcul est de coder les nombres dans une table d'entiers non signés. La taille du tableau est défini par la constante LENGTH. Dans l'exemple ci-dessous, avec la classe numérique DoubleLong,  le calcul sera effectué sur 64 bits (LENGTH = 4). Mais le code est facilement adaptable à des longueurs beaucoup plus grandes en fixant une valeurs plus élevée. Par exemple, en fixant la la valeur de LENGTH à 8, le calcul est effectué sur 128 bits.

Définition de la classe DoubleLong

Les objets DoubleLong sont des objets arithmétiques. Ce qui implique plusieurs concepts de programmation :

• Des opérations arithmétiques, comme l'addition, la soustraction, la multiplication et la division, doivent être possible. Ce qui implique l'implémentation des opérateurs +, -, *, / et %.
• Les objets doivent être interopérables avec les autre types entiers existants. La classe doit donc fournir un constructeur à partir du type uint32_t. 
• Les objets arithmétiques étant comparables, il faut prévoir les opérateurs == et !=. 
• Les objets arithmétiques étant ordonnés, il faut prévoir aussi les opérateurs <,<=, > et >=.

/* 1 */
#include <stdint.h>

class DoubleLong {
/* 2 */
  static const int LENGTH = 4;
/* 3 */
  uint16_t __value[LENGTH];
  uint8_t __carry;
  bool __error;

/* 4 */
  void __shiftL(uint8_t=0);
  void __shiftR(uint8_t=0);
/* 5 */
  static bool __isLower(const DoubleLong&, const DoubleLong&, bool);

  public:
/* 6 */
  DoubleLong(uint32_t, uint32_t);
  DoubleLong(uint32_t right = 0L) : DoubleLong(0L, right){ }

/* 7 */
  explicit operator uint32_t();
  operator double();
/* 8 */
  static void multiplication(DoubleLong*, DoubleLong, DoubleLong);
  static void division(DoubleLong*, DoubleLong, DoubleLong);
/* 9 */
  DoubleLong& operator +=(const DoubleLong&);
  DoubleLong& operator -=(const DoubleLong&);
  DoubleLong& operator *= (const DoubleLong&);
  DoubleLong& operator /= (const DoubleLong &);
/* 10 */
  friend DoubleLong operator + (const DoubleLong&, const DoubleLong&);
  friend DoubleLong operator - (const DoubleLong&, const DoubleLong&);
  friend DoubleLong operator * (const DoubleLong&, const DoubleLong&);
  friend DoubleLong operator / (const DoubleLong&, const DoubleLong&);
  friend DoubleLong operator % (const DoubleLong&, const DoubleLong&);
/* 11 */
  DoubleLong& operator++(void);
  DoubleLong& operator--(void);
/* 12 */
  const DoubleLong operator++(int);
  const DoubleLong operator--(int);
/* 13 */
  friend DoubleLong operator << (const DoubleLong&, uint8_t);
  friend DoubleLong operator >> (const DoubleLong&, uint8_t);
  DoubleLong& operator <<= (uint8_t kShift);
  DoubleLong& operator >>= (uint8_t kShift);
/* 14 */
  bool isNull();
  friend bool operator == (const DoubleLong&, const DoubleLong&);
  friend bool operator != (const DoubleLong&, const DoubleLong&);
  friend bool operator < (const DoubleLong&, const DoubleLong&);
  friend bool operator <= (const DoubleLong&, const DoubleLong&);
  friend bool operator > (const DoubleLong&, const DoubleLong&);
  friend bool operator >= (const DoubleLong&, const DoubleLong&);

/* 15 */
  bool overflow();
  bool error();
/* 16 */
  void trace(const char* label);
};

/* 17 */
const DoubleLong ZERO;

1. Définition de tous les types entiers standards. La classe DoubleLong utilise plusieurs type uintXX_t où XX définit le nombre de bits sur lequel l'entier est codé.
2. Définition de la constante de classe LENGTH. Cette valeur est la taille du tableau d'entier de 16 bits utilisé pour coder l'objet. Dans cet exemple, LENGTH vaut 4. Ce qui signifie que les entiers représentés par la classe DoubleLong  sont codés sur 64 bits.
3. Définition des attributs privés de la classe DoubleLong :
   • __value est un tableau d'entiers non signés codés sur 16 bits. La taille du tableau dépend de la valeur de la constante LENGTH (qui vaut 4 dans l'exemple). Les entiers contenus dans ce tableau constituent les chiffres significatifs de la valeur du tableau. L'ordre des entiers est en notation arabe. C'est à dire que le rang dans le tableau correspond à la place de l'entier de la droite vers la gauche. Autrement dit, la valeur numérique du tableau est :
     __value[0] + __value[1] * 2¹⁶ + __value[2] * 2³² + __value[3] * 2⁴⁸.
   • __carry est la retenue arithmétique. Lorsqu'un calcul arithmétique dépasse le nombre de bits possible, cela doit être identifiable. C'est le rôle de cet attribut. C'est une pratique courante en arithmétique : « 9 plus 8 égale 7 et je retiens 1 ». La retenue est une valeur arithmétique. Elle est propagée de la droite vers la gauche au fur et à mesure du calcul.
   • Certaines opérations arithmétiques, comme la division par 0, provoquent une erreur. Dans ce cas, la valeur informatique résultant de l'opération est erronée. __error est un booléen indiquant cette erreur lorsqu'elle se produit. Par défaut sa valeur est false (pas d'erreur).
4. Définition des méthodes de décalage. Ces méthodes sont utilisées pur la multiplication et la division de deux DoubleLong.
   • __shiftL() effectue un décalage de 1 bit vers la gauche dans le nombre représenté par DoubleLong. Le décalage est propagé de la droite vers la gauche dans le tableau __value via l'attribut __carry. Après cette opération, le bit situé le plus à droite dans __value[0] prend la valeur du paramètre passé (0 par défaut). Cela revient à effectuer une multiplication globale du nombre par 2. Si, avant l'opération le bit le plus à gauche de __value[LENGTH - 1] vaut 1, celui-ci est mis en retenue et __carry vaut 1 à la fin de l'opération.
   • __shiftR() effectue un décalage de 1 bit vers la droite dans le nombre représenté par DoubleLong. Le décalage est propagé de la gauche vers la droite dans le tableau __value via l'attribut __carry. Après cette opération, le bit situé le plus à gauche dans __value[LENGTH - 1] prend la valeur du paramètre passé (0 par défaut). Cela revient à effectuer une division globale du nombre par 2. Si, avant l'opération le bit le plus à droite de __value[0] vaut 1, celui-ci est mis en retenue et __carry vaut 1 à la fin de l'opération.
5. Le même algorithme est mis en oeuvre pour les opérateurs <, >, <= et >=. Cet algorithme est factorisé dans la méthode privée __isLower().
6. La classe DoubleLong possède deux constructeurs :
   • Le premier constructeur permet d'initialiser un DoubleLong à partir de deux entiers long non signés.
   • Le second permet d'initialiser un DoubleLong à partir d'un seul entier long non signé. Ce constructeur est indispensable pour interopérabilité avec les autres types entiers. Il invoque le précédent en passant comme 0 comme valeur haute. De plus il fourni une valeur par défaut pour pouvoir initialiser un DoubleLong à ZERO sans passer de paramètre.
7. Pour l'interopérabilité avec les autres types numériques, il est nécessaire de créer des opérateurs de conversion :
   • operator uint32_t() effectue la conversion implicite d'un DoubleLong en entier non signé sur 32 bits. Si le nombre est plus grand que 2³², le résultat est tronqué sur 32 bits.
     Attention aux opérandes mixtes. Par exemple si num1 est un DoubleLong et n2 est un long, pour l'expression num1 + n2 est ambiguë. En effet, la classe DoubleLong ne peut être insérée dans la hiérarchie des conversions implicites du C++ qui induit que l'opérateur calcule dans le référentiel le plus grand. Par exemple, lorsqu'une opérande est un long et l'autre un int, le compilateur effectue une conversion implicite du plus petit (int) vers le plus grand (long) et le calcul s'effectue dans le référentiel long. Ici, le compilateur ne sait pas s'il doit convertir num1 en long et effectuer le calcul dans le référentiel long, ou s'il doit convertir n2 en DoubleLong et effectuer le calcul dans le référentiel DoubleLong. Si on veut une addition de type long, il faudra écrire long(num1) + n2. Si on veut une addition de type DoubleLong, il faudra écrire num1 + DoubleLong(n2).
     A préciser que la conversion de DoubleLong vers les autres types d'entiers sur 16 ou 8 bits n'a pas vraiment de sens du fait de la nature même des objets de classe DoubleLong qui implémentent des grands nombres sur plus de 32 bits. 
   • operator double() effectue la conversion implicite d'un DoubleLong en virgule flottante double. Cela permet de passer des DoubleLong dans les fonctions mathématiques. Par exemple, si num1 est un DoubleLong, cela permet d'écrire sqrt(num1).
8. Deux méthodes statiques fournissent un résultat sur deux DoubleLong. Ces deux grands nombres sont retournés dans le tableau de deux DoubleLong dont l'adresse est passée en premier paramètre.  
• Le résultat de la  multiplication de deux nombre de 64 bits s'exprime sur 128 bits (2 x 64 bits). La méthode statique multiplication() effectue ce produit sur 128 bits. Le résultat est fourni dans un tableau de deux DoubleLong. Le premier indicé 0 est le produit tronqué dans le référentiel DoubleLong. Le second, indicé 1, est le DoubleLong correspondant aux 64 bits de poids fort des 128 bits du résultat.
• Le même algorithme est mis en oeuvre pour l'opérateur / (division entière) et l'opérateur % (reste de la division entière). Cet algorithme est factorisé dans le méthode statique division(). Les deux résultats sont fournis dans un tableau. Le premier, indicé 0 est le résultat de la division entière sur 64 bits. Le second, indicé 1, est le reste de la division entière sur 64 bits.

Le langage C++ permet la surcharge des opérateurs pour pouvoir être utilisés comme pour n'importe quel autre type de données numérique. Certains opérateurs sont surchargés en tant que méthodes membres de la classe DoubleLong. D'autres sont surchargés comme des fonctions (externes à la classe) et sont donc déclarées friend (amie) pour pouvoir avoir accès aux attributs privés de la classe. C'est le cas de la plupart des opérateurs dyadiques qui opèrent sur deux opérandes semblables sans les modifier.

9. Les opérateurs d'affectation reçoivent en paramètre l'opérande de droite par référence. Celle-ci est déclarée de type const DoubleLong&. Ils modifient l'opérande de gauche et en renvoie la référence en résultat pour pouvoir enchaîner les calculs dans des expressions. Ils sont donc déclarés comme méthodes membres de la classe DoubleLong&.
10. Les opérateurs arithmétiques opèrent sur deux opérandes sans les modifier. Celles-ci sont donc toutes les deux déclarées const DoubleLong&. Il sont déclarés comment des fonctions externes friend. Le résultat fourni est un nouvel objet de type DoubleLong.
11. Les opérateurs de pré-incrémentation et de pré-décrémentation modifient l'opérande qui est l'objet lui-même. Celui-ci est fourni en résultat après la modification. De ce fait, le résultat des ces opérateurs est une référence sur l'objet lui-même et est donc déclaré DoubleLong&. Ils ne prennent pas de paramètre. Ils sont déclarés comme méthodes membres de la classe. 
12. Les opérateurs  de post-incrémentation et de post-décrémentation modifient l'opérande qui est l'objet lui-même. Contrairement aux précédents, le résultat fourni est la valeur de l'objet avant la modification. De ce fait, il est déclaré const DoubleLong. Afin de les distinguer des précédent dans la syntaxe C++, on leur passe un paramètre anonyme (de type int) qui n'est pas exploité. Ils sont aussi déclarés comme méthodes membres de la classe.
13. Les opérateurs de décalage ne figurent ici qu'à titre d'exemple. Le paramètre passé, de type uint8_t, est le nombres de bits sur lequel porte le décalage. Ces opérateurs invoquent les méthodes privées __shiftL() et __shiftR(). 
14. Les opérateurs de comparaison comparent les deux opérandes sans les modifier. Elles sont donc déclarées  const DoubleLong&. Le résultat est de type bool (booléen). Ces opérateurs sont des fonctions externes friend.
15. Définition des accesseurs sur les attributs privés :
    • overflow() expose l'attribut privé __carry en lecture seule sous forme booléenne. La valeur est true si la dernière opération effectuée a provoqué un dépassement.
    • error() expose l'attribut privé __error en lecture seule. La valeur est true si la dernière opération effectuée a provoqué une erreur (division par 0 par exemple). Dans ce cas la valeur du nombre n'est pas significative.
16. La méthode trace() est utilisée pour déboguer la classe DoubleLong. En effet, les objets DoubleLong ne sont pas printables. Elle formate la valeur numérique en hexadécimal dans une chaîne de caractères quelle déverse sur le canal Série de l'Arduino. Le paramètre passé est le nom de  la valeur tracée. Cette méthode ne peut fonctionner que si le canal Série a été initialisé dans la fonction setup() du sketch (Serial.begin(9600);). 
17. La constante ZERO est un objet DoubleLong dont tous les bits sont à 0. 

Construction d'un DoubleLong

DoubleLong::DoubleLong(uint32_t left, uint32_t right) {
  this->__value[0] = right & 0x0000FFFF;
  this->__value[1] = right >> 16;
  this->__value[2] = left & 0x0000FFFF;
  this->__value[3] = left >> 16;
  this->__carry = 0;
  this->__error = false;
}

La classe DoubleLong, dans cet exemple, est implémentée sous la forme d'un tableau de 4 entiers non signés sur 16 bits (type uint16_t). Pour faciliter le codage et au vu de l'utilisation qui en sera faite dans ClockTime, le constructeur proposé ici permet d'initialiser un DoubleLong avec deux entiers long non signés sur 32 bits left (poids fort) et right (poids faible). Ce qui permet d'obtenir les quatre entiers du tableau en fractionnant les 32 bits en deux entiers de 16 bits pour obtenir __value[0], __value[1] à partir du paramètre right et __value[2], __value[3] à partir de left.

Pour l'interopérabilité avec les autres types d'entier, il est nécessaire de disposer d'un constructeur permettant d'initialiser un DoubleLong à partir de n'importe quel entier. Un seul constructeur suffit à partir d'un entier long non signé, car si on passe à ce constructeur l'un quelconque des autres types entier, la conversion implicite du plus petit vers le plus grand sera effectuée.  

DoubleLong(uint32_t right = 0L) : DoubleLong(0L, right){ }

Ce constructeur n'a pas besoin d'être implémenté dans le fichier DoubleLong.cpp. En effet, la déclaration ci-dessus est inscrite directement dans la définition de la classe DoubleLong. Celle-ci indique que ce constructeur avec un seul paramètre de type uint32_t invoque l'autre constructeur en considérant que le paramètre passé correspond au paramètre right, le paramètre left étant 0. Elle indique aussi que si aucun paramètre n'est passé au constructeur, le paramètre right lui aussi est nul.

Dans l'absolu, il faudrait aussi disposer d'un constructeur qui initialise un DoubleLong avec tableau d'entier uint16_t.

Problème de l'addition des grands nombres

L'addition suppose deux opérandes, donc deux nombres, dont on fait la somme pour obtenir un troisième nombre. Pour les grands nombres, c'est la même chose. C'est à dire que pour la classe DoubleLong, on part de deux instances num1 et num2 de cette classe pour en produire une troisième contenant la somme des précédentes.

Or chaque instance de la classe DoubleLong est implémentée sous la forme d'un tableau __value de 4 entiers de type uint16_t. La première solution qui vient à l'esprit est de construire le tableau du résultat en additionnant les entiers de même rang des opérandes. Concrètement, en effectuant une boucle dont le code ressemblerait à ce qui est ci-dessous :

for (int i = 0; i < LEFT, i++) {
   result.__value[i] = num1.__value[i] + num2.__value[i];
}

Malheureusement, cette solution ne va pas fonctionner. En effet, si lors d'une des quatre itération de cette boucle, le résultat de la somme des deux uint16_t dépasse 16 bits, le bit supplémentaire est purement et simplement ignoré. Autrement dit, en base 10, si on procédait de cette manière, 17 + 26 vaudrait 33 et non pas 43. En réalité, en primaire on apprend qu'il faut faire «7 et 6 font 3 et je retient 1, 1 et 2 font 3 plus la retenue qui font 4». Autrement dit, on procède chiffre par chiffre de la droite vers la gauche et propageant la retenue en cas de dépassement lors de l'addition de deux chiffres de même rang.

Pour la classe DoubleLong, il faut procéder de la même manière. Mais au lieu de d'effectuer les opérations en base 10, on va le faire en base 65536, chaque membre du tableau d'entiers correspondant à un chiffre dont la valeur peut être de 0 à 65535. Le problème étant de matérialiser la fameuse retenue. C'est pourquoi, rang par rang, la somme des deux entiers de 16 bits (uint16_t) s'effectue dans le référentiel de 32 bits (uint32_t) en convertissant le premier entier de 16 bits à 32 bits pour forcer l'opération sur 32 bits. Dans ce cas, la valeur __value[i] du résultat correspond à l'uint16_t de poids faible, l'uint16_t de poids fort contenant la fameuse retenue.

Code de l'opérateur +=

DoubleLong& DoubleLong::operator +=(const DoubleLong &num) {
  this->__carry = 0;
  uint32_t add;
  for (int i = 0; i < LENGTH; i++) {
    add = (uint32_t)this->__value[i] + num.__value[i] + this->__carry;
    this->__value[i] = add & 0x0000FFFF;
    this->__carry = (add & 0xFFFF0000) ? 1 : 0;
  }
  return *this;
}

L'opérateur += est un opérateur d'affectation qui possède deux opérandes. Ce qui permet d'écrire l'expression num1 += num2. Il  modifie à la première opérande, num1, en y ajoutant la seconde num2. A la fin de l'opération num1 vaut num1+num2. 

• Dans un premier temps, l'attribut __carry est initialisé à 0. 
• La boucle for effectue LENGTH itérations, LENGTH étant la taille du tableau d'entier __value. Pour DoubleLong, LENGTH vaut 4. Ce qui permet de gérer des nombres sur 64 bits. Avec LENGTH à 8, on gère avec le même algorithme une addition sur 128 bits.
• L'addition des deux entiers de 16 bits de rang i est rangée dans une variable temporaire add de 32 bits (uint32_t), déclarée avant la boucle for par soucis de performance. Pour que le calcul soit effectué sur 32 bits, this->__value[i] est converti en uint32_t.
• Le résultat est affecté à this->__value[i] en prenant les 16 bits de poids le plus faible de add.
• La retenue est affectée à this->__carry en testant la valeur des 16 bits de poids fort de add. Celle-ci est prise en compte dans l'addition de l'itération suivante.
• Le résultat de cette opération est une référence sur l'instance de l'opérande de gauche modifiée (return *this).

Code de l'opérateur +

DoubleLong operator + (const DoubleLong &num1, const DoubleLong &num2) {
  DoubleLong result(num1);
  return (result += num2);
}

L'opérateur + utilise le même algorithme que +=. Mais il y a quelques différences importantes à saisir :

• L'opérateur += ne reçoit qu'un seul paramètre qui est considéré comme l'opérande de droite, l'opérande de gauche étant l'instance sur laquelle il est invoqué. Alors que l'opérateur + reçoit deux paramètres correspondant respectivement aux opérandes de gauche et de droite.
• L'opérateur += modifie l'instance sur laquelle il est invoqué, qui est considérée comme l'opérande de gauche. Alors que l'opérateur + ne modifie aucune des deux opérandes qui lui sont passées en paramètres.
• Du fait qu'il modifie l'opérande de gauche, l'opérateur += est une méthode membre de la classe DoubleLong. Il est donc déclaré comme toute les méthodes avec DoubleLong::opérator +=. Alors que l'opérateur + est une fonction externe à la classe qui reçoit les deux opérandes gauche et droite qui ne doivent pas être modifiées. Elle est déclarée friend dans la définition de la classe afin de pouvoir accéder aux attributs privés de la classe. La déclaration de l'opérateur est operator + sans le préfixe DoubleLong::.
• Le résultat de l'opérateur += est l'instance elle-même sur laquelle il est invoqué après modification. De ce fait, le retour est déclaré comme une référence DoubleLong&. Alors que le résultat de l'opérateur + est une nouvelle instance contenant la somme des deux opérandes passées en paramètre. Le retour est donc déclaré DoubleLong par valeur, sans le &.

Ceci étant précisé, une fois le code de l'opérateur += testé et validé, on peut réutiliser celui-ci de la façon suivante :

• Création d'une copie result  de num1.
• Utilisation de l'opérateur += sur result en lui passant num2 comme opérande.
• Le résultat de l'opération est result.

Problème de la soustraction de deux grands nombres

La soustraction procède du même principe que l'addition. A savoir que l'on va procéder comme en base 10. Pour effectuer 32 - 16 en primaire, on ferai «6 ôté de 12 font 6 et je retient 1, 1 plus la retenue font 2, ôté de trois 3 font 1» ce qui donne 16. Autrement dit, on procède chiffre par chiffre de la droite vers la gauche et propageant la retenue en cas de dépassement lors de la soustraction de deux chiffres de même rang.

Pour la classe DoubleLong, il faut procéder de la même manière. Mais au lieu de d'effectuer les opérations en base 10, on va le faire, comme pour l'addition, en base 65536, chaque membre du tableau d'entiers correspondant à un chiffre dont la valeur peut être de 0 à 65535. Le problème étant de matérialiser la fameuse retenue. C'est pourquoi, rang par rang, la différence entre les deux entiers de 16 bits (uint16_t) s'effectue dans le référentiel de 32 bits (uint32_t) en convertissant le premier entier de 16 bits à 32 bits pour forcer l'opération sur 32 bits. Et, comme pour l'addition, la valeur __value[i] du résultat correspond à l'uint16_t de poids faible, l'uint16_t de poids fort contenant la fameuse retenue.

Code de l'opérateur -=

DoubleLong& DoubleLong::operator -= (const DoubleLong &num) {
  this->__carry = 0;
  uint32_t sub;
  for (int i = 0; i < LENGTH; i++) {
    sub = (uint32_t)this->__value[i] - num.__value[i] - this->__carry;
    this->__value[i] = sub & 0x0000FFFF;
    this->__carry = (sub & 0xFFFF0000) ? 1 : 0;
  }
  return *this;
}

L'opérateur -= est un opérateur d'affectation qui possède deux opérandes. Ce qui permet d'écrire l'expression num1 -= num2. Il  modifie à la première opérande, num1, en y ôtant la seconde num2. A la fin de l'opération num1 vaut num1-num2. 

• Dans un premier temps, l'attribut __carry est initialisé à 0. 
• La boucle for effectue LENGTH itérations, LENGTH étant la taille du tableau d'entier __value. 
• La soustraction des deux entiers de 16 bits de rang i est rangée dans une variable temporaire sub de 32 bits (uint32_t), déclarée avant la boucle for par soucis de performance. Pour que le calcul soit effectué sur 32 bits, this->__value[i] est converti en uint32_t.
• Le résultat est affecté à this->__value[i] en prenant les 16 bits de poids le plus faible de sub.
• La retenue est affectée à this->__carry en testant la valeur des 16 bits de poids fort de sub. Celle-ci est prise en compte dans l'addition de l'itération suivante.
• Le résultat de cette opération est une référence sur l'instance de l'opérande de gauche modifiée (return *this).

Code de l'opérateur -

DoubleLong operator - (const DoubleLong &num1, const DoubleLong &num2) {
  DoubleLong result(num1);
  return (result -= num2);
}

L'opérateur - utilise le même algorithme que -= en notant des distinctions comparables à celles indiquées entre le opérateur += et +. L'opérateur - utilise l'opérateur -= comme ceci :

• Création d'une copie result  de num1.
• Utilisation de l'opérateur -= sur result en lui passant num2 comme opérande.
• Le résultat de l'opération est result.

Problème de la multiplication des grands nombres

Pour la multiplication, il n'est pas possible de procéder par tranche de 16 bits comme on l'a fait pour l'addition et la soustraction. En effet, le produit de deux nombres de 16 bits a un résultat sur 32 bits avec un possibilité d'overflow dont la détection nécessiterait un bit supplémentaire. Or, la nécessité du développement de la classe DoubleLong est justement l'absence d'outil permettant de calculer sur plus de 32 bits. Aussi est-il nécessaire de procéder autrement.

L'algorithme utilisé est celui du principe de la machine à calculer de Blaise Pascal. La Pascaline ne permettant que de faire des additions, pour effectuer des multiplications, il est nécessaire plusieurs additions. Par exemple, pour effectuer la multiplication de num1 par num2, il faut ajouter plusieurs fois num2 à 0 en comptant les additions jusqu'à ce que le compteur atteigne num1. Le problème de cette solution est que pour les nombres de 64 bits, il faut envisager 18 446 744 073 709 551 616 itérations. Que dire sur des nombres de 128 bits ? Ce qui pose deux problèmes :

• Le temps que va prendre la boucle sur un nombre aussi grand d'itérations. Il faut se rappeler que le traitement de la fonction loop() de l'Arduino doit être aussi bref que possible. De toute façon, une boucle exécutant ce nombre d'itérations de 32 bit prendrait plus d'une journée sur un Arduino. Alors pour 64 bits ...
• La gestion d'un compteur aussi grand sur 64 bits dans une boucle for. Car on retombe sur le problème du calcul sur plus de 32 bits.

Or, il est possible de réduire le nombre d'itérations en décalant les chiffres vers la gauche. C'est ce que l'on fait en primaire lorsqu'on pose une multiplication. A chaque ligne, on décale les chiffres d'une position vers la gauche. Ce qui revient, en base 10, à multiplier la ligne par 10.

En binaire, c'est encore plus simple. Décaler d'un bit vers la gauche revient à multiplier le nombre par 2. De ce fait, il existe un algorithme très simple pour faire une multiplication bit à bit. Soit deux nombre num1 et num2 correspondant respectivement aux opérandes de gauche et de droite de l'opérateur. On va procéder à plusieurs décalage de 1 bit vers la gauche. Le nombre de décalage est égale au nombre de bits des nombres. Ce qui limite le nombre d'itération à ce nombre. A titre indicatif, procéder ainsi avec 64 bits sur un Arduino, les 64 itérations nécessaires prennent moins de 4 millisecondes.

• Un accumulateur result est initialisé à 0. A noter que l'accumulateur doit avoir deux fois plus de bits que les opérandes.
• Pour chaque bit de rang i :
• On regarde la valeur du bit le plus à droite de num1.
• Si ce bit vaut 1 :
• On ajoute num2 à l'accumulateur result.
• On décale num2 de 1 bit vers la gauche (le bit le plus à gauche est perdu mais ça n'a pas d'importance sinon pour le calcul éventuel d'un overflow). num2 vaut maintenant deux fois sa valeur précédente. 
• On décale num1 de 1 bit vers la droite. Le bit le plus est droite est perdu. Mais ça n'a aucune importance. Car ce bit n'est utilisé que pour savoir si on procède à l'addition ou non. De ce fait, à l'itération suivante, on pourra à nouveau tester le bit le plus à droite de num1 sans avoir d'opération binaire compliquée à effectuer.

La figure ci-dessous illustre le principe de l'opération. Dans la colonne de gauche l'opérande num2 est décalée de 1 bit vers la gauche. Dans la colonne num1, la première opérande est décalé de 1 bit vers la droite à chaque ligne. Lorsque le bit le plus à droite est égal  à 1, une addition est effectuée. Lorsque le bit est nul, l'accumulateur conserve sa valeur. Dans la colonne result figurent les valeurs successive de l'accumulateur à chaque itération en gras lorsqu'une addition a été effectuée. On peut remarquer que la disposition de l'opération est similaire à celle pratiquée en primaire pour la multiplication en base 10. 

																|	num1	|	result
num2								0	1	1	0	1	0	1	1	|		|
num1								1	0	0	1	1	0	1	1	|		|
								0	1	1	0	1	0	1	1	|	10011011	|	0000000001101011
							0	1	1	0	1	0	1	1	.	|	01001101	|	0000000101000001
						0	0	0	0	0	0	0	0	.	.	|	00100110	|	0000000101000001
					0	1	1	0	1	0	1	1	.	.	.	|	00010011	|	0000010010011001
				0	1	1	0	1	0	1	1	.	.	.	.	|	00001001	|	0000101101001001
			0	0	0	0	0	0	0	0	.	.	.	.	.	|	00000100	|	0000101101001001
		0	0	0	0	0	0	0	0	.	.	.	.	.	.	|	00000010	|	0000101101001001
	0	1	1	0	1	0	1	1	.	.	.	.	.	.	.	|	00000001	|	0100000011001001
0	1	0	0	0	0	0	0	1	1	0	0	1	0	0	1	|		|

En conclusion, pour pratiquer la multiplication, des outils de décalage de 1 bit vers la gauche et vers la droite sur les grands nombres sont indispensables. C'est le rôle des méthodes de décalage __shiftL() et __shiftR().

Code des méthodes de décalage __shiftL() et __shiftR()

La méthode __shiftL() effectue un décalage des tous les bits de l'objet DoubleLong vers la gauche. Cela revient à effectuer une multiplication par 2 de l'objet. A l'issue de l'opération le bit bit le plus à gauche disparaît pour alimenter l'attribut privé __carry, signalant ainsi qu'il y a eu un overflow. Le bit le plus à droite est alimenté par le paramètre lastCarry passé à la méthode. Par défaut, il vaut 0.

void DoubleLong::__shiftL(uint8_t lastCarry) {
  this->__carry = lastCarry ? 1: 0;
  uint8_t carry;
  for (int i = 0; i < LENGTH; i++) {
    carry = (this->__value[i] & 0x8000) ? 1 : 0;
    this->__value[i] = (this->__value[i] << 1) + this->__carry;
    this->__carry = carry;
  }
}

• L'attribut privé __carry est tout d'abord initialisé avec la valeur lastCarry passée en paramètre.
• Ensuite, pour chaque membre du tableau __value, la valeur du bit de poids le plus fort est rangé dans une variable locale carry pour éviter qu'il soit perdu.
• Un décalage de 1 bit vers la gauche est effectué sur le membre de rang i du tableau. A l'issue du décalage le bit du poids le plus faible est alimenté avec la valeur précédente de l'attribut __carry.
• La valeur de l'attribut __carry est mis à jour à partir de la valeur sauvegardée dans carry.

La méthode __shiftR() effectue un décalage des tous les bits de l'objet DoubleLong vers la droite. Cela revient à effectuer une division par 2 de l'objet. A l'issue de l'opération le bit bit le plus à droite disparaît pour alimenter l'attribut privé __carry, signalant ainsi qu'il y a eu un overflow. Le bit le plus à gauche est alimenté par le paramètre lastCarry passé à la méthode. Par défaut, il vaut 0.

void DoubleLong::__shiftR(uint8_t lastCarry) {
  this->__carry = lastCarry ? 1 : 0;
  uint8_t carry;
  for (int i = LENGTH - 1; i >= 0; i--) {
    carry = this->__value[i] & 1;
    this->__value[i] = (this->__value[i] >> 1) + 0x8000 * this->__carry;
    this->__carry = carry;
  }
}

• L'attribut privé __carry est tout d'abord initialisé avec la valeur lastCarry passée en paramètre.
• Ensuite, pour chaque membre du tableau __value, la valeur du bit de poids le plus faible est rangé dans une variable locale carry pour éviter qu'il soit perdu.
• Un décalage de 1 bit vers la droite est effectué sur le membre de rang i du tableau. A l'issue du décalage le bit du poids le plus fort est alimenté avec la valeur précédente de l'attribut __carry.
• La valeur de l'attribut __carry est mis à jour à partir de la valeur sauvegardée dans carry.

Code de la méthode statique multiplication()

Grâce aux méthodes décalage élaborées ci-dessus, il est possible d'implémenter l'algorithme de la multiplication.

La méthode multiplication() effectue le produit des deux opérandes de 64 bits operandL et operandR pour fournir un résultat sur 128 bits. Le résultat de 128 bits est fourni sous la forme d'un tableau de deux DoubleLong dont l'adresse product est passé en premier paramètre. Le tableau destiné à recueillir le résultat doit donc être déclaré dans le programme appelant avant l'invocation de la méthode. product[|0] contient le résultat du produit operandL * operandR tronqué que 64 bits. product[1] contient les 64 bits de poids fort du résultat.

void DoubleLong::multiplication(DoubleLong* product, DoubleLong operandL, DoubleLong operandR) {
DoubleLong excess;
  while (operandL != ZERO) {
    if (operandL.__value[0] & 1) {
      product[0] += operandR;
      product[1] += excess;
      if (product[0].__carry) {
        product[1]++;
      }
    }
    operandL.__shiftR();
    operandR.__shiftL();
    excess.__shiftL(operandR.__carry);
  }
}

• Le résultat  n'est pas renvoyé dans la pile de retour de la méthode. Celle-ci est donc déclarée void.
• La méthode reçoit trois paramètres :
• product est l'adresse d'un tableau de deux DoubleLong destiné à recueillir le résultat de la multiplication sur 128 bits.
• operandL est la première opérande correspondant à celle de gauche de l'opérateur.
• operandR est la seconde opérande correspondant à celle de droite de l'opérateur.
• La variable locale excess est destinée recevoir les bits excédentaires issus des décalages successifs d'operandR vers la gauche afin de permettre les opérations de calcul du résultat sur 128 bits.
• Le nombre d'itérations à effectuer dépend de la valeur d'operandL. Il est de 64 maximum. Mais il peut être réduit si plusieurs bits  de poids le  plus fort sont à 0. En effet, une fois qu'il n'existe plus aucun bit à 1 dans operandL à l'issus de quelques décalages vers la droite, il est inutile de poursuivre les 64 itérations maximums de l'algorithme puisque la valeur à ajouter dans l'accumulateur product serait systématiquement nulle.
• En effectuant une opération logique ET sur le dernier bit du nombre, en fait le dernier bit de __value[0], en fonction du résultat 1 ou 0 on effectue (ou pas) l'addition de operandR dans la partie faible de l'accumulateur (product[0]). Les bits excédentaires  sont eux ajoutés à product[1], y compris la retenue de l'addition à product[0].
• On procède alors au décalage vers la droite d'operandL pour pouvoir tester le prochain bit à l'itération suivante.
• On procède également au décalage vers la gauche d'operandR et des bits excédentaires contenus dans excess en récupérant au passage la retenue du décalage d'operandR.

Code de l'opérateur *

Du coup le codage de l'opérateur * devient très simple. Il reçoit deux opérandes non modifiable en paramètres et il fournit en résultat une nouvelle instance de la classe DoubleLong. 

DoubleLong operator * (const DoubleLong& num1, const DoubleLong& num2) {
  DoubleLong accumulator[2];
  DoubleLong::multiplication(accumulator, num1, num2);
  accumulator[0].__carry = (accumulator[1] == ZERO) ? 0 : 1;
  return accumulator[0];
}

• Les opérandes num1 et num2 sont passées en paramètre par référence et déclarées const pour ne pas pouvoir être modifiées par l'opérateur.
• Le retour de l'opérateur * est une nouvelle instance de DoubleLong
• On commence par définir un tableau accumulator de deux DoubleLong destiné à recueillir le résultat du produit de num1 par num2. 
• La méthode statique multiplication() est alors invoquée. Le résultat du produit de num1 par num2 se trouvent maintenant dans accumulator[1] et accumulator[0].
• L'opérateur * opérant dans le référentiel DoubleLong, il doit fournir un résultat de classe DoubleLong. En conséquence, seule la partie faible du produit, accumulator[0], est fournie en résultat, correspondant au produit sur 128 bits tronqué à 64 bits. La partie forte, accumulator[1] ne sert, si elle est différente de ZERO, qu'à à activer l'attribut __carry du résultat, signalant ainsi qu'il y a eu un dépassement de capacité.

Code de l'opérateur *=

L'opérateur *= modifie l'opérande de gauche en effectuant le produit par l'opérande de droite num passée en paramètre.

DoubleLong& DoubleLong::operator *= (const DoubleLong &num) {
  *this = *this * num;
  return *this;
}

• L'opérande de droite num est passée en paramètre par référence et déclarée const pour ne pas pourvoir être modifiée pas l'opérateur.
• L'opérateur *= est considéré comme une méthode. this est l'adresse de l'instance sur laquelle est invoquée la méthode. En C++, *this signifie valeur pointée par this. L'opérande de gauche *this est donc l'instance de DoubleLong  sur laquelle est invoqué l'opérateur *=. Celle-ci est modifiée par l'opérateur. 
• L'opérateur *= invoque l'opérateur * en passant en paramètres *this et num. Le résultat est affecté à *this.
• Comme tous les opérateurs d'affectation, *= est déclaré DoubleLong&. Le résultat est une référence sur l'opérande de gauche *this modifiée.

Problème de la division des grand nombres

Pour la division, le problème est assez semblable à la multiplication. Et une solution similaire doit être adoptée. Mais si pour la multiplication, on procédait par des additions successives, pour la division ce sont des soustractions qui seront effectuées. Et, pour ne pas multiplier les itérations, là encore, ce sont les fonctions de décalage qui seront utilisées. Pour l'expression num1/num2, num1 est appelé dividende et num2 diviseur. L'algorithme utilisé est assez semblable à celui pratiqué en primaire pour la division décimale. Mais en binaire il est encore plus simple :

• On effectue une série de décalage du diviseur num2 de 1 bit vers la gauche tant que le diviseur est  plus petit que le dividende, ou que le bit le plus  à gauche du diviseur soit égale à 1. Ceci est une condition initiale pour que l'algorithme fonctionne. Le nombre de décalage effectué dépend évidemment des valeurs respectives du dividende et du diviseur. Soit k ce nombre. La valeur maximum de k est forcément inférieur au nombres de bits sur lesquels s'effectue le calcul.  Pour DoubleLong, k est inférieur à LENGTH.
• Initialisation d'un accumulateur result à 0
•  k étant connus, on va exécuter la boucle suivante k fois :
• Décalage de result de 1 bit vers la  gauche. La première fois result reste nul.
• Si  num2 < num1 alors
• Soustraction num1 = num1 - num2
• Incrémentation de result = result + 1
• Décalage de num2 de 1 bit vers la droite.
• A la fin de la boucle, result contient le résultat de la division entière de num1 par num2. Et num2 contient le reste de la division entière.

La figure ci-dessous illustre le principe de l'opération pour la division d'un nombre binaire de 16 bits par un nombre binaire de 8 bits. Dans la colonne de gauche figurent les soustractions et les valeurs successives de num1. Dans la colonne de droite figurent les valeurs successives de result au fur et à mesure des décalages. Comme pour la multiplication une telle disposition est similaire à celle pratiquée en primaire pour la division en base 10.

num1																|	num2 < num1	|	num2 result
0	0	0	0	1	0	0	1	1	0	1	0	0	1	1	1	|		|	0	0	1	1	0	1	1	0
			-	1	1	0	1	1	0	.	.	.	.	.	.	|	0	|	0	0	0	0	0	0	0	0
				-	1	1	0	1	1	0	.	.	.	.	.	|	1	|	0	0	0	0	0	0	0	1
				0	0	1	0	1	1	1	0	0	1	1	1	|		|
					-	1	1	0	1	1	0	.	.	.	.	|	0	|	0	0	0	0	0	0	1	0
						-	1	1	0	1	1	0	.	.	.	|	1	|	0	0	0	0	0	1	0	1
						0	1	0	0	1	1	0	1	1	1	|		|
							-	1	1	0	1	1	0	.	.	|	1	|	0	0	0	0	1	0	1	1
							0	0	1	0	1	1	1	1	1	|		|
								-	1	1	0	1	1	0	.	|	0	|	0	0	0	1	0	1	1	0
									-	1	1	0	1	1	0	|	1	|	0	0	1	0	1	1	0	1
Reste :									0	1	0	1	0	0	1	|		|

Il faut remarquer dans la figure ci-dessus que les bits résultant de l'assertion num2 < num1, qui rend la soustraction possible, sont exactement ceux du résultat de la division entière. Dans le cas le plus défavorable, cet algorithme ne prend pas plus de 3 millisecondes en 64 bits sur un Arduino.

Code de la méthode statique division()

La méthode division() effectue la division entière des deux opérandes de 64 bits dividend et divider. Comme l'algorithme calcule à la fois le résultat entier et le reste de la division, le résultat global est fourni dans un tableau de deux DoubleLong dont l'adresse quotient est passée en premier paramètre. Le tableau destiné à recueillir le résultat doit donc être déclaré dans le programme appelant avant l'invocation de la méthode. quotient[0] contient le résultat entier de la division. quotient[1] contient le reste de la division entière. 

/* 1 */
void DoubleLong::division(DoubleLong* quotient, DoubleLong dividend, DoubleLong divider) {
  /* 2 */
  if (divider.isNull()) {
    quotient[0] = ZERO;
    quotient[0].__error = true;
    quotient[1] = dividend;
    quotient[1].__error = true;
    return;
  }
  /* 3 */
  uint8_t k = 0;
  while ((divider < dividend) && !(divider.__value[LENGTH - 1] & 0X8000)) {
    divider.__shiftL();
    k++;
  }
  /* 4 */
  DoubleLong result;
  for (int i = 0; i <= k; i++) {
    result.__shiftL();
    if (dividend > divider) {
      result++;
      dividend -= divider;
    }
    divider.__shiftR();
  }
  /* 5 */
  quotient[0] = result;
  quotient[1] = dividend; 
}

1. Comme pour la méthode multiplication, le résultat n'est pas renvoyé dans la pile de retour de la méthode. Celle-ci est donc déclarée void.
   La méthode reçoit trois paramètres :
• quotient est l'adresse d'un tableau de deux DoubleLong destiné à recueillir les résultats de la division.
• dividend est l'opérande qui doit être divisée, celle de  gauche de l'opérateur.
• divider est le diviseur, l'opérande de droite de l'opérateur.
2. En arithmétique, la division n'a de sens que si le diviseur est non nul. Un contrôle est effectué en début de méthode. Si le diviseur est nul, le résultat fourni n'a pas vraiment de sens. Cependant, en C++, il est nécessaire de fournir une valeur. Pour les deux résultat fournis, l'attribut __error est mis à true. Le résultat arbitraire, dans ce cas, et le suivant :
• quotient[0] vaut ZERO, c'est à dire un DoubleLong dont tous les membres du tableau __value sont nuls.
• quotient[1] vaut la valeur initiale de l'opérande dividend. Ce qui peut être compris comme « la division d'ayant pas eu lieu, le reste à diviser est dividend ».
3. Pour que l'algorithme fonctionne il faut que le bit de poids fort du diviseur soit le plus à gauche possible. Pour cela, on effectue une série de décalage du diviseur de 1 bit vers la gauche. Afin de l'imiter le nombre d'itérations (64 au maximum), il est inutile de poursuivre les décalages jusqu'à 64. On peut s'arrêter dès que le diviseur est supérieur au dividende. Le nombre décalage effectués est compté dans la variable locale k. Car il faudra procéder à un même nombre de décalages inverses à chaque itération après la soustraction.
4. Un accumulateur result est initialisé à ZERO. A chaque itération :
• On procède à un décalage de result de 1 bit vers la gauche. A la première itération, c'est sans effet puisque result est nul. 
• Si le diviseur est inférieur ou égal au dividende, on peut procéder à la soustraction dividend - divider. Le bit de poids le plus faible de result est mis à 1. Cela se fait par une simple incrémentation de result en utilisant l'opérateur ++ (voir plus loin la description de cet opérateur sur les grands nombres). 
• Dans le cas contraire, on ne fait rien. la valeur de dividend reste inchangée et le bit de poids le plus faible de result reste à 0.
• Dans tous les cas, on procède d'un décalage du diviseur d'un bit vers la droite.
5. La boucle s'arrête lorsque le diviseur retrouve sa valeur initiale. A la fin de la boucle :
• result est égale au résultat de la division entière de dividend par divider sur 64 bits. Cette valeur est affectée à quotient[0].
• dividend , après avoir subit une succession de soustractions, contient le reste de la division sur 64 bits. Cette valeur est affectée à quotient[1].

Code de l'opérateur /

Comme pour la multiplication, la méthode division() existant, le codage de l'opérateur / devient très simple. Il reçoit deux opérandes en paramètres et fournit en résultat une nouvelle instance de la classe DoubleLong.

DoubleLong operator / (const DoubleLong &num1, const DoubleLong &num2) {
  DoubleLong quotient[2];
  DoubleLong::division(quotient, num1, num2);
  return quotient[0];
}

• les opérandes num1 et num2 sont passée en paramètre par référence et déclarées const pour ne pas pouvoir être modifiées par l'opérateur.
• Le retour de l'opérateur / est une nouvelle instance de DoubleLong
• On commence par définir un tableau quotient de deux DoubleLong destiné à recueillir les résultats de la division de num1 par num2. 
• La méthode statique division() est alors invoquée. quotient[0] contient le résultat de la division entière de num1 par num2. quotient[1].
• L'opérateur * opérant dans le référentiel DoubleLong, il doit fournir un résultat de classe DoubleLong. En conséquence, seule la partie faible du produit, accumulator[0], est fournie en résultat, correspondant au produit sur 128 bits tronqué à 64 bits. La partie forte, accumulator[1] ne sert, si elle est différente de ZERO, qu'à à activer l'attrib

Code de l'opérateur /=

L'opérateur /= modifie l'opérande de gauche en effectuant la division de celle-ci par l'opérande de droite num passée en paramètre.

DoubleLong& DoubleLong::operator /= (const DoubleLong &num) {
  *this = *this / num;
  return *this;
}

• L'opérande de droite num est passée en paramètre par référence et déclarée const pour ne pas pourvoir être modifiée pas l'opérateur.
• L'opérateur /= est considéré comme une méthode. this est l'adresse de l'instance sur laquelle est invoquée la méthode. En C++, *this signifie valeur pointée par this. L'opérande de gauche *this est donc l'instance de DoubleLong  sur laquelle est invoqué l'opérateur /=. Celle-ci est modifiée par l'opérateur. 
• L'opérateur /= invoque l'opérateur / en passant en paramètres *this et num. Le résultat est affecté à *this.
• Comme tous les opérateurs d'affectation, /= est déclaré DoubleLong&. Le résultat est une référence sur l'opérande de gauche *this modifiée.

Code de l'opérateur %

L'opérateur % fonctionne exactement comme l'opérateur /, à la différence que c'est le reste de la division contenu dans quotient[1] qui est renvoyé en résultat et non pas quotient[0]. En effet la méthode division() calcule à la fois le résultat entier de la division dans quotient[0] et le reste de la division entière dans quotient[1].

DoubleLong operator % (const DoubleLong &num1, const DoubleLong &num2) {
  DoubleLong quotient[2];
  DoubleLong::division(quotient, num1, num2);
  return quotient[1];
}

Incrémentation et décrémentation des grands nombres

Ce chapitre traite des opérateurs ++ et --. En effet, leur conception est assez délicate dans le sens ou plusieurs syntaxes sont possibles. Par exemple pour l'opérateur ++, il est possible d'écrire ++num, dans ce cas on parle de pré-incrémentation, ou num++, dans ce cas on parle de post-incrémentation. Globalement, le calcul est le même. Cela revient à écrire l'expression num = num + 1. La distinction provient du moment où se passe l'incrémentation.
Par exemple, pour le code suivant :

num1 = 5
num2 = ++num1

Ces deux instructions exécutées, num1 et num2 valent tous les deux 6. Car l'incrémentation de num1 se produit avant l'affectation de num1 à num2. Alors que pour ce code :

num1 = 5
num2 = num1++

num1 vaut 6. Mais l'incrémentation de num1 s'étant produite après l'affectation de num1 à num2, num2 vaut la valeur de num1 avant l'incrémentation, à savoir 5.

Par ailleurs, les opérateurs de pré-incrémentation et de post-incrémentation sont considérés comme deux opérateurs différents. Or, ils ont tous les deux le même nom en C++ (operator ++) , n'ont qu'une seule opérande de même type, mais qui peut être soit à gauche, soit à droite de l'opérateur et fournissent tous les deux un résultat de même type.

La surcharge de ces quatre opérateurs pour les grands nombres permet de mettre en évidence leurs différences à travers leur implémentation.

Code de l'opérateur de pré-incrementation ++

DoubleLong& DoubleLong::operator++(void) {
  this->__carry = 1;
  for (int i = 0; i < LENGTH; i++) {
    if (this->__carry) {
      uint32_t res = ((uint32_t)this->__value[i]) + 1;
      this->__value[i] = res & 0x0000FFFF;
      this->__carry = (res & 0xFFFF0000) ? 1 : 0;
    }
  }
  return *this;
}

• L'opérateur de pré-incrémentation modifie l'instance sur laquelle il est invoqué qui est considérée comme opérande de droite. Il permet la syntaxe ++num. Il ne prend pas de paramètre (void). Le résultat est une référence sur l'instance modifiée. Il est donc déclaré de type DoubleLong&.
• La retenue __carry est pré-positionnée à 1.
• Pour chaque membre du tableau __value :
• Si la retenue est à 1
• Le membre __value[i] est incrémenté de 1. L'incrémentation se fait sur 32 bits (alors que __value[i] est codé sur 16 bits)  pour détecter le dépassement. sur les 16 bits de poids fort. Le résultat de l'incrémentation du  membre est rangé dans la variable locale res (de 32 bits).
• La nouvelle valeur du membre __value[i] correspond aux 16 bits de poids faible de res.
• Si les 16 bits de poids fort de res ne sont pas nuls, c'est qu'il y a eu un dépassement. La retenue __carry est alors mise à 1. Sinon elle est mise à 0.
• Le résultat de l'opération est l'instance elle-même.

Code de l'opérateur de post-incrementation ++

const DoubleLong DoubleLong::operator++(int) {
  DoubleLong result = *this;
  this->operator++();
  return result;
}

• L'opérateur de post-incrémentation modifie l'instance sur laquelle il est invoqué qui est considérée comme opérande de gauche. Il permet la syntaxe num++.  Afin de le distinguer de l'opérateur de pré-incrémentation dans la syntaxe, on lui passe un paramètre anonyme de type int. 
• Le résultat de l'opération est la valeur de l'instance avant l'incrémentation. Cette valeur est sauvegardée dans la variable locale result. 
• L'incrémentation se fait en invoquant l'opérateur de pré-incrémentation dans la syntaxe explicite.
• Le résultat de l'opération est la valeur de l'instance sauvegardée dans result. Il s'agit donc d'une nouvelle instance. Cependant celle-ci ne peut ni ne doit être modifiée par le programme utilisant l'opérateur. Celui-ci est donc déclaré de type const DoubleLong.

Code de l'opérateur de pré-décrementation --

DoubleLong& DoubleLong::operator--(void) {
  uint8_t carry;
  this->__carry = 1;
  for (int i = 0; i < LENGTH; i++) {
    carry = 0;
    if (this->__carry) {
      carry = this->__value[i] ? 0 : 1;
      this->__value[i]--;
    }
    this->__carry = carry;
  }
  return *this;
}

• L'opérateur de pré-décrémentation modifie l'instance sur laquelle il est invoqué qui est considérée comme opérande de droite. Il permet la syntaxe - - num. Il ne prend pas de paramètre (void). Le résultat est une référence sur l'instance modifiée. Il est donc déclaré de type DoubleLong&.
• La retenue __carry est pré-positionnée à 1.
• Pour chaque membre du tableau __value :
• Un variable locale carry destinée à recueillir la retenue générée par la décrémentation est initialisée à 0.
• Si la retenue __carry (qu'il ne faut pas confondre avec la variable locale carry sans les soulignés) précédente  est à 1
• Si le membre __value[i] est nul, sa décrémentation va générer une retenue qui doit être propagée dans la décrémentation du membre suivant. Lui-même va passer à 0xFFFF. Cette retenue est sauvegardée dans la variable locale carry.
• Le membre __value[i] est décrémenté de 1. 
• La retenue carry générée par la décrémentation est réaffecté à __carry pour être prise en compte à l'itération suivante.
• Le résultat de l'opération est l'instance elle-même.

Code de l'opérateur de post-décrementation --

const DoubleLong DoubleLong::operator--(int) {
  DoubleLong result = *this;
  this->operator--();
  return result;
}

• L'opérateur de post-décrémentation modifie l'instance sur laquelle il est invoqué qui est considérée comme opérande de gauche. Il permet la syntaxe num - -.  Afin de le distinguer de l'opérateur de pré-incrémentation dans la syntaxe, on lui passe un paramètre anonyme de type int. 
• Le résultat de l'opération est la valeur de l'instance avant la décrémentation. Cette valeur est sauvegardée dans la variable locale result. 
• La décrémentation se fait en invoquant l'opérateur de pré-décrémentation dans la syntaxe explicite.
• Le résultat de l'opération est la valeur de l'instance sauvegardée dans result. Il s'agit donc d'une nouvelle instance. Cependant celle-ci ne peut ni ne doit être modifiée par le programme utilisant l'opérateur. Celui-ci est donc déclaré de type const DoubleLong.

Les opérateurs de décalage

Disposant des méthodes privées __shiftR() et __shiftL(), il serait dommage de ne pas en profiter pour surcharger les opérateurs de décalage, même si cela ne présente pas vraiment d'utilité pour les grands nombres dont la vocation est le calcul arithmétique et non les opérations binaires bit à bit. Ils sons implémentés ici à titre d'exemple.

Code de l'opérateur d'affectation >>=

L'opérateur >>= effectue un décalage de kShift bits vers la droite sur le DoubleLong sur lequel il est invoqué. Les bits les plus à droite sont perdus. Les bits les plus à gauche sont alimentés par des 0. Le résultat de l'opération est une référence sur l'objet lui-même.

DoubleLong& DoubleLong::operator >>= (uint8_t kShift) {
  for (int i = 0; i < kShift; i++) {
    this->__shiftR();
  }
  return *this;
}

• Comme tous les opérateurs d'affectation, il est déclaré DoubleLong&. C'est une méthode de la classe DoubleLong.
• Il reçoit un seul paramètre de type uint8_t sur 8 bits. Ce qui permet 255 décalages. C'est suffisant pour des grands nombres de 64 bits. Au dela de 64 décalage, l'opérande est forcément nulle. Le paramètre est considéré comme non signé car une valeur négative n'aurait aucun sens.
• La méthode privée  __shiftR() est invoquée kShift fois sur l'objet lui-même.
• Le résultat est une référence sur l'objet lui-même.

Code de l'opérateur de décalage >>

L'opérateur >> effectue un décalage de  bits kShift vers la droite de l'opérande num  passée en paramètre. Le résultat est une nouvelle instance de DoubleLong. num n'est pas modifié.

DoubleLong operator >> (const DoubleLong& num, kShift) {
  DoubleLong result (num);
  return result >>= kShift;
}

• L'opérateur >> est une fonction externe amie de la classe DoubleLong.  
• Elle reçoit en paramètres l'opérande de gauche num qui est une référence sur un objet DoubleLong et l'opérande de droite kShift de type uint8_t.
• Une copie de num est créée dans result.
• On invoque l'opérateur >>= sur la nouvelle instance result.
• Le résultat est result après décalage.

Code de l'opérateur d'affectation <<=

L'opérateur <<= effectue un décalage de kShift bits vers la gauche sur le DoubleLong sur lequel il est invoqué. Les bits les plus à gauche sont perdus. Les bits les plus à droite sont alimentés par des 0. Le résultat de l'opération est une référence sur l'objet lui-même.

DoubleLong& DoubleLong::operator <<= (uint8_t kShift) {
  for (int i = 0; i < kShift; i++) {
    this->__shiftL();
  }
  return *this;
}

• Comme tous les opérateurs d'affectation, il est déclaré DoubleLong&. C'est une méthode de la classe DoubleLong.
• Il reçoit un seul paramètre de type uint8_t sur 8 bits.
• La méthode privée  __shiftL() est invoquée kShift fois sur l'objet lui-même.
• Le résultat est une référence sur l'objet lui-même.

Code de l'opérateur de décalage <<

L'opérateur << effectue un décalage de  bits kShift vers la gauche de l'opérande num  passée en paramètre. Le résultat est une nouvelle instance de DoubleLong. num n'est pas modifié.

DoubleLong operator << (const DoubleLong& num, uint8_t kShift) {
  DoubleLong result = num;
  return result <<= kShift;
}

• L'opérateur << est une fonction externe amie de la classe DoubleLong.  
• Elle reçoit en paramètres l'opérande de gauche num qui est une référence sur un objet DoubleLong et l'opérande de droite kShift de type uint8_t.
• Une copie de num est créée dans result.
• On invoque l'opérateur <<= sur la nouvelle instance result.
• Le résultat est result après décalage.

Remarque sur les opérateurs >> et <<

En C++, Les opérateurs << et >> ne sont pas utilisés que pour effectuer des décalages de bits. Ils sont aussi utilisés pour les entrées-sorties. << sert à écrire dans un flux (cout par exemple). >> sert à lire dans un flux (cin par exemple).  Dans ce cas leur déclaration et la nature de leurs opérandes est différente. Ils n'offrent aucun intérêt dans le cadre des applications sur l'Arduino. Si nécessaires, ils seraient implémentés comme des fonctions amies (friend) et seraient implémentés comme ci-dessous :

ostream& operator << (ostream &out, const Doublelong& num) {
    out << . . .;
    return out;
}

istream& operator >> (istream &in, const Doublelong& num) {
    in >> . . .;
    return in;
}

Comparaison des grands nombres

Comme pour tous les autres types numériques, il est nécessaire de pouvoir effectuer des comparaisons entre grands nombres. Le C++ permet la surcharge des opérateurs de comparaison pour cet usage. Ceux-ci sont tous implémentés comme des fonctions externes à la classe recevant en paramètres les deux opérandes à comparer. Le résultat est un booléen.

Code de la méthode isNull()

La méthode isNull() est une méthode publique. Elle renvoie true si tous les membres du tableau privé __value sont nuls.

bool DoubleLong::isNull() {
  for (int i = 0; i < LENGTH; i++) {
    if (this->__value[i]) return false;
  }
  return true;
}

• Le tableau __value est exploré membre par membre.
• Dès q'un membre est trouvé non nul la méthode s'arrête est renvoie false.
• Si tous les membres sont nuls, la méthode renvoie true. 

Code de l'opérateur ==

bool operator == (const DoubleLong &num1, const DoubleLong &num2) {
  for (int i = 0; i < DoubleLong::LENGTH; i++) {
    if (num1.__value[i] != num2.__value[i]) return false;
  }
  return true;
}

• L'opérateur == est une fonction externe amie (friend). Il reçoit en paramètre les deux opérandes à comparer. 
• Les membres du tableau __value sont comparés de façon homologue deux à deux.
• Dès que deux membres homologues sont trouvés différents, fonction s'arrête et renvoie false.
• Si tous les membres de même rang sont égaux, la fonction renvoie true.

Code de l'opérateur !=

bool operator != (const DoubleLong &num1, const DoubleLong &num2) {
  return !operator ==(num1, num2);
}

• L'opérateur != renvoie la négation de l'opérateur ==.

Code de la méthode privée statique  __isLower()

La méthode __isLower() est utilisée par les opérateurs relatif à la relation d'ordre qui existe pour les objets DoubleLong. C'est une méthode de classe privée qui n'est pas exposée dans l'interface publique de la classe DoubleLong.

bool DoubleLong::__isLower(const DoubleLong& num1, const DoubleLong& num2, bool isEqual) {
  for (int i = LENGTH - 1; i >= 0; i--) {
    if (num1.__value[i] != num2.__value[i]) {
      return (num1.__value[i] < num2.__value[i]);
    }
  }
  return isEqual;
}

• La méthode reçoit trois paramètres :
• num1 est l'opérande de gauche.
• num2 est l'opérande de droite.
• isEqual indique si la comparaison est stricte ou large. 
• Les membres __value[i] homologues des deux opérandes num1 et num2 sont comparés deux à deux successivement en commençant par les membres des poids le plus fort. Dès que, pour le rang i, la relation d'ordre < ou > est avérée, le résultat est true si inférieur ou false si supérieur. Ça ne sert à rien de poursuivre la boucle pour les membres de poids le plus faible. Lorsque la boucle arrive au bout, cela signifie que tous les membres sont égaux. Le paramètre isEqual est alors exploité pour distinguer les comparaisons strictes des comparaisons larges. 
• Le résultat est booléen. Si isEqual est vrai, la méthode renvoie true si num1 est inférieur ou égale à num2. Si isEqual est faux, la méthode renvoie true uniquement si num1 est strictement inférieure à num2.

Code de l'opérateur <

bool operator < (const DoubleLong &num1, const DoubleLong &num2) {
  return DoubleLong::__isLower(num1, num2, false);
}

• L'opérateur < invoque la méthode __isLover()  au sens stricte.

Code de l'opérateur <= 

bool operator <= (const DoubleLong &num1, const DoubleLong &num2) {
  return DoubleLong::__isLower(num1, num2, true);
}

• L'opérateur < invoque la méthode __isLover()  au sens large.

Code de l'opérateur >

bool operator > (const DoubleLong &num1, const DoubleLong &num2) {
  return !operator <= (num1, num2);
}

• L'opérateur > invoque explicitement la négation de de l'opérateur <=. 

Code de l'opérateur >=

bool operator >= (const DoubleLong &num1, const DoubleLong &num2) {
  return !operator < (num1, num2);
}

• L'opérateur >= invoque explicitement la négation de de l'opérateur <.

Les opérateurs de conversion implicite

Les opérateurs de conversion implicite sont indispensables pour l'interopérabilité avec les autres types numériques.

Ces opérateurs introduisent une ambiguïté dans l'utilisation des opérateurs utilisant l'une une instance de la classe DoubleLong et l'autre une expression de type numérique prédéfinie. En effet la classe DoubleLong ne fait pas partie de la liste de priorité des conversions implicites forçant l'opération dans le type le plus grand (double > float > unsigned long > long > unsigned int > int > char). Cette ambiguïté est signalée à la compilation. Elle peut être levée en précisant par un cast (changement de type) de l'une ou l'autre des opérandes dans quel référentiel l'opération doit être effectuée.

Code de l'opérateur de conversion en entier long

operator uint32_t() effectue la conversion d'un DoubleLong en un entier non signé sur 32 bits. Si le DoubleLong est supérieur à 2³², le nombre est tronqué sur 32 bits. Il permet la syntaxe (long)num ou long(num),  où num est une instance de la classe DoubleLong, pour effectuer un changement de type.
Le type uint32_t étant le type de donnée entière le plus grand dans la hiérarchie des types entiers, il est inutile d'implémenter un type de conversion vers les types plus petits. D'une part DoubleLong implémentant des nombres entiers de grande taille la conversion implicite vers d'autre types plus petits n'a pas beaucoup de sens. D'autre part, la conversion implicite de uint32_t vers tous les autres types entiers existent déjà.

DoubleLong::operator uint32_t() {
  return (uint32_t(this->__value[1]) << 16) + this->__value[0];
}

• Un opérateur de conversion implicite n'a pas besoin de préciser le type du résultat puisque celui-ci est lui-même le nom de l'opérateur uint32_t. 
• Un opérateur de conversion est un membre de la classe DoubleLong. Son implémentation doit donc préciser DoubleLong::.
• Seul les deux membres __value[0] et __value[1], correspondant aux 32 bits de poids faible sont utilisé pour construire un entier non signé sur 32 bits.

Code de l'opérateur de conversion en virgule flottante

operator double() effectue la conversion d'un DoubleLong en un nombre virgule flottante de type double sur 32 bits (pour info, le type double de 64 bits n'est implémenté que sur l'Arduino DUE). Cela permet de passer un objet de type DoubleLong dans les fonctions mathématiques standard (par exemple, la syntaxe sqrt(num) est possible).
Il est inutile d'implémenter operator float(). D'abord, sauf pour Arduino DUE, le type double et le type float sont absolument identiques. Dans tous les cas, la conversion implicite de double vers float existe déjà.

DoubleLong::operator double() {
  double base = 1.0;
  double result = 0;
  for (int i = 0; i < LENGTH; i++) {
    result += base * this->__value[i];
    base *= 65536.0;
  }
  return result;
}

• Un opérateur de conversion implicite n'a pas besoin de préciser le type du résultat puisque celui-ci est lui-même le nom de l'opérateur double. 
• Un opérateur de conversion est un membre de la classe DoubleLong. Son implémentation doit donc préciser DoubleLong::.
• Un accumulateur result de type double est initialisé à 0.
• Une variable locale base est initialisée à 1. Elle est multipliée par 2¹⁶ à chaque itération.
• Chaque membre __value[i] est converti en double par une multiplication ce celui-ci à 2^16*i et additionné à result.

Les autres méthodes de la classe DoubleLong

Les autres méthodes publiques de la classe DoubleLong donnent accès aux membres privés __carry et __error en lecture seule pour permettre d'exploiter respectivement un overflow ou une erreur de calcul dans les programme utilisant la classe DoubleLong.

Code de la méthode overflow()

La méthode overflow() exploite l'attribut privé __carry pour signaler au programme appelant que l'opération précédente, effectuée sur un objet DoubleLong, a provoqué un dépassement de capacité.

bool DoubleLong::overflow() {
  return (bool)this->__carry;
}

• Le résultat est true si il y a dépassement de capacité. C'est-à-dire l'attribut __carry est différent de 0.

Code de la méthode error()

La méthode error() exploite l'attribut privé __error pour signaler au programme appelant que l'opération précédente, effectuée sur un objet DoubleLong, a provoqué une erreur de calcul, par exemple en effectuant une division par 0.

bool DoubleLong::error() {
  return this->__error;
}

• La valeur de l'attribut __error est renvoyée en résultat.

Conclusion

Cet article définit une nouvelle classe de donnée numérique DoubleLong. Celle-ci est dotée de tous les opérateurs qui permettent d'effectuer du calcul arithmétique 64 bits, voire beaucoup plus en modifiant la valeur de la constante LENGTH. Elle permet de pallier à l'absence de type de 64 bits comme long long ou double long.

C'est ce nouveau type de données qui va être exploité dans l'article suivant traitant de l'amélioration de la classe ClockTime pour permettre au projet Horloge de dépasser le délai de fonctionnement de 50 jours de l'horloge évoqué dans la précédente version de ClockTime.