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

https://stackoverflow.com/questions/2398442

25-09-2019
|

Question

Je sens que je dois juste être incapable de le trouver. Y at-il raison que la fonction C pow de ne met pas en œuvre la fonction de « puissance » quoi que ce soit, sauf floats et doubles?

Je sais que la mise en œuvre est trivial, je me sens comme si je fais un travail qui devrait être dans une bibliothèque standard. Une fonction de forte puissance (d'une certaine manière cohérente, explicite à savoir poignées débordement) n'est pas amusant à écrire.

La solution

En fait, il le fait.

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

EDIT: les puristes peuvent faire valoir ce n'est pas correct, car il est en fait « promu » typage utilisé. D'une façon ou une autre, on obtient un résultat de int correct, ou une erreur, sur les paramètres int.

Autres conseils

Au C++11, des cas particuliers ont été ajoutés à la suite des fonctions de puissance (et d'autres). États C++11 [c.math] /11, après avoir énuméré toutes les surcharges float/double/long double (mon accent, et paraphrase):

De plus, il doit y avoir une surcharge supplémentaire suffisante pour assurer que, si un argument correspondant à un paramètre de double est de type double ou un type entier, alors tous les arguments correspondant à des paramètres double sont coulés à double efficacement.

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

Avant C++11 (qui était quand votre question a été posée), aucun entier existait une surcharge.

Depuis que je ne étroitement associé aux créateurs de C ni C++ dans les jours de leur création (si je h plutôt vieux), ni une partie des comités ANSI / ISO qui a créé les normes, c'est nécessairement l'opinion de ma part. Je voudrais penser que c'est informé opinion mais, comme ma femme vous dira (souvent et sans beaucoup d'encouragements nécessaires), je suis mal avant: -)

Supposition, pour ce que ça vaut, suit.

