/*-------------------------------------------------------*/
/* puissances d'un entier, méthodes naïve et dichotomique*/
/*----------------LG novembre 2004-----------------------*/
/*-------------------------------------------------------*/

#include<stdio.h>

int puiss_naive(int x, int n)
{
  int i;
  int res = 1;
  for (i=0;i<=n-1;i++)
    {
      res = res * x;
    }
  return res;
}


int puiss_dicho(int x, int n)
{
  int  k,puiss,res;
  if (n==0) 
    {return 1;}
  else
    {
      if (n==1)
	{
	  return x;
	}
      else
	{
	  res = 1;
	  puiss = x;
	  k=n;
	  while(k>1)
	    {
	      if (k%2 == 1) 
		{
		  res =res*puiss;
		}
	      puiss = puiss*puiss;
	      k = k/2;
	    }
	  return res*puiss;
	}
    }
}

int main(void)
{
  printf("%d puissance %d = %d\n",2,4,puiss_naive(2,4));
/*écrit  2 puissance 4 = 16 */

  printf("%d puissance %d = %d\n",2,4,puiss_dicho(2,4));
/*écrit  2 puissance 4 = 16 */

  return 0;
}