Pourquoi `int pow (int base, int exposant)` n'est-il pas dans les bibliothèques C ++ standard?

J'ai l'impression que je dois juste être incapable de le trouver. Y a-t-il une raison pour laquelle la powfonction C ++ n'implémente pas la fonction «power» pour autre chose que floats et doubles?

Je sais que l'implémentation est triviale, j'ai juste l'impression de faire un travail qui devrait être dans une bibliothèque standard. Une fonction de puissance robuste (c.-à-d. Gère le débordement d'une manière cohérente et explicite) n'est pas amusante à écrire.

À partir de C++11, des cas spéciaux ont été ajoutés à la suite de fonctions d'alimentation (et autres). C++11 [c.math] /11déclare, après avoir répertorié toutes les float/double/long doublesurcharges (mon emphase et paraphrasé):

De plus, il doit y avoir des surcharges supplémentaires suffisantes pour garantir que, si un argument correspondant à un doubleparamètre a un type doubleou un type entier, alors tous les arguments correspondant aux doubleparamètres sont effectivement convertis en double.

Donc, fondamentalement, les paramètres entiers seront mis à niveau en doubles pour effectuer l'opération.

Avant C++11(c'est-à-dire lorsque votre question a été posée), aucune surcharge d'entiers n'existait.

Comme je n'étais ni étroitement associé aux créateurs Cni C++à l'époque de leur création (bien que je sois plutôt vieux), ni membre des comités ANSI / ISO qui ont créé les normes, c'est forcément un avis de ma part. J'aimerais penser que c'est une opinion éclairée mais, comme ma femme vous le dira (souvent et sans grand besoin d'encouragement), je me suis trompé avant :-)

La supposition, pour ce qu'elle vaut, suit.

Je soupçonne que la raison pour laquelle le pré-ANSI original Cn'avait pas cette fonctionnalité est qu'elle était totalement inutile. Premièrement, il y avait déjà un très bon moyen de faire des puissances entières (avec des doubles et ensuite simplement une reconversion en entier, en vérifiant le dépassement et le sous-dépassement d'entiers avant la conversion).

Deuxièmement, une autre chose dont vous devez vous rappeler est que l'intention initiale Cétait en tant que langage de programmation de systèmes , et il est douteux que la virgule flottante soit souhaitable dans ce domaine.

Comme l'un de ses premiers cas d'utilisation était de coder UNIX, la virgule flottante aurait été presque inutile. BCPL, sur lequel C était basé, n'avait pas non plus besoin de pouvoirs (il n'avait pas du tout de virgule flottante, de mémoire).

En passant, un opérateur de puissance intégrale aurait probablement été un opérateur binaire plutôt qu'un appel de bibliothèque. Vous n'ajoutez pas deux entiers avec x = add (y, z)mais avec x = y + z- une partie du langage proprement dit plutôt que la bibliothèque.

Troisièmement, comme la mise en œuvre de la puissance intégrale est relativement triviale, il est presque certain que les développeurs du langage utiliseraient mieux leur temps pour fournir des éléments plus utiles (voir ci-dessous les commentaires sur le coût d'opportunité).

C'est également pertinent pour l'original C++. Étant donné que l'implémentation d'origine n'était en fait qu'un traducteur qui produisait du Ccode, elle reprenait de nombreux attributs de C. Son intention originale était C-avec-classes, pas C-avec-classes-plus-un-peu-de-extra-maths.

Quant à savoir pourquoi il n'a jamais été ajouté aux normes auparavant C++11, vous devez vous rappeler que les organismes de normalisation ont des lignes directrices spécifiques à suivre. Par exemple, l'ANSI a Cété spécifiquement chargé de codifier la pratique existante et non de créer un nouveau langage. Sinon, ils auraient pu devenir fous et nous donner Ada :-)

Les versions ultérieures de cette norme ont également des lignes directrices spécifiques et peuvent être trouvées dans les documents de justification (justification de la raison pour laquelle le comité a pris certaines décisions, et non justification du langage lui-même).

