Power Series Evaluation

Power series evaluation in O(lg(n)):[n is the number of terms]

We'll try to evaluate the following power series in logarithmic time w.r.t. the number of terms n.


Well well... I may be asked, "dude, why do you want to do this in O(lg(n)) when there's already we have a O(1) solution for your problem?". Answer is simple, "I'm trying it from a programming perspective and the O(1) can get sometimes impossible when n keeps going up i.e. like 10¹⁰⁰⁰ and you are asked to return the answer w.r.t. some %m [modulus m] (meaning the final result will not reach m). This method will be suitable for this case only. Because, calculating {(x^n-1-1)/(x-1)}%m is not a very easy task and sometimes, it is not directly possible.

This series can be evaluated by binary splitting and recursively solving those building up the answer.
Let n = 6
We have, 1 + x + x² + x³ + x⁴ + x⁵
⇒ (1 + x + x²) + x³(1 + x + x²)
⇒ (1 + x + x²)(1 + x³)

So, when n is even, f(x, n) = (1 + x^n/2)f(x, n/2)

Now, what if n is odd, Let n = 7
We have, 1 + x + x² + x³ + x⁴ + x⁵ + x⁶
⇒ (1 + x + x²) + x³(1 + x + x²) + x⁶
⇒ (1 + x + x²)(1 + x³) + x⁶

So, when n is odd, f(x, n) = (1 + x^n/2)f(x, n/2) + x^n-1

So, by combining the above 2 equations, we get the final solution:
f(x, n) = (1 + x^n/2)f(x, n/2) + (n%2)x^n-1

By some clever observation, the need for -1 and %2 operation on n can be eliminated. So, the only thing we need to do is the /2 operation on n, which is easy even when n is a big integer.

Here is a python module that shows only the recursive part, no trick applied.

import math

def evaluate(x, n):
    if(n==0):
        return 0
    if(n==1):
        return 1
    ret = 0
    if(n%2==1):
        ret = ret + int(math.pow(x, n-1))
    n = n/2
    return ret + evaluate(x, n)*(1 + int(math.pow(x, n)))

If this is to be done with C/C++, some biginteger division algorithm should be implemented.

Easy, eh? Check different types of series here