/*---------------------------------------------------------------------------
File name: pow.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/22/2007 17:47:04
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

Post: pow(a, b): can we do it iteratively using lgn multiplications?

Following code calculates a^b using lgn multiplications. But it is recursive.

Question:

Can we do it using a loop?

Don't use a stack to convert recursion into iteration, 'coz that does not solve
the problem.
*/

#include <stdio.h>

/**
Calculates a^b using lgn multiplications.
*/
int pow(int a, int n)
{
int t;

if(n==0)
return 1;

t=pow(a, n/2);
t*=t;
if(n&1)
t*=a;

return t;
}

int main()
{
int a=3, i;

for(i=0; i<21; ++i)
printf("%d\n", pow(a, i));

return 0;
}