Thursday, January 12, 2012

Write a program to calculate M^N where M & N are two integer number

#include<iostream>
#include<string>
using namespace std;
#define MAX 50005


char num1[MAX] , temp[MAX];


//function to find the multiplication of two string number
void squaremulti(char num2[])
{
char num3[MAX] = {0};
long i ,j ,k ,rem ,a ,b;


//here num1 and num2 is multiplied and num3 keeps them
for(i = 0;num2[i]!='\0';i++)
{
k =i; rem = 0;
for(j = 0;num1[j]!='\0';j++)
{
b = num3[k] - '0';
if(num3[k] == '\0') b = 0;
a = b+(num2[i]-'0')*(num1[j]-'0')+rem;
num3[k] = a%10+'0';
k+=1; rem = a/10;
}
if(rem>0)
{
num3[k] = rem+'0';
k+=1;
}
num3[k] = '\0';
}


//num1 is assigned the final result
for(i = 0; ; i++)
{
num1[i] = num3[i];
if(num3[i]=='\0') break;
}
}


//recursive function strexp takes only log(N) steps
//this function divide the power into two part in
//every stepsand then call squaremulti to find the
//multiplication of the the two numbers with same power


void strexp(long pow)
{
if(pow == 0) return ;
else if(pow%2==0)
{
strexp(pow/2);
squaremulti(num1);
}
else
{
if(pow-1==0) return ;
strexp(pow-1);
if(pow-1==0) return ;
squaremulti(temp);
}
}




int main()
{
long pow,len;
//give string number and long int number


while(scanf(" %s %ld" ,num1 , &pow)==2)
{
   len = strlen(num1);
reverse(&num1[0],num1[len]);
strcpy(temp , num1);


//send the power to recursive function
strexp(pow);
//num1 is the result array
reverse(num1);
printf("%s" , num1);
printf("\n");
}
return 0;
}
/*
Input:
2 10
3 23
12 3
Output:
1024
94143178827
1728
*/

No comments:

Post a Comment