pow() semble être dépassé d'une unité ici.

Question

Ce qui se passe ici :

#include <stdio.h>
#include <math.h>
int main(void) {
    printf("17^12 = %lf\n", pow(17, 12));
    printf("17^13 = %lf\n", pow(17, 13));
    printf("17^14 = %lf\n", pow(17, 14));
}

J'obtiens ce résultat :

17^12 = 582622237229761.000000
17^13 = 9904578032905936.000000
17^14 = 168377826559400928.000000

13 et 14 ne correspondent pas à wolfram alpa cf :

12: 582622237229761.000000
    582622237229761

13: 9904578032905936.000000
    9904578032905937

14: 168377826559400928.000000
    168377826559400929

De plus, elle n'est pas fausse d'une fraction étrange - elle est fausse d'exactement un !

Si c'est parce que j'ai atteint les limites de ce que je peux faire. pow() peut faire pour moi, existe-t-il une alternative qui puisse calculer cela ? J'ai besoin d'une fonction qui puisse calculer x^y où x^y est toujours inférieur à ULLONG_MAX.

Answer 1

pow travaille avec double nombres. Ceux-ci représentent des nombres de la forme s * 2^e où s est un entier de 53 bits. Par conséquent, double peut stocker tous les entiers inférieurs à 2^53, mais seulement un peu de les nombres entiers supérieurs à 2^53. En particulier, il ne peut représenter que les nombres pairs > 2^53, puisque pour e > 0 la valeur est toujours un multiple de 2.

17^13 nécessite 54 bits pour être représenté exactement, donc e est mis à 1 et donc la valeur calculée devient un nombre pair. La valeur correcte est impaire, il n'est donc pas surprenant qu'elle soit décalée de 1. De même, 17^14 nécessite 58 bits pour être représenté. Le fait qu'il soit également différent de 1 est une coïncidence heureuse (tant que vous n'appliquez pas trop la théorie des nombres), il se trouve qu'il est différent de 1 par rapport à a. multiple de 32 qui est la granularité à laquelle double Les nombres de cet ordre de grandeur sont arrondis.

Pour l'exponentiation exacte d'un nombre entier, vous devez utiliser des nombres entiers dans tous les cas. Écrivez votre propre double -routine d'exponentiation libre. Utilisez l'exponentiation au carré si y peut être grande, mais je suppose qu'elle est toujours inférieure à 64, ce qui rend ce problème discutable.

Answer 2

Les nombres que vous obtenez sont trop grands pour être représentés par un chiffre. double avec précision. Un nombre à virgule flottante à double précision possède essentiellement 53 chiffres binaires significatifs et peut représenter tous les entiers jusqu'à 2^53 ou 9.007.199.254.740.992.

Pour les nombres plus élevés, les derniers chiffres sont tronqués et le résultat de votre calcul est arrondi au nombre suivant qui peut être représenté sous forme de double . Pour 17^13 qui n'est que légèrement supérieur à la limite, c'est le nombre pair le plus proche. Pour les nombres supérieurs à 2^54 c'est le nombre le plus proche qui est divisible par quatre, et ainsi de suite.

Answer 3

Si vos arguments en entrée sont des entiers non négatifs, vous pouvez implémenter votre propre pow .

De manière récursive :

unsigned long long pow(unsigned long long x,unsigned int y)
{
    if (y == 0)
        return 1;
    if (y == 1)
        return x;
    return pow(x,y/2)*pow(x,y-y/2);
}

De manière itérative :

unsigned long long pow(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y--)
        res *= x;
    return res;
}

Efficacement :

unsigned long long pow(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y > 0)
    {
        if (y & 1)
            res *= x;
        y >>= 1;
        x *= x;
    }
    return res;
}

Answer 4

Un petit complément aux autres bonnes réponses : sous l'architecture x86, il y a généralement une disponibilité x87 format étendu 80-bit qui est supporté par la plupart des compilateurs C via la fonction long double type. Ce format permet d'opérer avec des nombres entiers allant jusqu'à 2^64 sans lacunes.

Il existe un analogue de pow() sur <math.h> qui est destiné à fonctionner avec long double numéros - powl() . Il convient également de noter que le spécificateur de format pour le fichier long double est autre que pour double les - %Lf . Donc le programme correct utilisant le long double ressemble à ceci :

#include <stdio.h>
#include <math.h>
int main(void) {
    printf("17^12 = %Lf\n", powl(17, 12));
    printf("17^13 = %Lf\n", powl(17, 13));
    printf("17^14 = %Lf\n", powl(17, 14));
}

Comme Stephen Canon l'a noté dans les commentaires, il n'y a aucune garantie que ce programme donne un résultat exact.