### 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

This series can be evaluated by binary splitting and recursively solving those building up the answer.

Let n = 6

We have, 1 + x + x

⇒ (1 + x + x

⇒ (1 + x + x

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

Now, what if n is odd, Let n = 7

We have, 1 + x + x

⇒ (1 + x + x

⇒ (1 + x + x

So, when n is odd, f(x, n) = (1 + x

So, by combining the above 2 equations, we get the final solution:

f(x, n) = (1 + x

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.

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

Easy, eh? Check different types of series here

**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**^{1000}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

^{2}+ x^{3}+ x^{4}+ x^{5}⇒ (1 + x + x

^{2}) + x^{3}(1 + x + x^{2})⇒ (1 + x + x

^{2})(1 + x^{3})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

^{2}+ x^{3}+ x^{4}+ x^{5}+ x^{6}⇒ (1 + x + x

^{2}) + x^{3}(1 + x + x^{2}) + x^{6}⇒ (1 + x + x

^{2})(1 + x^{3}) + x^{6}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

can u clarify me ?

ReplyDeletewhen n is odd i simplfy

do for F(n)=F(n-1)+A^n

So F(n-1) will follow the recurrence for n is even

Is this correct?

yep... we will always try to make odds to even. so that we can divide. its the similar idea of successive squaring exponentiation algorithm.

ReplyDeleteany problem link??

ReplyDeletehttps://algo.codemarshal.org/problems/556def2d3bbbaa0300a964ce

Delete1 + 2a + 3a^2 +4a^3 + 5a^4 + . . . + na^(n-1) mod M

ReplyDeleteIs this also possible O(lg(n)) time?

That can be solve in O(n) by Horner's method. :)

Deletehttps://en.wikipedia.org/wiki/Horner's_method

-------------------------------------------------

int res = 0;

for(int i = n; i > 0; --i)

{

res = (res * a + i) % M;

}

printf("%d\n", res);

But in this recursive relation if we have n as large as given in the question(10e1000) then can we find that large number in python.

ReplyDelete