Calculer la différence entre deux nombres

Quelques raccourcis :

Si ce texte vous intéresse, vous serez peut-être aussi intéressé(e) par Implémenter assez_proches().

Les équations sur ce site sont affichées avec MathJax.

Le problème du calcul de la différence entre deux nombres peut sembler banal à qui a fait un peu de mathématiques dans sa vie. En effet, il serait simple par exemple de supposer que la différence entre deux nombres et peut s'écrire ... et c'est bien le cas dans un monde idéal. Par exemple, le programme suivant :

#include <iostream>
#include <cmath>
template <class T>
   T difference(T a, T b) {
      return std::abs(a - b);
   }
int main() {
   using std::cout;
   cout << difference(10, 3) << '\n'; // 7
   cout << difference(3, 10) << '\n'; // 7
   cout << difference(3.5, 10.0) << '\n'; // 6.5
   cout << difference(3.5, -10.0) << '\n'; // 13.5
}

... affichera, sans grande surprise (wandbox) :

7
7
6.5
13.5

Cependant, ces tests sont quelque peu naïfs, ne tenant pas compte des valeurs limites. Supposons par exemple que nous souhaitions tester notre fonction difference() sur deux variables de type short et supposons que l'intervalle des valeurs valides pour un short soient (ou )pour un total de possibilités. Que peut-on s'attendre alors du programme suivant?

#include <iostream>
#include <cmath>
#include <limits>
template <class T>
   T difference(T a, T b) {
      return std::abs(a - b);
   }
int main() {
   using namespace std;
   cout << difference(10, 3) << '\n'; // 7
   cout << difference(3, 10) << '\n'; // 7
   cout << difference(3.5, 10.0) << '\n'; // 6.5
   cout << difference(3.5, -10.0) << '\n'; // 13.5
   constexpr auto minval = numeric_limits<short>::min();
   constexpr auto maxval = numeric_limits<short>::max();
   static_assert(minval == -32768);
   static_assert(maxval == 32767);
   cout << difference(short{ -2 }, maxval) << '\n'; // ???
   cout << difference(minval, maxval) << '\n'; // ???
}

Si vous faites le test, vous constaterez probablement (car avec des entiers signés, nous sommes dans le comportement indéfini avec cet exemple, ayant provoqué un débordement de capacité!) que cet ajout, en caractères gras, affichera (wandbox) quelque chose comme et plutôt que et ... même si on parle du résultat d'un calcul de valeur absolue!). Que se passe-t-il ici?

Mathématiques et représentations finies

Notre fonction difference() dans sa forme actuelle accepte deux T en paramètre et retourne un T. La soustraction de short{-32768} par short{32767} donne un nombre (-65535) qui ne peut pas être représenté sur un short. Nous ne sommes pas dans le monde des nombres idéaux, manifestement : nous sommes dans le monde des représentations finies, et notre fonction difference() ne peut, si ses paramètres sont signés, représenter la moitié des différences de valeurs possibles.

Il se trouve que le calcul de la différence entre deux nombres est un calcul qui intervient dans une multitude de calculs essentiels (p. ex. : des tris, où il faut parfois calculer un point milieu entre deux indices, ou encore trouver si deux nombres sont assez proches l'un de l'autre pour être considérés équivalents même si leur représentation est inexacte).

L'importance de ce calcul nous permet d'établir qu'une solution ne tenant pas compte correctement des cas limites (ou, ici, de la moitié des cas possibles, du moins dans le cas des nombres signés) est... insatisfaisante.

Écrire une fonction difference(a,b) – enjeux

Il y a plusieurs enjeux associés à l'écriture d'une fonction difference(a,b) correcte :

La réponse à plusieurs de ces questions est à deux volets :

Nous profiterons donc dans cet article des concepts de C++ 20. Si vous souhaitez des solutions pour des versions du langage antérieures à C++ 20, contactez votre chic prof (c'est beaucoup plus lourd à écrire, alors je le ferai seulement s'il y a de la demande!).

Analyse sommaire du problème

Nous écrirons donc une fonction difference(a,b) acceptant des paramètre a et b de types distincts. Analysons de plus près les principaux enjeux auxquels nous serons confrontés.

Type de la valeur de retour de difference(a,b)

Étrangement, depuis C++ 14, cet aspect du problème est probablement le plus facile à gérer : nous utiliserons auto et nous profiterons des règles implicites au langage pour déterminer, par exemple, le type de l'expression a - b. Ainsi, le type retourné par difference(a,b) sera conséquent avec le type de a - b ce qui peut réduire les risques de surprise dans le code client.

Gestion des signes des types

Cet aspect est intéressant : difference(a,b) est défini pour toute paire de valeurs a et b si a et b sont tous deux non-signés, alors qu'elle ne l'est pas nécessairement si a et b sont non-signés. À titre d'illustration, supposons a et b de type unsigned short tels que :

constexpr auto minval = numeric_limits<unsigned short>::min(),
               maxval = numeric_limits<unsigned short>::max();
static_assert(minval == 0 && maxval == 65535);

Alors le pire cas de difference(a,b) est difference(minval,maxval) ce qui est équivalent à maxval, et est donc par définition représentable dans un unsigned short.

Maintenant, remplaçons unsigned short par signed short (donc short tout simplement). Alors, à titre d'illustration, supposons a et b de type short tels que :

constexpr auto minval = numeric_limits<short>::min(),
               maxval = numeric_limits<short>::max();
static_assert(minval == -32768 && maxval == 32767);

Alors le pire cas de difference(a,b) est difference(minval,maxval) ce qui est équivalent à 65535, ce qui n'est pas (par définition) représentable dans un short.

Sachant que la différence entre deux nombres est toujours positive, nous écrirons difference(a,b) pour tenir compte de cette réalité. Pour des signed short, par exemple, si a et b sont tous deux du même signe (tous deux positifs ou tous deux négatifs), la différence sera représentable à même le type short, mais si leurs signes sont différents l'un de l'autre (un positif et un négatif) alors il faudra s'assurer de faire en sorte que difference(a,b) retourne un unsigned short et que les calculs faits à l'interne pour évaluer ce calcul soient conséquents.

Gestion des cas limites

Il y a des cas pour lesquels aucune représentation efficiente ne sera possible (p. ex. : la différence entre numeric_limits<double>::min() et numeric_limits<double>::max() n'est pas représentable sur un double, qui est le plus grand type numérique supporté sur plusieurs plateformes). Dans un tel cas, il est possible de détecter le problème et de lever une exception, mais étant donné le caractère essentiel et critique des calculs numériques, nous laisserons à la responsabilité du code client d'éviter des calculs absurdes (ainsi, si a - b est un calcul déraisonnable, alors difference(a,b) le sera aussi, et avec des conséquences analogues).

Notez qu'il est possible (surtout en laboratoire) de détecter et de signaler les cas déraisonnables, mais le code de production devrait être numériquement correct (les coûts d'une validation dynamique de ces situations serait prohibitif).

Solution possible

Abordons d'abord le cas du code de test :

Ce code de test évalue d'abord des cas simples :

  • La différence entre 3 et 3 est 0
  • La différence entre 5 et 3 est 2
  • La différence entre 5 et -3 est 2, etc.

Un cas intéressant est celui de la différence entre le plus petit int possible plus un et le plus grand int possible. La raison du +1 et du -1 est le respect des règles du langage (ici, du langage C) par lesquelles un débordement de capacité du type du substrat entraînerait un comportement indéfini.

Quelques cas de comparaisons impliquant des types mixtes suivent.