Par exemple, le C99document de justification reprend spécifiquement deux des C89principes directeurs qui limitent ce qui peut être ajouté:

• Gardez le langage petit et simple.
  
• Fournissez une seule façon de faire une opération.

Des lignes directrices (pas nécessairement celles spécifiques ) sont établies pour les groupes de travail individuels et limitent donc également les C++comités (et tous les autres groupes ISO).

De plus, les organismes de normalisation se rendent compte qu'il y a un coût d'opportunité (un terme économique signifiant ce que vous devez renoncer pour une décision prise) à chaque décision qu'ils prennent. Par exemple, le coût d'opportunité de l'achat de cette machine à sous-gamer à 10000 $ est des relations cordiales (ou probablement toutes les relations) avec votre moitié pendant environ six mois.

Eric Gunnerson explique bien cela avec son explication de -100 points sur la raison pour laquelle les choses ne sont pas toujours ajoutées aux produits Microsoft - en gros, une fonctionnalité commence à 100 points dans le trou, elle doit donc ajouter un peu de valeur pour être même considérée.

En d'autres termes, préféreriez-vous avoir un opérateur d'alimentation intégré (que, honnêtement, n'importe quel codeur à moitié décent pourrait créer en dix minutes) ou un multi-threading ajouté à la norme? Pour moi, je préférerais avoir ce dernier et ne pas avoir à me soucier des différentes implémentations sous UNIX et Windows.

J'aimerais également voir des milliers et des milliers de collections de la bibliothèque standard (hachages, btrees, arbres rouge-noir, dictionnaire, cartes arbitraires, etc.) mais, comme le dit la justification:

Une norme est un traité entre l'implémenteur et le programmeur.

Et le nombre de personnes chargées de la mise en œuvre dans les organismes de normalisation dépasse de loin le nombre de programmeurs (ou du moins ceux qui ne comprennent pas le coût d'opportunité). Si tout cela était ajouté, le prochain standard C++serait C++215xet serait probablement entièrement implémenté par les développeurs de compilateurs trois cents ans plus tard.

Quoi qu'il en soit, ce sont mes pensées (plutôt volumineuses) sur la question. Si seulement les votes étaient attribués en fonction de la quantité plutôt que de la qualité, je ferais bientôt sauter tout le monde hors de l'eau. Merci pour l'écoute :-)

Pour tout type intégral à largeur fixe, presque toutes les paires d'entrées possibles débordent de toute façon du type. Quelle est l'utilité de normaliser une fonction qui ne donne pas de résultat utile pour la grande majorité de ses entrées possibles?

Vous avez à peu près besoin d'un grand type entier pour rendre la fonction utile, et la plupart des grandes bibliothèques d'entiers fournissent la fonction.

Edit: Dans un commentaire sur la question, static_rtti écrit "La plupart des entrées provoquent un débordement? La même chose est vraie pour exp et double pow, je ne vois personne se plaindre." Ceci est une erreur.

Laissons de côté exp, parce que ce n'est pas la question (bien que cela rendrait mon cas plus fort), et concentrons-nous sur double pow(double x, double y). Pour quelle partie des paires (x, y) cette fonction fait-elle quelque chose d'utile (c'est-à-dire pas simplement débordement ou sous-débordement)?

En fait, je vais me concentrer uniquement sur une petite partie des paires d'entrée pour ce powqui a du sens, car cela suffira pour prouver mon point: si x est positif et | y | <= 1, alors powne déborde pas ou ne sous-déborde pas. Cela comprend près d'un quart de toutes les paires à virgule flottante (exactement la moitié des nombres à virgule flottante non NaN sont positifs et un peu moins de la moitié des nombres à virgule flottante non NaN ont une magnitude inférieure à 1). De toute évidence, il existe de nombreuses autres paires d'entrées pour lesquelles powdes résultats utiles sont produits, mais nous avons constaté qu'il s'agit d'au moins un quart de toutes les entrées.

Regardons maintenant une fonction de puissance entière de largeur fixe (c'est-à-dire non bignum). Pour quelle portion d'entrées ne déborde-t-il pas simplement? Pour maximiser le nombre de paires d'entrée significatives, la base doit être signée et l'exposant non signé. Supposons que la base et l'exposant ont tous les deux une nlargeur de bits. Nous pouvons facilement obtenir une limite sur la partie des entrées qui sont significatives:

• Si l'exposant 0 ou 1, alors n'importe quelle base est significative.
• Si l'exposant est égal ou supérieur à 2, aucune base supérieure à 2 ^ (n / 2) ne produit un résultat significatif.

Ainsi, sur les 2 ^ (2n) paires d'entrées, moins de 2 ^ (n + 1) + 2 ^ (3n / 2) produisent des résultats significatifs. Si nous regardons ce qui est probablement l'utilisation la plus courante, les entiers 32 bits, cela signifie que quelque chose de l'ordre de 1 / 1000e d'un pour cent des paires d'entrée ne déborde pas simplement.

Parce qu'il n'y a aucun moyen de représenter toutes les puissances entières dans un int de toute façon:

>>> print 2**-4
0.0625

C'est en fait une question intéressante. Un argument que je n'ai pas trouvé dans la discussion est le simple manque de valeurs de retour évidentes pour les arguments. Comptons les échecs de la int pow_int(int, int)fonction hypthétique .

1. Débordement
2. Résultat non défini pow_int(0,0)
3. Le résultat ne peut pas être représenté pow_int(2,-1)

La fonction a au moins 2 modes de défaillance. Les nombres entiers ne peuvent pas représenter ces valeurs, le comportement de la fonction dans ces cas devrait être défini par la norme - et les programmeurs devraient être conscients de la manière exacte dont la fonction gère ces cas.

Dans l'ensemble, laisser la fonction de côté semble être la seule option raisonnable. Le programmeur peut utiliser la version à virgule flottante avec tous les rapports d'erreur disponibles à la place.

Réponse courte:

Une spécialisation de pow(x, n)à où nest un nombre naturel est souvent utile pour les performances temporelles . Mais le générique de la bibliothèque standard pow()fonctionne toujours assez bien ( étonnamment! ) À cette fin et il est absolument essentiel d'en inclure le moins possible dans la bibliothèque C standard afin qu'elle puisse être rendue aussi portable et aussi facile à implémenter que possible. D'un autre côté, cela ne l'empêche pas du tout d'être dans la bibliothèque standard C ++ ou la STL, que je suis presque sûr que personne n'envisage d'utiliser dans une sorte de plate-forme embarquée.

Maintenant, pour la réponse longue.

pow(x, n)peut être rendu beaucoup plus rapide dans de nombreux cas en se spécialisant nsur un nombre naturel. J'ai dû utiliser ma propre implémentation de cette fonction pour presque tous les programmes que j'écris (mais j'écris beaucoup de programmes mathématiques en C). L'opération spécialisée peut être effectuée à O(log(n))temps, mais lorsqu'elle nest petite, une version linéaire plus simple peut être plus rapide. Voici les implémentations des deux:

    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }

(Je suis parti xet la valeur de retour est double parce que le résultat de pow(double x, unsigned n)va rentrer dans un double aussi souvent que possible pow(double, double).)

(Oui, pownc'est récursif, mais casser la pile est absolument impossible car la taille maximale de la pile sera à peu près égale log_2(n)et nest un entier. Si nest un entier de 64 bits, cela vous donne une taille de pile maximale d'environ 64. Aucun matériel n'a une telle extrême limitations de la mémoire, à l'exception de certains PIC douteux avec des piles matérielles qui ne font que 3 à 8 appels de fonction profonds.)

En ce qui concerne les performances, vous serez surpris de ce dont une variété de jardin pow(double, double)est capable. J'ai testé cent millions d'itérations sur mon IBM Thinkpad âgé de 5 ans avec xun nombre d'itérations négal à 10 et égal à 10. Dans ce scénario, j'ai pown_lgagné. la glibc a pow()pris 12,0 secondes utilisateur, pown7,4 secondes utilisateur et pown_lseulement 6,5 secondes utilisateur. Ce n'est donc pas trop surprenant. Nous nous attendions plus ou moins à cela.

Ensuite, j'ai laissé xêtre constant (je l'ai mis à 2,5), et j'ai bouclé nde 0 à 19 cent millions de fois. Cette fois, de façon assez inattendue, la glibc a powgagné, et par un glissement de terrain! Cela n'a pris que 2,0 secondes utilisateur. Mon a pownpris 9,6 secondes et a pown_lpris 12,2 secondes. Que s'est-il passé ici? J'ai fait un autre test pour le savoir.

J'ai fait la même chose que ci-dessus seulement avec xégal à un million. Cette fois, a powngagné à 9,6 secondes. pown_la pris 12,2s et la glibc pow a pris 16,3s. Maintenant, c'est clair! la glibc powfonctionne mieux que les trois quand elle xest basse, mais pire quand elle xest élevée. Lorsque xest élevé, pown_lfonctionne mieux lorsqu'il nest faible et pownfonctionne mieux lorsqu'il xest élevé.

Voici donc trois algorithmes différents, chacun capable de mieux fonctionner que les autres dans les bonnes circonstances. Ainsi, en fin de compte, ce qui à utiliser dépend probablement plus sur la façon dont vous prévoyez d'utiliser pow, mais en utilisant la bonne version est la peine, et ayant toutes les versions est agréable. En fait, vous pourriez même automatiser le choix de l'algorithme avec une fonction comme celle-ci:

double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}

Tant que x_expectedet n_expectedsont des constantes décidées au moment de la compilation, avec éventuellement d'autres mises en garde, un compilateur d'optimisation digne de ce nom supprimera automatiquement l' pown_autoappel de fonction entier et le remplacera par le choix approprié des trois algorithmes. (Maintenant, si vous voulez vraiment essayer d' utiliser ceci, vous devrez probablement jouer un peu avec, car je n'ai pas vraiment essayé de compiler ce que j'avais écrit ci-dessus.;))

