Finding the sum x ^ k from k = 0 to n in O (logn) time

Question

So my question is how to do this in C more specifically. I know that O (logn) usually means that we will use recursion, as if breaking one of the parameters.

What I'm trying to achieve is the sum from k = 0 to n from x ⁿ . for example, exponent_sum (x, n) will be parameters in this case.

Then

exponent_sum(4, 4) would be 4 ⁰ + 4 ¹ + 4 ² + 4 ³ + 4 ⁴ = 341.

I'm not sure where to start. Some tips will be really appreciated.

Answer 1

One way to look at the sum is a number in the base x, consisting of all 1s.

For example, 4 ⁴ + 4 ³ + 4 ² + 4 ¹ + 4 ⁰ is 11111 in base 4.

In any database, a line of 1s will be equal to 1, followed by a line of the same number 0s, minus 1 divided by the base minus 1.

For instance,

• in base 10: (1000 - 1) / 9 = 999/9 = 111
• in base 16: (0x10000 - 1) / 0xF = 0xFFFF / 0xF = 0x1111
• in base 8: (0100 - 1) / 7 = 077/7 = 011

etc.

So, put them together, and we can generalize that

exponent_sum (x, n) = (x ^{(n + 1)} - 1) / (x - 1)

For example, exponent_sum (4, 4) = (4 ⁵ - 1) / 3 = 1023/3 = 341

So the big complexity of O for him will be the same as for computing x ⁿ

Answer 2

Let me add one more proof for completeness:

s = 1 + x ¹ + x ² + ... + x ⁿ

Then

xs = x (1 + x ¹ + x ² + ... + x ⁿ ) = x ¹ + x ² + ... + x ⁿ + x ^{n + 1} = s - 1 + x ^{n + 1}

Solution for s

(x - 1) s = x ^{n + 1} - 1,

s = (x ^{n + 1} - 1) / (x - 1)

Answer 3

Another way to see the solution is this: suppose that the sum S written as

 S = 1 + x + x^2 + ... + x^k 

Then, if we multiply both sides of this by x , we get

 S*x = x * (1 + x + x^2 + ... + x^k) = x + x^2 + ... + x^k + x^(k+1) 

then add 1 to both sides

 S*x + 1 = 1 + x + x^2 + ... + x^k + x^(k+1) = (1 + x + x^2 + ... + x^k) + x^(k+1) = S + x^(k+1) 

which means

 S*x - S = x^(k+1) - 1 S*(x - 1) = x^(k+1) - 1 

So

 S = (x^(k+1) - 1) / (x - 1) 

Answer 4

Use the theory of geometric progression. Where

 sum = (first-term(pow(common-ratio,number-of-terms)-1))/(common-ratio-1); here first-term is obviously 1; Common-ratio= number itself; number-of-terms=number+1; 

But the general ratio should be greater than 1; For

 Common-ratio=1; Sum=number*number-of-terms. 

Answer 5

You can directly estimate the amount without using the geometric progression formula. This has the advantage that division is not required (which is necessary if, for example, you want to adapt the code to return the result modulo some large number).

Let S (k) be the sum x ^ 0 + ... + x ^ {k-1}, it satisfies these recurrence relations:

 S(1) = 1 S(2n) = S(n) * (1 + x^n) S(2n+1) = S(n) * (1 + x^n) + x^{2n} 

Using them, the only difficulty is to keep the current xp value for use as x ^ n. Otherwise, the algorithm is very similar to the upward implementation of squaring.

 #include <inttypes.h> #include <stdio.h> #include <stdint.h> int64_t exponent_sum(int64_t x, int64_t k) { int64_t r = 0, xp = 1; for (int i = 63; i >= 0; i--) { r *= 1 + xp; xp *= xp; if (((k + 1) >> i) & 1) { r += xp; xp *= x; } } return r; } int main(int argc, char *argv[]) { for (int k = 0; k < 10; k++) { printf("4^0 + 4^1 + ... + 4^%d = %" PRId64 "\n", k, exponent_sum(4, k)); } return 0; }