suspect que la raison pour laquelle le C pré-ANSI d'origine n'a pas cette fonctionnalité est parce qu'il était tout à fait inutile. Tout d'abord, il y avait déjà une très bonne façon de faire des puissances entières (avec doubles puis simplement retransférer un entier, la vérification de débordement d'entier et underflow avant la conversion).

En second lieu, une autre chose que vous avez à retenir est que l'intention initiale de C était comme systèmes langage de programmation, et on peut se demander si à virgule flottante est souhaitable dans cette arène du tout.

Depuis l'un de ses cas d'utilisation initiale était de coder UNIX, virgule flottante aurait été presque inutile. BCPL, sur laquelle C était fondée, aucune utilisation avait également des pouvoirs (il n'y avait pas du tout à virgule flottante, de la mémoire).

En aparté, un opérateur de puissance intégrale aurait probablement été un opérateur binaire plutôt que d'un appel de la bibliothèque. Vous n'ajoutez pas deux entiers avec x = add (y, z) mais avec x = y + z -. Partie du langue appropriée plutôt que la bibliothèque

En troisième lieu, depuis la mise en œuvre de la puissance intégrale est relativement trivial, il est presque certain que les développeurs de la langue serait mieux utiliser leur temps à fournir des choses plus utiles (voir ci-dessous les commentaires sur le coût d'opportunité).

C'est aussi pertinent pour l'C++ d'origine. Depuis la mise en œuvre originale était effectivement juste un traducteur qui a produit code C, il portait sur un grand nombre des attributs de C. Son intention initiale était de C avec classes, pas C avec classes-plus-un-peu-bit de-extra-mathématiques-stuff.

Quant à savoir pourquoi il n'a jamais été ajouté aux normes avant C++11, vous devez vous rappeler que les organismes de normalisation ont des directives spécifiques à suivre. Par exemple, la norme ANSI C a été spécifiquement chargé de codifier la pratique actuelle, pas pour créer une nouvelle langue. Dans le cas contraire, ils auraient pu fou et nous a donné Ada: -)

itérations ultérieures de cette norme ont également des directives spécifiques et se trouvent dans les documents de justification (les raisons pour lesquelles le comité a certaines décisions, la raison non de la langue elle-même).

Par exemple, le document de justification de C99 porte spécifiquement en avant deux des principes directeurs C89 qui limitent ce qui peut être ajouté:

Gardez la langue petite et simple.
Fournir une seule façon de faire une opération.

Directives (pas nécessairement celles spécifique les) sont fixées pour l'individudes groupes de travail et donc de limiter les comités de C++ (et tous les autres groupes ISO), ainsi.

En outre, les organismes de normalisation se rendent compte qu'il ya un coût d'opportunité (un terme économique qui signifie que vous devez renoncer à une décision) à toutes les décisions qu'ils font. Par exemple, le coût d'opportunité d'acheter que 10 000 $ la machine uber-jeu est des relations cordiales (ou probablement tous ) les relations avec l'autre moitié pendant environ six mois.

Eric Gunnerson explique bien avec ses -100 points explication pour expliquer pourquoi les choses ne sont pas toujours ajoutées à Microsoft produits- essentiellement une fonction commence 100 points dans le trou il doit ajouter un peu de valeur à même envisagée.

En d'autres termes, auriez-vous plutôt un opérateur de puissance intégrale (qui, honnêtement, tout codeur demi-décent pourrait fouetter en dix minutes) ou multi-threading ajouté à la norme? Pour ma part, je préfère avoir ce dernier et ne pas avoir à propos de les muck implémentations différentes sous UNIX et Windows.

Je voudrais aussi voir des milliers et des milliers de collection de la bibliothèque standard (hash, arbres, arbre binaire rouge-noir, dictionnaire, cartes arbitraires et ainsi de suite) mais aussi, comme l'indique logique:

Une norme est un traité entre l'exécution et programmeur.

Et le nombre de implémenteurs sur les organismes de normalisation dépassent largement le nombre de programmeurs (ou au moins les programmeurs qui ne comprennent pas le coût d'opportunité). Si ce genre de choses a été ajouté, la prochaine C++ norme serait C++215x et serait probablement pleinement mis en œuvre par les développeurs du compilateur trois cents ans après.

Quoi qu'il en soit, c'est mes pensées (assez volumineux) en la matière. Si seuls les votes ont été distribués bases sur la quantité plutôt que la qualité, je bientôt souffler tout le monde hors de l'eau. Merci pour votre écoute: -)

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

à peu près besoin d'avoir un grand type entier afin de 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 à cause de débordement est de même pour pow exp et double, je ne vois personne se plaindre? ». Ceci est incorrect.

Laissons de côté exp, parce que c'est à côté du point (bien qu'il serait en fait rendre mon cas plus fort), et se concentrer sur double pow(double x, double y). Pour quelle partie de (x, y) paires cette fonction ne fait quelque chose d'utile (à savoir, non seulement dépassement positif ou négatif)?

Je vais en fait de se concentrer uniquement sur une petite partie des paires d'entrée pour lesquelles pow est logique, parce que ce sera suffisant pour prouver mon point: si x est positif et | y | <= 1, pow ne déborde pas ou négatif. Cela comprend près d'un quart de toutes les paires à virgule flottante (exactement la moitié des chiffres non-NAN-virgule flottante sont positifs, et un peu moins de la moitié des chiffres non-NAN-virgule flottante dont la puissance est inférieure à 1). De toute évidence, il y a beaucoup d'autres paires d'entrée pour lesquelles pow produit des résultats utiles, mais nous avons vérifié qu'il est au moins un quart de toutes les entrées.

Voyons maintenant à une largeur fixe (à savoir non bignum) fonction de puissance entière. Pour quels intrants partie-t-il pas simplement trop-plein? Afin de maximiser le nombre de paires d'entrée significatives, la base doit être signé et l'exposant non signé. Supposons que la base et l'exposant sont tous deux des bits de n large. On peut facilement obtenir une borne sur la partie des données qui sont significatives:

Si l'exposant 0 ou 1, toute base est significative.
Si l 'exposant est 2 ou plus, alors pas de base supérieure à 2 ^ (n / 2) produit un résultat significatif.

Ainsi, parmi 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, entiers 32 bits, cela signifie que quelque chose de l'ordre de 1 / 1000ème d'un pour cent des paires d'entrée ne suffit pas déborder.

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

>>> print 2**-4
0.0625

C'est en fait une question intéressante. Un argument que je ne l'ai pas trouvé dans la discussion est le simple manque de valeurs de retour évidentes pour les arguments. Comptons les moyens de la fonction hypthetical de int pow_int(int, int) pourrait échouer.

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

La fonction comporte au moins 2 modes de défaillance. Entiers ne peut pas représenter ces valeurs, le comportement de la fonction dans ces cas devront être définis par la norme -. Et les programmeurs doivent être conscients de la façon dont exactement la fonction gère ces cas

Dans l'ensemble en laissant la fonction hors semble que 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ù n est un nombre naturel est souvent utile pour performances de temps . Mais le pow() générique de bibliothèque standard fonctionne encore assez ( étonnamment! ) bien à cet effet et il est absolument essentiel d'inclure aussi peu que possible dans la bibliothèque standard C de sorte qu'il peut être aussi portable et aussi facile à mettre en œuvre possible. D'autre part, cela ne l'empêche pas du tout d'être dans la bibliothèque standard C ou de la STL, que je suis sûr que personne envisage d'utiliser dans une sorte de plate-forme embarquée.

Maintenant, pour la longue réponse.

pow(x, n) peut être 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 tous les programmes que j'écris (mais j'écrire beaucoup de programmes mathématiques en C). L'opération spécialisée peut se faire dans le temps O(log(n)), mais quand n est petite, une version linéaire simple peut être plus rapide. Voici les mises en œuvre à la fois:


    // 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 x et la valeur de retour en double parce que le résultat de pow(double x, unsigned n) se tenir dans un double à peu près aussi souvent que pow(double, double) sera.)

(Oui, pown est récursive, mais casser la pile est absolument impossible car la taille maximale de la pile sera à peu près égale log_2(n) et n est un entier. Si n est un entier de 64 bits, qui vous donne une taille maximale de la pile d'environ 64. Non matériel a des limitations de mémoire extrêmes, à l'exception de certains pays insulaires du Pacifique avec du matériel louches des piles qui ne vont 3 à 8 appels de fonction profonde.)

En ce qui concerne la performance, vous serez surpris par ce que une pow(double, double) variété de jardin est capable. Je l'ai testé une centaine de millions d'itérations sur mon-5 ans avec IBM Thinkpad x égal au nombre d'itérations et n égal à 10. Dans ce scénario, pown_l gagné. glibc pow() a pris 12,0 secondes de l'utilisateur, pown a pris 7,4 secondes d'utilisateur et pown_l a pris seulement 6,5 secondes de l'utilisateur. Donc, ce n'est pas trop surprenant. Nous avons été plus ou moins attendions.

Alors, je laisse x être constant (je l'ai mis à 2,5), et je mis en boucle n de 0 à 19 une centaine de millions de fois. Cette fois, tout à fait inattendue, pow glibc a gagné, et par un glissement de terrain! Il a fallu seulement 2,0 secondes utilisateur. Mon pown a pris 9,6 secondes, et pown_l a pris 12,2 secondes. Que s'est-il passé ici? Je l'ai fait un autre test pour le savoir.

Je l'ai fait la même chose que ci-dessus qu'avec x égale à un million. Cette fois-ci, pown a gagné à 9,6 secondes. pown_l a 12.2s et glibc Pow a 16.3s. Maintenant, il est clair! glibc pow fonctionne mieux que les trois quand x est faible, mais le pire quand x est élevé. Lorsque x est élevé, pown_l fonctionne mieux lorsqu'il est n est faible, et pown meilleures performances lorsque x est élevé.

Voici donc trois algorithmes différents, chacun capable d'exécuter mieux 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 la peine, 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);
}

Tant que x_expected et n_expected sont des constantes déterminées au moment de la compilation, avec peut-être quelques autres mises en garde, un compilateur optimisant la valeur de son sel supprimera automatiquement l'ensemble de l'appel de la fonction pown_auto et le remplacer par le choix approprié des troisalgorithmes. (Maintenant, si vous allez réellement essayer de utiliser , vous aurez probablement à jouer avec un peu, parce que je ne cherche pas exactement compilation ce que je « d écrit ci-dessus;.))

D'autre part, glibc pow ne fonctionne et glibc est assez grand déjà. La norme C est censé être portable, y compris à divers périphériques embarqués (en fait les développeurs embarqués partout conviennent généralement que la glibc est déjà trop grand pour eux), et il ne peut pas être portable si pour tout simplement fonction mathématique dont il a besoin d'inclure tous les autre algorithme que peut être utiles. Donc, c'est pourquoi il est pas dans la norme C.

note: Dans les essais de performances en temps, j'ai donné mes fonctions drapeaux d'optimisation relativement généreux (-s -O2) qui sont susceptibles d'être comparables, sinon pire, que ce qui était probablement utilisé pour compiler glibc sur mon système (ArchLinux), donc les résultats sont probablement juste. Pour un test plus rigoureux, je dois compiler me glibc et I reeeally ne se sentent pas envie de faire ça. Je l'habitude d'utiliser Gentoo, donc je me rappelle le temps qu'il faut, même si la tâche est automatisé . Les résultats sont concluants (ou plutôt peu concluante) assez pour moi. Vous êtes bien sûr les bienvenus de le faire vous-même.

Bonus round: Une spécialisation de pow(x, n) à tous les entiers est instrumental si une sortie entier exacte est nécessaire, ce qui ne se produit. Considérons l'allocation de mémoire pour une matrice à N dimensions avec des éléments p ^ N. Obtenir p ^ N off même par un entraînera une peut se produire au hasard segfault.

L'une des raisons pour C ++ de ne pas avoir d'autres est de surcharges être compatible avec C.

C ++ 98 a des fonctions comme double pow(double, int), mais ceux-ci ont été enlevés en C ++ 11 avec l'argument selon lequel C99 ne les a pas inclus.

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

Obtenir un résultat un peu plus précis signifie aussi obtenir un peu différent résultat.

Le monde est en constante évolution et sont donc les langages de programmation. Le quatrième partie de la virgule C TR ¹ ajoute quelques autres fonctions à <math.h>. Deux familles de ces fonctions peuvent être d'intérêt pour cette question:

Les fonctions de pown, qui prend un nombre à virgule flottante et un exposant de intmax_t.
Les fonctions de powr, qui prend deux nombres de points flottants (x et y) et calculer x au y d'alimentation avec la formule exp(y*log(x)).

Il semble que les gars standards finalement jugé que ces caractéristiques assez utiles pour être intégrées dans la bibliothèque standard. Cependant, le rationnel est que ces fonctions sont recommandées par le ISO / IEC / IEEE 60559: 2011 standard pour les nombres à virgule flottante binaire et décimal. Je ne peux pas dire avec certitude ce que « standard » a été suivi au moment de C89, mais les évolutions futures de <math.h> seront probablement fortement influencées par les évolutions futures du ISO / IEC / IEEE 60559 Standard .

Notez que la quatrième partie de la TR décimale ne sera pas inclus dans C2x (la prochaine grande révision C), et sera probablement inclus plus tard en option. Il n'y a pas eu d'intention que je connaisse d'inclure cette partie du TR dans une future révision ++ C.

Vous pouvez ¹ trouver un travail en cours .

Peut-être parce que le processeur de ALU n'a pas mis en œuvre une telle fonction pour les entiers, mais il y a une telle instruction FPU (comme Stephen souligne, il est en fait une paire). Donc, il était en fait plus rapide de jeter doubler, appelez pow avec double, puis effectuez un test pour trop-plein et rejetterait, que de le mettre en œuvre en utilisant l'arithmétique entier.

(pour une chose, logarithmes réduire les pouvoirs à la multiplication, mais logarithmes des nombres entiers perdent beaucoup de précision pour la plupart des entrées)

Stephen est vrai que sur les processeurs modernes, ce ne l'est plus, mais la norme C lorsque les fonctions mathématiques ont été sélectionnés (C ++ seulement utilisé les fonctions C) est maintenant ce que, 20 ans?

A raison très simple:

5^-2 = 1/25

Tout dans la bibliothèque STL est basée sur la plus précise, des choses robustes imaginables. Bien sûr, l'int retournerait à zéro (de 1/25), mais ce serait une réponse inexacte.

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

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow