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

pour tout type intégral à Largeur fixe, presque toutes les paires d'entrées possibles débordent le type, de toute façon. À quoi bon normaliser une fonction qui ne donne pas un résultat utile pour la grande majorité de ses entrées possibles?

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

modifier: 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 incorrect.

laissons de côté exp , parce que c'est hors de propos (bien que cela rendrait mon cas plus fort), et se concentrer sur double pow(double x, double y) . Pour quelle portion des paires (x,y) cette fonction fait-elle quelque chose d'utile (c.-à-d. pas simplement déborder ou sous-traiter)?

je suis en fait va se concentrer uniquement sur une petite partie des paires d'entrées pour lesquelles pow a du sens, parce que cela suffira à prouver mon point: si x est positif et |y| <= 1, alors pow ne déborde pas ou ne déborde pas. Cela représente près du quart de tous les couples à 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 y a beaucoup de autres paires d'entrées pour lesquelles pow produit des résultats utiles, mais nous avons constaté qu'il s'agit d'au moins un quart de tous les entrées.

regardons maintenant une fonction de puissance à Largeur fixe (i.e. non-bignum). Pour quelle portion inputs ne déborde-t-il pas tout simplement? Pour maximiser le nombre de paires d'entrées significatives, la base doit être signée et l'exposant non signé. Supposons que la base et l'exposant sont à la fois n bits large. Nous pouvons facilement obtenir une limite sur le partie des intrants qui sont significatives:

• si l'exposant 0 ou 1, alors n'importe quelle base est significative.
• si l'exposant est 2 ou plus, alors aucune base plus grande que 2^(n/2) produit un résultat significatif.

ainsi, sur les paires d'entrées 2^(2n), moins de 2^(n+1) + 2^(3n/2) produisent des résultats significatifs. Si nous regardons ce qui est probablement l'usage le plus commun, entiers de 32 bits, cela signifie que quelque chose sur l'ordre de 1 / 1000ème de un pour cent des paires d'entrées ne débordent pas simplement.

parce qu'il n'y a aucun moyen de représenter toutes les puissances entières dans un sens:

>>> 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 façons dont la fonction hyphétique int pow_int(int, int) pourrait échouer.

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

cette fonction comporte au moins deux modes de défaillance. Les 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 façon dont exactement la fonction gère ces cas.

dans l'ensemble, laisser la fonction en dehors semble être la seule option raisonnable. Le programmeur peut utiliser la version floating point avec tous les rapports d'erreur disponibles à la place.

courte réponse:

une spécialisation de pow(x, n) à où n est un nombre naturel est souvent utile pour performance de temps . Mais le générique pow() de la bibliothèque standard fonctionne encore assez bien ( étonnamment! ) et il est absolument essentiel d'inclure le moins possible dans la bibliothèque standard C pour qu'elle soit aussi portable et facile à mettre en œuvre que possible. Sur le d'un autre côté, cela ne l'empêche pas du tout d'être dans la bibliothèque standard C++ ou le STL, que je suis presque sûr que personne ne prévoit d'utiliser dans une sorte de plate-forme intégrée.

maintenant, pour la longue réponse.

pow(x, n) peut être rendu beaucoup plus rapide dans de nombreux cas en se spécialisant n à un nombre naturel. J'ai dû utiliser ma propre mise en œuvre de cette fonction pour presque chaque programme que j'écris (mais j'écris beaucoup de programmes mathématiques en C). L'opération spécialisée peut être effectuée en temps O(log(n)) , mais lorsque n est petit, 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;
    }

(j'ai quitté x et la valeur de retour comme doubles parce que le résultat de pow(double x, unsigned n) tiendra dans un double environ aussi souvent que pow(double, double) .)

(Oui, pown est récursif, mais casser la pile est absolument impossible puisque le la taille maximale de la pile sera approximativement égale à log_2(n) et n est un entier. Si n est un entier 64 bits, cela vous donne une taille de pile maximale d'environ 64. Non hardware a de telles limites de mémoire extrêmes, à l'exception de quelques PICs douteux avec des piles de matériel qui vont seulement 3 à 8 appels de fonction profonde.)

pour ce qui est de la performance, vous serez surpris par ce qu'une variété de jardin pow(double, double) est capable de faire. J'ai testé une centaine de millions itérations sur Mon IBM Thinkpad de 5 ans avec x égale au numéro d'itération et n égale à 10. Dans ce scénario, pown_l a gagné. glibc pow() a pris 12,0 secondes utilisateurs, pown a pris 7,4 secondes utilisateurs, et pown_l a pris seulement 6,5 secondes utilisateurs. Ce n'est donc pas trop surprenant. Nous nous y attendions plus ou moins.

ensuite, j'ai laissé x être constant (Je l'ai mis à 2,5), et j'ai bouclé n de 0 à 19 une centaine de millions temps. Cette fois, de façon tout à fait inattendue, glibc pow gagné, et par un glissement de terrain! Il a fallu seulement 2,0 utilisateur secondes. Mon pown a pris 9,6 secondes, et pown_l 12,2 secondes. Ce qui s'est passé ici? J'ai fait un autre test pour le savoir.

