how to find sum efficiently

[hello1036]

somebody please tell me the efficient program to calculate

0 ^(n) + 1^(n) + 2^(n) + . . . . . . . . . . . . . . . . .+ k^(n)

k<=10^(9)

[Ganado]

http://mathworld.wolfram.com/PowerSum.html

[zapshe]

double pow(int base, int num) //Function To Calculate Power
{
	if (num == 0)
		return 1;
	else
	return base * (pow(base, num - 1));
}

int main()
{
	int n = 2; //Change This As Needed
	double answer = 0;
	for (int k = 0; k <= pow(10, 9); k++)
	{
		answer += pow(k, n);
	}
	std::cout << answer;
}

Understand that this may quickly overflow the variable.

[jonnin]

while the answer is likely NOT to use pow, pow stinks. write an efficient integer power routine and it will be significantly faster; the built in one is doing stuff for floating point exponents that you don't need to do.
assuming, of course, they ARE integers :) (zapshe did this for you, but didn't say why. )

my microscopic contribution would be to start at 2, though.
0 to any power being zero, unless the power is zero -- trivial cases.
1 to any power is 1, including zero. so unless power is zero you can start at 2 in that loop (and answer at 1 of course)

but again, brute force is not the way .. consider:
the sum of the first n cubes is the square of the sum of the first n natural numbers.
now google Faulhaber's formula to see how that was found.

this one is pretty quick. you can eliminate the upper terms if your powers are small, in practice you can usually cut from 16+ out. It isnt significantly faster than the above or a flat loop, just amusing.

long long ipow(long long p, unsigned long long e) //fast for big powers (> 8)
{ 
  const long long one = 1;
  const long long *lut[2] = {&p,&one};
  register long long result = 1;
    result *= lut[!(e&1)][0]; p *= p;
	result *= lut[!(e&2)][0]; p *= p;
	result *= lut[!(e&4)][0]; p *= p;
	result *= lut[!(e&8)][0]; p *= p;
	result *= lut[!(e&16)][0]; p *= p;
	result *= lut[!(e&32)][0]; p *= p;
	result *= lut[!(e&64)][0]; 	
	return result;
}