Saturday, December 12, 2009

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 101000 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 {(xn-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 + x2 + x3 + x4 + x5
⇒ (1 + x + x2) + x3(1 + x + x2)
⇒ (1 + x + x2)(1 + x3)

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

Now, what if n is odd, Let n = 7
We have, 1 + x + x2 + x3 + x4 + x5 + x6
⇒ (1 + x + x2) + x3(1 + x + x2) + x6
⇒ (1 + x + x2)(1 + x3) + x6

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

So, by combining the above 2 equations, we get the final solution:
f(x, n) = (1 + xn/2)f(x, n/2) + (n%2)xn-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

7 comments:

  1. can u clarify me ?
    when 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?

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

    ReplyDelete
  3. Replies
    1. https://algo.codemarshal.org/problems/556def2d3bbbaa0300a964ce

      Delete
  4. 1 + 2a + 3a^2 +4a^3 + 5a^4 + . . . + na^(n-1) mod M
    Is this also possible O(lg(n)) time?

    ReplyDelete
    Replies
    1. That can be solve in O(n) by Horner's method. :)
      https://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);

      Delete
  5. 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