Le moyen le plus efficace pour implémenter une fonction de puissance basée sur des nombres entiers pow (int, int)

Quelle est la manière la plus efficace donnée pour élever un entier à la puissance d'un autre entier en C?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

Exponentiation par quadrature.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

Il s'agit de la méthode standard pour effectuer l'exponentiation modulaire pour des nombres énormes en cryptographie asymétrique.

Notez que l' exponentiation par quadrature n'est pas la méthode la plus optimale. C'est probablement le mieux que vous puissiez faire en tant que méthode générale qui fonctionne pour toutes les valeurs d'exposant, mais pour une valeur d'exposant spécifique, il peut y avoir une meilleure séquence qui nécessite moins de multiplications.

Par exemple, si vous voulez calculer x ^ 15, la méthode d'exponentiation par quadrature vous donnera:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

C'est un total de 6 multiplications.

Il s'avère que cela peut être fait en utilisant "seulement" 5 multiplications via l' exponentiation de la chaîne d'addition .

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

Il n'y a pas d'algorithmes efficaces pour trouver cette séquence optimale de multiplications. De Wikipédia :

Le problème de trouver la chaîne d'addition la plus courte ne peut pas être résolu par la programmation dynamique, car elle ne satisfait pas à l'hypothèse d'une sous-structure optimale. Autrement dit, il ne suffit pas de décomposer la puissance en puissances plus petites, chacune étant calculée de façon minimale, car les chaînes d'addition pour les petites puissances peuvent être liées (pour partager les calculs). Par exemple, dans la chaîne d'addition la plus courte pour a¹⁵ ci-dessus, le sous-problème pour a⁶ doit être calculé comme (a³) ² car a³ est réutilisé (par opposition à, disons, a⁶ = a² (a²) ², qui nécessite également trois multiplications ).

Si vous devez augmenter 2 à une puissance. Le moyen le plus rapide de le faire est de décaler les bits par la puissance.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

Voici la méthode en Java

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp & 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}

Si vous voulez obtenir la valeur d'un entier pour 2 élevé à la puissance de quelque chose, il est toujours préférable d'utiliser l'option shift:

pow(2,5) peut être remplacé par 1<<5

C'est beaucoup plus efficace.

power()fonction pour travailler uniquement avec des nombres entiers

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

Complexité = O (log (exp))

power()fonction pour fonctionner avec une base exp et négative flottante .

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

Complexité = O (log (exp))

Un cas extrêmement spécialisé est, lorsque vous avez besoin de dire 2 ^ (- x au y), où x, bien sûr, est négatif et y est trop grand pour faire un décalage sur un int. Vous pouvez toujours faire 2 ^ x en temps constant en vissant avec un flotteur.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

Vous pouvez obtenir plus de pouvoirs de 2 en utilisant un double comme type de base. (Merci beaucoup aux commentateurs d'avoir aidé à corriger ce message).

Il y a aussi la possibilité que d'en savoir plus sur les flotteurs IEEE , d'autres cas spéciaux d'exponentiation pourraient se présenter.

Tout comme un suivi des commentaires sur l'efficacité de l'exponentiation par quadrature.

L'avantage de cette approche est qu'elle s'exécute en temps log (n). Par exemple, si vous deviez calculer quelque chose d'énorme, tel que x ^ 1048575 (2 ^ 20 - 1), vous n'avez qu'à parcourir la boucle 20 fois, pas 1 million + en utilisant l'approche naïve.

De plus, en termes de complexité du code, c'est plus simple que d'essayer de trouver la séquence de multiplications la plus optimale, comme le suggère la Pramod.

Éditer:

Je suppose que je devrais clarifier avant que quelqu'un m'étiquette pour le potentiel de débordement. Cette approche suppose que vous avez une sorte de bibliothèque de type énorme.

Tard à la fête:

Vous trouverez ci-dessous une solution qui traite également du y < 0mieux qu'elle peut.

1. Il utilise un résultat de intmax_tpour une portée maximale. Il n'y a aucune disposition pour les réponses qui ne correspondent pas intmax_t.
2. powjii(0, 0) --> 1ce qui est un résultat courant pour ce cas.

3. pow(0,negative), un autre résultat indéfini, renvoie INTMAX_MAX

   intmax_t powjii(int x, int y) {
     if (y < 0) {
       switch (x) {
         case 0:
           return INTMAX_MAX;
         case 1:
           return 1;
         case -1:
           return y % 2 ? -1 : 1;
       }
       return 0;
     }
     intmax_t z = 1;
     intmax_t base = x;
     for (;;) {
       if (y % 2) {
         z *= base;
       }
       y /= 2;
       if (y == 0) {
         break; 
       }
       base *= base;
     }
     return z;
   }

Ce code utilise une boucle for(;;)pour toujours pour éviter le base *= basecommun final dans d'autres solutions en boucle. Cette multiplication est 1) non nécessaire et 2) pourrait être un int*intdébordement qui est UB.

solution plus générique considérant exponenet négatif

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

Une autre implémentation (en Java). Peut ne pas être la solution la plus efficace mais le nombre d'itérations est le même que celui de la solution exponentielle.

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

    if(exp % 2 == 0){
        long half = pow(base, exp/2);
        return half * half;
    }else{
        long half = pow(base, (exp -1)/2);
        return base * half * half;
    }       
}

J'utilise récursif, si l'exp est pair, 5 ^ 10 = 25 ^ 5.

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

En plus de la réponse d'Elias, qui provoque un comportement indéfini lorsqu'il est implémenté avec des entiers signés et des valeurs incorrectes pour une entrée élevée lorsqu'il est implémenté avec des entiers non signés,

voici une version modifiée de l'exponentiation par quadrature qui fonctionne également avec les types entiers signés et ne donne pas de valeurs incorrectes:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

Considérations pour cette fonction:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

En cas de débordement ou d'emballage, return 0;

J'ai utilisé int64_t, mais n'importe quelle largeur (signée ou non signée) peut être utilisée avec peu de modifications. Cependant, si vous devez utiliser un type entier à largeur non fixe, vous devrez changer SQRT_INT64_MAXpar (int)sqrt(INT_MAX)(dans le cas de l'utilisation int) ou quelque chose de similaire, qui devrait être optimisé, mais il est plus laid et non une expression constante C. Le fait de convertir le résultat de sqrt()en un intn'est pas très bon à cause de la précision en virgule flottante dans le cas d'un carré parfait, mais comme je ne connais aucune implémentation où INT_MAX-ou le maximum de tout type- est un carré parfait, vous pouvez vivre avec ça.

J'ai implémenté un algorithme qui mémorise toutes les puissances calculées et les utilise ensuite en cas de besoin. Ainsi, par exemple, x ^ 13 est égal à (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x où x ^ 2 ^ 2 il a été extrait du tableau au lieu de le calculer à nouveau. Il s'agit essentiellement de l'implémentation de la réponse @Pramod (mais en C #). Le nombre de multiplication nécessaire est Ceil (Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

Mon cas est un peu différent, j'essaie de créer un masque à partir d'une puissance, mais j'ai pensé partager la solution que j'ai trouvée de toute façon.

Évidemment, cela ne fonctionne que pour des puissances de 2.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;

Si vous connaissez l'exposant (et il s'agit d'un entier) au moment de la compilation, vous pouvez utiliser des modèles pour dérouler la boucle. Cela peut être rendu plus efficace, mais je voulais démontrer le principe de base ici:

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

Nous terminons la récursivité en utilisant une spécialisation de modèle:

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

L'exposant doit être connu au moment de l'exécution,

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}