Le moyen le plus efficace pour mettre en œuvre une puissance entière selon la fonction pow (int, int)

Question

Ce qui est le moyen le plus efficace donné à soulever un entier à la puissance d’un autre entier en C ?

Answer 1

Exponentiation par quadrature.

Il s’agit de la méthode standard pour faire l’exponentiation modulaire pour un nombre considérable de cryptographie asymétrique.

Answer 2

Notez que l'exponentiation par la quadrature n'est pas la meilleure méthode. Il est probablement le meilleur que vous pouvez faire en tant que méthode générale qui fonctionne pour toutes les valeurs d'exposant, mais pour une valeur d'exposant il y a peut être une meilleure séquence qui a besoin de moins de multiplications.

Par exemple, si vous voulez calculer x^15, la méthode d'exponentiation par la 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 le "juste" 5 multiplications.

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

Je ne me souviens pas de la source, mais je me souviens vaguement qu'il n'existe pas d'algorithmes efficaces pour trouver cette séquence optimale des multiplications.

Answer 3

Exponentiation par quadrature peut être utile de jeter un coup d’oeil à.

Answer 4

Voici la méthode en Java

Answer 5

int pow( int base, int exponent)
{
    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);
}