Pour voir le résultat de l'exécution de ce code de test, voir https://wandbox.org/permlink/Mhe7oCeunyDhnx9S

 Notez au passage le recours à static_assert; il serait déraisonnable de ne pas offrir difference(a,b) de manière constexpr (tristes sont les langages qui poussent de tels calculs à l'exécution quand ils peuvent être résolus à la compilation).

// ...
#include <iostream>
#include <limits>

void test_difference(auto a, auto b) {
   std::cout << "difference(" << a << ", " << b << ") == "
             << difference(a, b) << std::endl;
}

int main() {
   test_difference(3, 3);
   test_difference(5, 3);
   test_difference(5, -3);
   test_difference(-5, -3);
   test_difference(-5, 3);
   test_difference(std::numeric_limits<int>::min(), 0);
   test_difference(std::numeric_limits<int>::min(), 3);
   test_difference(std::numeric_limits<int>::min() + 1, std::numeric_limits<int>::max());
   static_assert(difference(std::numeric_limits<int>::min() + 1, std::numeric_limits<int>::max()) ==
                 std::numeric_limits<unsigned int>::max() - 1);
   test_difference(3.0, 3);
   test_difference(5.1, 3);
   test_difference(5.1, -3);
   test_difference(-3, -5.1);
   test_difference(-5.1, 3.0);
   test_difference(std::numeric_limits<float>::max(), std::numeric_limits<float>::max() / 2);
}

Cela dit, comment difference(a,b) est-elle implémentée? La réponse est... par étapes. Procédons.

Détecter si un nombre est négatif est pertinent dans le calcul de difference(a,b) au sens où si a et b sont tous deux de même signe (tous deux positifs, tous deux négatifs), alors la différence entre a et b se limite à une soustraction et le résultat sera représentable à l'aide du substrat le plus grand des deux.

Dans le cas des entiers non-signés, la réponse est bien sûr triviale.

#include <concepts>
#include <type_traits>
#include <algorithm>
constexpr bool is_negative(std::unsigned_integral auto) {
   return false;
}
constexpr bool is_negative(auto n) {
   return n < 0;
}

Dans le cas de la différence entre deux entiers, le résultat du calcul sera toujours non-signé. La fonction as_unsigned(n) convertira n en son équivalent non-signé s'il y a lieu. Notez que n est nécessairement un entier; il n'y a pas de type à virgule flottante qui soit non-signé en C++.

constexpr auto as_unsigned(std::integral auto n) {
   return static_cast<std::make_unsigned_t<decltype(n)>>(n);
}

La valeur absolue calculée par absolute(n) retourne la valeur absolue de n, mais de manière calculable à la compilation. Note : il y a un bogue sur un cas limite ici, le voyez-vous?

constexpr auto absolute(std::integral auto n) {
   return as_unsigned(is_negative(n) ? -n : n);
}
constexpr auto absolute(auto n) {
   return is_negative(n) ? -n : n;
}

Le calcul de difference(a,b) va comme suit :

  • Si a et b sont tous deux entiers, ou si a et b sont tous deux des nombres à virgule flottante, et si les deux sont de même signe (a et b sont positifs, ou a et b sont négatifs), alors le calcul naïf (valeur absolue de a - b) suffit
  • Si a et b sont tous deux entiers de signes distincts, alors la différence est la somme de la valeur absolue du plus petit (nécessairement négatif) et du plus grand (nécessairement positif) dans sa déclinaison non-signée (pour éviter les débordements)
  • Si a et b sont tous deux des nombres à virgule flottante de signes distincts, alors la différence est la somme de la valeur absolue du plus petit (nécessairement négatif) et du plus grand (nécessairement positif)
  • Si a et b sont tels que l'un des deux est entier et l'autre est à virgule flottante, alors celui qui est entier est converti dans le type de celui qui est à virgule flottante et le calcul suit son cours
constexpr auto difference(std::integral auto a, std::integral auto b) {
   if (is_negative(a) == is_negative(b))
      return absolute(a - b);
   else {
      auto [min, max] = std::minmax(a, b);
      return absolute(min) + as_unsigned(max);
   }
}

constexpr auto difference(std::floating_point auto a, std::floating_point auto b) {
   if (is_negative(a) == is_negative(b))
      return absolute(a - b);
   else {
      auto [min, max] = std::minmax(a, b);
      return absolute(min) + max;
   }
}

constexpr auto difference(std::integral auto a, std::floating_point auto b) {
   return difference(static_cast<decltype(b)>(a), b);
}

constexpr auto difference(std::floating_point auto a, std::integral auto b) {
   return difference(a, static_cast<decltype(a)>(b));
}
}

Le code complet suit :

#include <iostream>
#include <concepts>
#include <type_traits>
#include <algorithm>
#include <limits>

constexpr bool is_negative(std::unsigned_integral auto) {
   return false;
}
constexpr bool is_negative(auto n) {
   return n < 0;
}

constexpr auto as_unsigned(std::integral auto n) {
   return static_cast<std::make_unsigned_t<decltype(n)>>(n);
}

constexpr auto absolute(std::integral auto n) {
   return as_unsigned(is_negative(n) ? -n : n);
}
constexpr auto absolute(auto n) {
   return is_negative(n) ? -n : n;
}

constexpr auto difference(std::integral auto a, std::integral auto b) {
   if (is_negative(a) == is_negative(b))
      return absolute(a - b);
   else {
      auto [min, max] = std::minmax(a, b);
      return absolute(min) + as_unsigned(max);
   }
}

constexpr auto difference(std::floating_point auto a, std::floating_point auto b) {
   if (is_negative(a) == is_negative(b))
      return absolute(a - b);
   else {
      auto [min, max] = std::minmax(a, b);
      return absolute(min) + max;
   }
}

constexpr auto difference(std::integral auto a, std::floating_point auto b) {
   return difference(static_cast<decltype(b)>(a), b);
}

constexpr auto difference(std::floating_point auto a, std::integral auto b) {
   return difference(a, static_cast<decltype(a)>(b));
}

void test_difference(auto a, auto b) {
   std::cout << "difference(" << a << ", " << b << ") == "
             << difference(a, b) << std::endl;
}

int main() {
   test_difference(3, 3);
   test_difference(5, 3);
   test_difference(5, -3);
   test_difference(-5, -3);
   test_difference(-5, 3);
   test_difference(std::numeric_limits<int>::min(), 0);
   test_difference(std::numeric_limits<int>::min(), 3);
   test_difference(std::numeric_limits<int>::min() + 1, std::numeric_limits<int>::max());
   static_assert(difference(std::numeric_limits<int>::min() + 1, std::numeric_limits<int>::max()) ==
                 std::numeric_limits<unsigned int>::max() - 1);
   test_difference(3.0, 3);
   test_difference(5.1, 3);
   test_difference(5.1, -3);
   test_difference(-3, -5.1);
   test_difference(-5.1, 3.0);
   test_difference(std::numeric_limits<float>::max(), std::numeric_limits<float>::max() / 2);
}

Si vous avez des suggestions pour faire mieux encore, contactez-moi!

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !