Obtenir x élevé à la puissance n

Question

Je suis un débutant et je sais que ce programme C que j'ai obtenu quelque part sur Internet (crédits : http://www.geeksforgeeks.org/archives/28 ) fonctionne correctement.

#include<stdio.h>

float power(float x, int y)
{
    float temp;
    if( y == 0)
       return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
    {
        if(y > 0)
            return x*temp*temp;
        else
            return (temp*temp)/x;
    }
}

/* Program to test function power */
int main()
{
    float x=2;
    int y=5;
    printf("%f", power(x, y));
    getchar();
    return 0;
}

Je me demande simplement comment et pourquoi. J'ai posé mes questions/remarques dans un commentaire après la ligne de mon code dans cette fonction...

float temp;
if( y == 0)
   return 1; 
       //this I understand because for instance 2^0 is 1
temp = power(x, y/2);
if (y%2 == 0)
    return temp*temp; 
        //if y is even, eg. 2^4 then 2^2 * 2^2 is still equal to 16
else
{
    if(y > 0) 
        //this part I don't get anymore. eg. 2^5, then temp=2^(5/2)
        return x*temp*temp; 
            //2 * 2^(5/2) * 2^(5/2) how? this will become 64 but the answer is 32.
            //but when I run the program it halts the right answer ie, 32
    else
        return (temp*temp)/x;
}

Veuillez m'expliquer ce qui s'est passé. J'ai peut-être raté quelque chose. Et aussi comment c'est devenu un O(lg n) durée. Nous vous remercions de votre attention.

Answer 1

Il convient de noter que le y/2 utilisée pour calculer la température est entier division. Ainsi, dans les questions que vous avez commentées, le résultat de 5/2 sera 2, et non 2,5.

Answer 2

/* if y is even and positive, e.g., 5, then floor of y/2 is (y-1)/2, e.g. 4/2
   then x^((y-1)/2 + (y-1)/2 + 1) = x^y, e.g., x * x^2 * x^2 = x^(1+2+2) = x^5) */
if(y > 0) 
    return x*temp*temp; 

/* if y is even and negative, e.g., -5, then floor of y/2 is (y+1)/2, e.g. -4/2
   then x^((y+1)/2 - (y+1)/2 - 1) = x^y, e.g., x^-1 * x^-2 * x^-2 = x^(-1-2-2) = x^-5) */

else
    return (temp*temp)/x;

En ce qui concerne la complexité O(lgn), puisque vous divisez par 2 avant chaque appel à la puissance récursive, vous ferez lg(n) appels au maximum.

Answer 3

Il s'agit d'une mise en œuvre quelque peu maladroite de la méthode habituelle x n qui quadrille x de façon répétée tout en divisant par deux n. Odd n nécessite une manipulation supplémentaire : À chaque étape, il faut vérifier si n est impair et multiplier un autre facteur.

---

Alexander Stepanov's 1 très belle série de conférences sur les algorithmes génériques/modèles explique l'origine de celle-ci :

Il provient de l'ancien algorithme égyptien pour multiplier par addition répétée tout en divisant par deux. n .

Le premier cours commence par des choses assez faciles, mais il se poursuit. Il a des apartés et des histoires amusantes. Il commence par un algo récursif pour la multiplication par addition répétée, et l'affine de diverses manières. Il en arrive au point de remplacer + par * pour créer cet algo d'exponentiation vers la fin de l'exposé 2 (sur 4) .

---

1 : Stepanov a conçu et mis en œuvre une grande partie du STL de C++. Il a été l'un des tout premiers inventeurs/pionniers de la programmation générique. J'ai apprécié ses conférences et je les recommande.

---

Cette mise en œuvre particulière ne me semble pas très satisfaisante.

Je n'y ai pas réfléchi, mais il y a sûrement une meilleure façon de gérer les impairs négatifs. n que la division. Il s'agit peut-être d'une bizarrerie du sens d'arrondi pour la division d'entiers en C ? (C'est différent d'un décalage arithmétique vers la droite, même sur les implémentations C qui effectuent un décalage arithmétique pour les divisions entières). >> sur un opérande signé. La norme C ne l'exige pas, mais dans certaines implémentations C spécifiques, le comportement est défini).

En outre, les noms des variables sont trompeurs : normalement, on s'attend à ce que le nom de la variable soit y pour avoir le même type que x . Si vous mélangez des variables entières et des variables FP, utilisez des noms tels que n pour les entiers.

Answer 4

private int nthPower(int num, int power)
    {
        int [] arr = new int[power+1];
        arr[0] = 1; // Any number to the power '0' is '1'
        arr[1] = num; // Any number to the power '1' is num itself.
        int i =2;
        //Now in the for loop you just fill the next element in the array 
        // by multiplying the num with its previous result. Once you are out 
        // of loop you have the desired answer in 'i-1' th index.
        for (i =2; i<=power;i++)
        {
            arr[i] = num*arr[i-1];
        }
        return arr[i-1]; //This is your answer
    }