D'un autre côté, la glibc pow fonctionne et la glibc est déjà assez grande. Le standard C est censé être portable, y compris vers divers périphériques embarqués (en fait, les développeurs embarqués du monde entier conviennent généralement que la glibc est déjà trop volumineuse pour eux), et il ne peut pas être portable si pour chaque fonction mathématique simple, il doit inclure tous les algorithme alternatif qui pourrait être utile. C'est pourquoi ce n'est pas dans la norme C.

note de bas de page: Lors des tests de performances temporelles, j'ai donné à mes fonctions des indicateurs d'optimisation relativement généreux ( -s -O2) qui sont susceptibles d'être comparables, sinon pires, à ce qui a probablement été utilisé pour compiler la glibc sur mon système (archlinux), donc les résultats sont probablement juste. Pour un test plus rigoureux, je devrais compiler moi-même la glibc et je n'ai vraiment pas envie de faire ça. J'utilisais Gentoo, donc je me souviens du temps que cela prend, même lorsque la tâche est automatisée . Les résultats sont assez concluants (ou plutôt peu concluants) pour moi. Vous êtes bien sûr les bienvenus pour le faire vous-même.

Tour de bonus: une spécialisation de pow(x, n)à tous les entiers est instrumentale si une sortie entière exacte est requise, ce qui se produit. Envisagez d'allouer de la mémoire pour un tableau à N dimensions avec p ^ N éléments. Obtenir p ^ N même par un entraînera un segfault éventuellement aléatoire.

L'une des raisons pour lesquelles C ++ n'a pas de surcharges supplémentaires est d'être compatible avec C.

C ++ 98 a des fonctions comme double pow(double, int), mais celles-ci ont été supprimées dans C ++ 11 avec l'argument que C99 ne les incluait pas.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#550

Obtenir un résultat légèrement plus précis signifie également obtenir un résultat légèrement différent .

Le monde est en constante évolution, tout comme les langages de programmation. La quatrième partie du C décimal TR ¹ ajoute quelques fonctions supplémentaires <math.h>. Deux familles de ces fonctions peuvent être intéressantes pour cette question:

• Les pownfonctions, qui prennent un nombre à virgule flottante et un intmax_texposant.
• Les powrfonctions, qui prennent deux nombres à virgule flottante ( xet y) et calculent xà la puissance yavec la formule exp(y*log(x)).

Il semble que les gars standard aient finalement jugé ces fonctionnalités suffisamment utiles pour être intégrées dans la bibliothèque standard. Cependant, le rationnel est que ces fonctions sont recommandées par la norme ISO / CEI / IEEE 60559: 2011 pour les nombres à virgule flottante binaires et décimaux. Je ne peux pas dire avec certitude quelle "norme" a été suivie à l'époque de C89, mais les évolutions futures de <math.h>seront probablement fortement influencées par les évolutions futures de la norme ISO / IEC / IEEE 60559 .

Notez que la quatrième partie du TR décimal ne sera pas incluse dans C2x (la prochaine révision majeure en C), et sera probablement incluse plus tard en tant que fonctionnalité facultative. Il n'y a eu aucune intention à ma connaissance d'inclure cette partie du TR dans une future révision C ++.

¹ Vous pouvez trouver une documentation sur les travaux en cours ici .

Peut-être parce que l'ALU du processeur n'a pas implémenté une telle fonction pour les entiers, mais il existe une telle instruction FPU (comme le souligne Stephen, c'est en fait une paire). Il était donc en fait plus rapide de lancer en double, d'appeler pow avec des doubles, puis de tester le dépassement et de le renvoyer, que de l'implémenter en utilisant l'arithmétique des entiers.

(d'une part, les logarithmes réduisent les puissances à la multiplication, mais les logarithmes d'entiers perdent beaucoup de précision pour la plupart des entrées)

Stephen a raison de dire que sur les processeurs modernes, ce n'est plus vrai, mais le standard C lorsque les fonctions mathématiques ont été sélectionnées (C ++ a juste utilisé les fonctions C) est maintenant quoi, 20 ans?

Voici une implémentation O (log (n)) vraiment simple de pow () qui fonctionne pour tous les types numériques, y compris les entiers :

template<typename T>
static constexpr inline T pown(T x, unsigned p) {
    T result = 1;

    while (p) {
        if (p & 0x1) {
            result *= x;
        }
        x *= x;
        p >>= 1;
    }

    return result;
}

C'est mieux que l'implémentation O (log (n)) d'énigmaticPhysicist car elle n'utilise pas la récursivité.

C'est aussi presque toujours plus rapide que son implémentation linéaire (tant que p> ~ 3) car:

• il ne nécessite aucune mémoire supplémentaire
• il ne fait que ~ 1,5 fois plus d'opérations par boucle
• il ne fait que ~ 1,25 fois plus de mises à jour de mémoire par boucle

En fait, c'est le cas.

Depuis C ++ 11, il existe une implémentation basée sur un modèle de pow(int, int)--- et même des cas plus généraux, voir (7) sur http://en.cppreference.com/w/cpp/numeric/math/pow

EDIT: les puristes peuvent argumenter que ce n'est pas correct, car il est en fait utilisé un typage «promu». D'une manière ou d'une autre, on obtient un intrésultat correct , ou une erreur, sur les intparamètres.

Une raison très simple:

5^-2 = 1/25

Tout dans la bibliothèque STL est basé sur les éléments les plus précis et les plus robustes imaginables. Bien sûr, le int reviendrait à zéro (à partir de 1/25) mais ce serait une réponse inexacte.

Je suis d'accord, c'est bizarre dans certains cas.