/* fastmult.c
   demonstrates fast multiplication by recursion
   Richard Kay 29 April 1999 */

#include <stdio.h>
#include <conio.h>

double power(double, long int);
int level=0;

int main(void){
  double result,num;
  long int p;
  printf("enter a number and an (positive int) power to raise it to\n");
  scanf("%lf%ld",&num,&p);
  result=power(num,p);
  printf("the result is %15.6lf\n",result);
  printf("press a key to continue\n");
  getch();
  return 0;
}

double power(double x, long int n){
  /* raises a number to a power with smallest possible
     number of multiplications */
  double a;
  int oldlevel;
  printf("level of recursion on entry is %d\n",++level);
  oldlevel=level;
  printf("n is %ld\n",n);
  getch();
  if(n==1) return x;
  a=power(x,n/2);
  printf("the value returned by power is %10.6lf \n",a);
  printf("the level of recursion on exit is %d\n",oldlevel);
  getch();
  if (n%2) return x*a*a;
  return a*a;
}