Given a function $\sum_{i=-N}^N{c_i x^i}$:$f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$. The constant $c_0$ is desired, and we start with only $f(x)$ and $N$.  $N$ is $\Theta(2^{b})$ for some $b$.Can you clarify?First, we start with a closed form of a function.  The function itself is similar to a generating function, so that the function description is usually more concise than a list of all of its coefficients, yet it describes all of the coefficients.  Some examples are$\frac{1-x^{100}}{1-x} = 1 + x + x^2 + ... + x^{99}$$\frac{ 1 - (n+1)x^n + nx^{n+1} }{ (x-1)^2 } = 1 + 2x + 3x^2 + ... + (n+1)x^n$The problem seems to be that this coefficient is in the middle of a list of positive and negative coefficients.  In the two examples above, the coefficient c_0 can be easily extracted.  However, this is not so when there are negative coefficients.  For example, take the functions above and divide by x^m to get a function that contains some negative coefficients.What is known about the general form of $f(x)$?The function $f(x)$ is a rational function:$f(x) = P(x)/Q(x)$where $P(x)$ and $Q(x)$ are polynomials.Here's a little insight into how $f(x)$ is calculated.I use a standard rational function:$g(x) = (x^s(x^t-1)) / ((x-1)(x^u+1))$I then multiply $g(x)$ by $g(y)$, and $g(y)$ is of the same form of $g(x)$, but in another variable.  I then possibly subtract this from a function of one coefficients:$h(xy) = (1-(x y)^v) / (1-x y)$I then use another variable function similar to $g(x)$, say $g(z)$, and multiply again.  Possibly subtract again.  Repeat this until the function I want is constructed.  Then reassign variables like so (to either positive or negative exponents):$y \mapsto \displaystyle x^{\pm 2^N}$$z \mapsto \displaystyle (x^{\pm 2^N})*(x^{\pm 2^N})$and so on.  This is how the function is created, without going into detail.How fast can this computation be performed?So far, I've seen that Bruno Salvy's webpage hosts a gfun package that solves this in O(N).I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better.  I imagine that a bounds related to the length of the function description may be possible...
What is/are the lower bounds for finding a something akin to complex residue?
lower bounds;algebra