problem calculating N^N

[ayan2587]

Hello guyz !!!
I came across this problem and I am still unable to come up with a good algorithm to solve this problem

Problem :
given, 1<=n<=1000000, and 1<=k<=9 , calculate the first and last k digits of n^n.

for example if n=13 and k=4, then
result : first 4 digits ->3028
last 4 digits ->2253

since the value of 13^13= 302875106592253

I do realize that it is not feasible to calculate the actual value of n^n, since for n=1000000, it takes up a lot of time and is not the correct method.

So, someone please suggest another suitable method to solve this.

[Krstevski]

You can't calculate N^N if N is bigger than 13 because the result of 13^13 is out of range.
More about data types range.

You can try with BigInteger Library or you can use char array to find the result of N^N (calculating char by char).

Anyway, I hate tasks with calculating big number. :/

[mrnutty]

For this, read up on Modular exponentiation. Using that technique, will help you solve this problem.

[ayan2587]

For this, read up on Modular exponentiation. Using that technique, will help you solve this problem.

Hi...thanks for the information.
Could you please give a small example..because I can't seem to understand how the use of modulus will be helpful in solving this problem.

[VernonDozier]

This is a math problem, first and foremost, more than a computer science problem. As you correctly mentioned, you don't want to calculate n^n. Even if you could use BigInteger (and you may be able to), I imagine that misses the point of the math problem, which is that you can throw out a whole bunch of digits or simplify things in some other way. Calculating the LAST k digits looks far easier than calculating the FIRST k digits, so I would tackle that one first. This looks like one of those pencil/paper/calculator exercises before you even touch the computer.

[gashtio]

As firstPerson said, the last digits can be obtained by modular exponentiation.
Getting the first digits requires some mathematical trickery, but nothing too special.

I've commented the code so it shouldn't be hard to understand.

#include <cstdio>
#include <cmath>
typedef unsigned int UINT;
typedef unsigned long long ULL;

//--------------------------------------------------------------------------------------
// Calculates a^n mod k
//--------------------------------------------------------------------------------------
UINT modexp( UINT a, UINT n, UINT k )
{
	//	using the fact that (a*b) % m = ((a%m) * (b%m)) % m:
	//
	//		 	 |	1				n = 0
	//	a^n % m	=	<	( (a%m) * ((a^(n-1))%m) ) % m	n is odd
	//		 	 |	(a^2 % m)^(n/2) % m		n is even

	// promote a and k to 64-bit integers,
	// since we need to calculate squares of 32-bit ints
	ULL base = a;
	ULL mod = k;

	ULL res = 1;
	while ( n > 0 )
	{
		if ( n & 1 ) // n is odd
			res = (res * base) % mod;

		n /= 2;
		base = (base * base) % mod;
	}

	return (UINT)res; // after taking the modulo, res fits nicely into an UINT
}

UINT get_last_k( UINT a, UINT n, UINT k )
{
	UINT mod = 1;
	while ( k-- ) mod *= 10; // 10^k

	return modexp( a, n, mod ); // last k digits of a^n = a^n % 10^k
}

//--------------------------------------------------------------------------------------
// Calculates the first k digits of a^n
//--------------------------------------------------------------------------------------
//#define log10(x) log(x)/log(10.0)

UINT get_first_k( UINT a, UINT n, UINT k )
{
	//	a^n = 10^( log10(a^n) ) = 10^( n * log10(a) )
	//
	//	for any real number f with integer part a and fractional part b (b = 0,...),
	//	10^f = 10^(a+b) = 10^a * 10^b = 10^b * 1000..., meaning that the
	//	first k digits of 10^f are the first k digits of 10^b.
	//	For any b such that 0 <= b < 1, 10^b has a non-zero digit for its integer part,
	//	so the first k digits of 10^f are the single digit in 10^b's integer part,
	//	and k-1 more from its fractional part. Thus we obtain the answer:
	//	
	//	first k digits of a^n = 10^(b + k-1)

	double intpart;
	return (UINT)floor( pow( 10.0, modf( n * log10((double)a), &intpart ) + k - 1 ) );
}

//--------------------------------------------------------------------------------------
// Entry point
//--------------------------------------------------------------------------------------
int main()
{
	// note that k must be strictly less than 10, because we're using 32-bit integers
	UINT a = 123123, n = 123123, k = 9;

	printf( "%u\t%u\n", get_first_k( a, n, k ), get_last_k( a, n, k ) );

	return 0;
}

Here's something for checking the results :) : http://www.wolframalpha.com/input/?i=123123^123123

[ayan2587]

Thnx buddy...
ur post was of a lot of help.. :)

As firstPerson said, the last digits can be obtained by modular exponentiation.
Getting the first digits requires some mathematical trickery, but nothing too special.

I've commented the code so it shouldn't be hard to understand.

#include <cstdio>
#include <cmath>
typedef unsigned int UINT;
typedef unsigned long long ULL;

//--------------------------------------------------------------------------------------
// Calculates a^n mod k
//--------------------------------------------------------------------------------------
UINT modexp( UINT a, UINT n, UINT k )
{
	//	using the fact that (a*b) % m = ((a%m) * (b%m)) % m:
	//
	//		 	 |	1				n = 0
	//	a^n % m	=	<	( (a%m) * ((a^(n-1))%m) ) % m	n is odd
	//		 	 |	(a^2 % m)^(n/2) % m		n is even

	// promote a and k to 64-bit integers,
	// since we need to calculate squares of 32-bit ints
	ULL base = a;
	ULL mod = k;

	ULL res = 1;
	while ( n > 0 )
	{
		if ( n & 1 ) // n is odd
			res = (res * base) % mod;

		n /= 2;
		base = (base * base) % mod;
	}

	return (UINT)res; // after taking the modulo, res fits nicely into an UINT
}

UINT get_last_k( UINT a, UINT n, UINT k )
{
	UINT mod = 1;
	while ( k-- ) mod *= 10; // 10^k

	return modexp( a, n, mod ); // last k digits of a^n = a^n % 10^k
}

//--------------------------------------------------------------------------------------
// Calculates the first k digits of a^n
//--------------------------------------------------------------------------------------
//#define log10(x) log(x)/log(10.0)

UINT get_first_k( UINT a, UINT n, UINT k )
{
	//	a^n = 10^( log10(a^n) ) = 10^( n * log10(a) )
	//
	//	for any real number f with integer part a and fractional part b (b = 0,...),
	//	10^f = 10^(a+b) = 10^a * 10^b = 10^b * 1000..., meaning that the
	//	first k digits of 10^f are the first k digits of 10^b.
	//	For any b such that 0 <= b < 1, 10^b has a non-zero digit for its integer part,
	//	so the first k digits of 10^f are the single digit in 10^b's integer part,
	//	and k-1 more from its fractional part. Thus we obtain the answer:
	//	
	//	first k digits of a^n = 10^(b + k-1)

	double intpart;
	return (UINT)floor( pow( 10.0, modf( n * log10((double)a), &intpart ) + k - 1 ) );
}

//--------------------------------------------------------------------------------------
// Entry point
//--------------------------------------------------------------------------------------
int main()
{
	// note that k must be strictly less than 10, because we're using 32-bit integers
	UINT a = 123123, n = 123123, k = 9;

	printf( "%u\t%u\n", get_first_k( a, n, k ), get_last_k( a, n, k ) );

	return 0;
}

Here's something for checking the results :) : http://www.wolframalpha.com/input/?i=123123^123123