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.5Cependant, 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?
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.
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!).
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.
É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.
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.
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).
Abordons d'abord le cas du code de test :
Ce code de test évalue d'abord des cas simples :
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). |
|
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. |
|
|
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++. |
|
|
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? |
|
|
Le calcul de difference(a,b) va comme suit :
|
|
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!
Quelques liens pour enrichir le propos.