j'ai fait la même chose que ci-dessus mais avec x égal à un million de dollars. Cette fois, pown a gagné à 9,6 S. pown_l a pris 12,2 s et glibc pow 16,3 S. Maintenant, c'est clair! glibc pow fonctionne mieux que le trois lorsque x est faible, mais le pire lorsque x est élevé. Lorsque x est forte", 1519190920" donne les meilleurs résultats lorsque n est faible, et pown donne les meilleurs résultats lorsque x est élevé.

voici donc trois algorithmes différents, chacun capable de fonctionner mieux que les autres dans les bonnes circonstances. Donc, en fin de compte, ce qui à utiliser dépend très probablement de la façon dont vous prévoyez d'utiliser pow , mais en utilisant la bonne version est vaut le coup, et ayant toutes les versions est agréable. En fait, vous pouvez même automatiser le choix de l'algorithme avec une fonction comme ceci:

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);
}

aussi longtemps que x_expected et n_expected sont des constantes décidées au moment de la compilation, avec éventuellement d'autres mises en garde, un compilateur optimisant qui vaut sa peine supprimera automatiquement la totalité de l'appel de fonction pown_auto et le remplacera par le choix approprié des trois algorithme. (Maintenant, si vous allez réellement essayer de utiliser ceci, vous aurez probablement à jouer avec un peu, parce que je n'ai pas exactement essayé compiler ce que j'avais écrit ci-dessus. ;))

d'autre part, glibc pow ne fonctionne et glibc est déjà assez grand. La norme C est censée être portable, y compris à divers dispositifs encastrés (en fait les développeurs embedded partout conviennent généralement que glibc est déjà trop grand pour eux), et il ne peut pas être portable si pour chaque fonction mathématique simple, il doit inclure tous les algorithmes alternatifs que pourrait être d'utilisation. Donc, c'est pourquoi il n'est pas dans la norme.

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

tour Bonus: A la spécialisation de pow(x, n) à tous les entiers est instrumental si une sortie entière exacte est nécessaire, ce qui se produit. Envisager l'attribution de mémoire pour un réseau n-dimensionnel avec des éléments P^N. L'obtention de p^N même par entraînera éventuellement aléatoires erreur de segmentation.

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 en 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 aussi obtenir un légèrement différent résultat.

peut-être parce que L'ALU du processeur n'a pas implémenté une telle fonction pour les entiers, mais il y a une telle instruction FPU (comme Stephen le souligne, c'est en fait une paire). Donc, il était en fait plus rapide de lancer pour doubler, appel pow avec doubles, puis tester pour débordement et mouler en arrière, que de mettre en œuvre en utilisant arithmétique entière.

(pour une chose, les logarithmes réduisent les pouvoirs à la multiplication, mais les logarithmes des 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++ vient d'utiliser les fonctions C) est maintenant quoi, 20 ans?

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

• les fonctions pown , qui prennent un nombre de virgule flottante et un exposant intmax_t .
• les fonctions powr , qui prend deux nombres de points flottants ( x et y ) et calculer x à la puissance y avec la formule exp(y*log(x)) .

il semble que les standard guys ont finalement jugé ces fonctionnalités suffisamment utiles pour être intégrées dans la bibliothèque standard. Cependant, le raisonnement est que ces fonctions sont recommandées par la ISO/IEC/IEEE 60559:2011 norme pour les nombres binaires et décimaux à virgule flottante. Je ne peux pas dire certes, 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 de la TR décimale ne sera pas incluse dans C2x (la prochaine révision c majeure), et sera probablement incluse plus tard comme une fonctionnalité optionnelle. Il n'y a pas eu d'intention que je sache d'inclure cette partie du TR dans un futur c++ révision.

1 Vous pouvez trouver de la documentation ici .

en fait, oui.

depuis c++11 Il y a un modèle d'implémentation de pow(int, int) - - - et même des cas plus généraux, voir (7) en http://en.cppreference.com/w/cpp/numeric/math/pow

une raison très simple:

5^-2 = 1/25

tout dans la bibliothèque STL est basé sur la substance la plus précise, robuste imaginable. Bien sûr, l'int retournerait à zéro (à partir de 1/25), mais ce serait une réponse inexacte.

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