<p>I don't have time to go into detail now, but here's a quick sketch of how to solve it. Let's assume that all of your polynomials look like $x^k-1$. What you have to do is use the identity $x^k-1 = (x-1)(1+x+x^2+\ldots + x^{k-1})$. You are starting with the function $\frac{\Pi_{i=1}^n (x^{k_i}-1)}{\Pi_{i=1}^m (x^{\ell_i}-1)}$. Now, factor out all the $(x-1)$ terms and take the limit. If $n >m$, you get $0$. If $n \lt m$, you get $\infty$. Otherwise, the $x-1$ terms cancel out, and what you're left with is $\frac{\Pi_{i=1}^nk_i}{\Pi_{i=1}^n\ell_i}$.</p>

CC BY-SA 2.5
2010-10-26T03:50:57.900Z
2010-10-26T03:56:44.560Z
2010-10-26T03:56:44.560Z
Peter Shor 
<p>I'm interested in finding the running time(s) for determining mathematical limits.</p>

<p>For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$.</p>

<p>I'd like to know more about algorithms for determining mathematical limits such as this, and I'm primarily concerned with the runtimes of such algorithms.</p>

<p>If it helps, there are only certain types of limits that I'm concerned with.</p>

<p>Specifically, I'm concerned with limits of one variable.  I'm also really only concerned with rational functions of polynomials.  For example, given two polynomials $p(x)$ and $q(x)$, I'm interested in finding the limit $\lim_{x \to 1}\frac{p(x)}{q(x)}$.</p>

<p>There is additional information that should greatly help.  I only really want to find the limit as $x$ approaches 1.  Further, the limit itself is bounded $-O(2^n) \leq \lim_{x \to 1} \leq O(2^n)$.</p>

<p>The function $p/q$ itself is actually a description of a polynomial with powers at most $O(2^n)$, and coefficients $c_i \in {-1, 0, 1}$.</p>

<p>This may not be the best method, but I'm essentially trying to sum the coefficients of a polynomial.</p>

<blockquote>
  <p>An Additional Interest</p>
</blockquote>

<p>I'm also interested in expanding the problem to include limits of rational functions of multiple polynomials, i.e. polynomials $p_i(x)$ and $q_j(x)$ to find:</p>

<p>$\lim_{x \to 1}\frac{\prod_{i=0}^m{p_i(x)}}{\prod_{j=0}^n{q_j(x)}}$</p>

<p>Note that the polynomials $p_i(x)$ and $q_j(x)$ are very sparse in this representation, consisting of no more than 2 terms.</p>

CC BY-SA 2.5
2010-10-24T15:45:30.377Z
Using l'Hopital's rule, if you have degree $n$ polynomials with $t$ terms, taking a limit involves differentiating at most $n$ times, which should take something like $O(nt)$ steps, ignoring issues of big integer arithmetic. By the way, your example is incorrect. And knowing the type of limit you're concerned with definitely helps ... I'm not even sure the question has an answer without this information.
Peter Shor 
CC BY-SA 2.5
2010-10-24T15:53:28.507Z
Thanks Peter.  I'm not sure I know what you mean by type of limit.  I'd like to find the limit as $x$ approaches $c$ from either side.  Also, The coefficients of the polynomials are cyclical in nature, so I'm helping that this may help.
Matt Groff
CC BY-SA 2.5
2010-10-24T16:17:22.743Z
Are $p,q \in Z[x]$? So your questions is what is the time complexity of the following problem: "Given $p(x),q(x) \in Z[x]$, compute $\lim_{x \to c} \frac{p(x)}{q(x)}$".
Kaveh
CC BY-SA 2.5
2010-10-24T16:29:50.817Z
So you are given a polynomial $r(x) = \frac{p(x)}{q(x)}$ implicitly as $p(x)$,$q(x)$ and you want to compute the value of $r(1)$.
Kaveh
CC BY-SA 2.5
2010-10-24T16:35:31.497Z
@Kaveh: Yes. I forgot to mention that all powers $t$ of the polynomial are withing the range $0 \leq t \leq O(2^n)$.
Matt Groff
CC BY-SA 2.5
2010-10-24T16:48:24.170Z
@Matt: I didn't mean type of limit. I meant type of expression for which you're finding the limit.
Peter Shor 
CC BY-SA 2.5
2010-10-24T18:19:28.133Z
Just one more clarification question, what is the representation of the polynomials $p(x)$,$q(x)$ given? Are you giving the coefficients of all monomials, or just nonzero ones, or are you giving them in some more compressed way? Note that a special case is when $q(x)=1$, so evaluation a polynomial is a special case. Also what is $n$?
Kaveh
CC BY-SA 2.5
2010-10-24T18:56:43.010Z
The monomials $p(x)$ and $q(x)$ will be in the product form at the bottom of the question.  The monomials $p_i(x)$ and $q_j(x)$ will contain only nonzero coefficients.  I tried to use $n$ to compare powers and results.  The powers of $x$ are related to the range of the result by $n$.
Matt Groff
CC BY-SA 2.5
2010-10-25T17:53:49.090Z
This seems like a classical question in numerical analysis. Nothing to do with tcs...
Sariel Har-Peled
CC BY-SA 2.5
2010-10-25T17:55:13.307Z
@Matt: If the polynomials are in product form, you can separate them into polynomials for which $p_i(1)=0$ and for which $p_i(1) \neq 0$, and then try to use l'Hopital's rule for the ones which evaluate to 0. If each of them has no more than two terms, and contain only nonzero coefficients, does that mean that they all have degree 1, or do you maen something else by that?
Peter Shor 
CC BY-SA 2.5
2010-10-25T21:13:52.293Z
@Peter: I can be very specific in this case - they will all have the form $\pm 1 \pm x^{2^n}$ for some integer $n$.  I guess the large powers of x make naively plugging in values look pretty good.
Matt Groff
CC BY-SA 2.5
2010-10-25T22:45:06.237Z
@Matt: I think this means we should be able to solve your problem quite easily. Unfortunately, I don't have time to write up an answer right now.
Peter Shor 
<cc.complexity-theory><lower-bounds><time-complexity><upper-bounds><polynomials>
What is the running time of taking a limit?
Matt Groff
# What is the running time of taking a limit?

(Asked by: username_0 on 2010-10-24)

I'm interested in finding the running time(s) for determining mathematical limits.

For instance, $\lim\_{x \to 2} \frac{1}{x} = \frac{1}{2}$.

I'd like to know more about algorithms for determining mathematical limits such as this, and I'm primarily concerned with the runtimes of such algorithms.

If it helps, there are only certain types of limits that I'm concerned with.

Specifically, I'm concerned with limits of one variable. I'm also really only concerned with rational functions of polynomials. For example, given two polynomials $p(x)$ and $q(x)$, I'm interested in finding the limit $\lim\_{x \to 1}\frac{p(x)}{q(x)}$.

There is additional information that should greatly help. I only really want to find the limit as $x$ approaches 1. Further, the limit itself is bounded $-O(2^n) \leq \lim\_{x \to 1} \leq O(2^n)$.

The function $p/q$ itself is actually a description of a polynomial with powers at most $O(2^n)$, and coefficients $c\_i \in {-1, 0, 1}$.

This may not be the best method, but I'm essentially trying to sum the coefficients of a polynomial.

> An Additional Interest

I'm also interested in expanding the problem to include limits of rational functions of multiple polynomials, i.e. polynomials $p\_i(x)$ and $q\_j(x)$ to find:

$\lim\_{x \to 1}\frac{\prod\_{i=0}^m{p\_i(x)}}{\prod\_{j=0}^n{q\_j(x)}}$

Note that the polynomials $p\_i(x)$ and $q\_j(x)$ are very sparse in this representation, consisting of no more than 2 terms.

**Tags:** cc.complexity-theory, lower-bounds, time-complexity, upper-bounds, polynomials
> **Comments:**
> **username_1**: Using l'Hopital's rule, if you have degree $n$ polynomials with $t$ terms, taking a limit involves differentiating at most $n$ times, which should take something like $O(nt)$ steps, ignoring issues of big integer arithmetic. By the way, your example is incorrect. And knowing the type of limit you're concerned with definitely helps ... I'm not even sure the question has an answer without this information.  
> **username_0**: Thanks Peter.  I'm not sure I know what you mean by type of limit.  I'd like to find the limit as $x$ approaches $c$ from either side.  Also, The coefficients of the polynomials are cyclical in nature, so I'm helping that this may help.  
> **username_2**: Are $p,q \in Z[x]$? So your questions is what is the time complexity of the following problem: "Given $p(x),q(x) \in Z[x]$, compute $\lim_{x \to c} \frac{p(x)}{q(x)}$".  
> **username_2**: So you are given a polynomial $r(x) = \frac{p(x)}{q(x)}$ implicitly as $p(x)$,$q(x)$ and you want to compute the value of $r(1)$.  
> **username_0**: @Kaveh: Yes. I forgot to mention that all powers $t$ of the polynomial are withing the range $0 \leq t \leq O(2^n)$.  
> **username_1**: @Matt: I didn't mean type of limit. I meant type of expression for which you're finding the limit.  
> **username_2**: Just one more clarification question, what is the representation of the polynomials $p(x)$,$q(x)$ given? Are you giving the coefficients of all monomials, or just nonzero ones, or are you giving them in some more compressed way? Note that a special case is when $q(x)=1$, so evaluation a polynomial is a special case. Also what is $n$?  
> **username_0**: The monomials $p(x)$ and $q(x)$ will be in the product form at the bottom of the question.  The monomials $p_i(x)$ and $q_j(x)$ will contain only nonzero coefficients.  I tried to use $n$ to compare powers and results.  The powers of $x$ are related to the range of the result by $n$.  
> **username_3**: This seems like a classical question in numerical analysis. Nothing to do with tcs...  
> **username_1**: @Matt: If the polynomials are in product form, you can separate them into polynomials for which $p_i(1)=0$ and for which $p_i(1) \neq 0$, and then try to use l'Hopital's rule for the ones which evaluate to 0. If each of them has no more than two terms, and contain only nonzero coefficients, does that mean that they all have degree 1, or do you maen something else by that?  
> **username_0**: @Peter: I can be very specific in this case - they will all have the form $\pm 1 \pm x^{2^n}$ for some integer $n$.  I guess the large powers of x make naively plugging in values look pretty good.  
> **username_1**: @Matt: I think this means we should be able to solve your problem quite easily. Unfortunately, I don't have time to write up an answer right now.  

---

## 1 answers

### Answer by username_1 on 2010-10-26. Score: 11 | Accepted answer

I don't have time to go into detail now, but here's a quick sketch of how to solve it. Let's assume that all of your polynomials look like $x^k-1$. What you have to do is use the identity $x^k-1 = (x-1)(1+x+x^2+\ldots + x^{k-1})$. You are starting with the function $\frac{\Pi\_{i=1}^n (x^{k\_i}-1)}{\Pi\_{i=1}^m (x^{\ell\_i}-1)}$. Now, factor out all the $(x-1)$ terms and take the limit. If $n >m$, you get $0$. If $n \lt m$, you get $\infty$. Otherwise, the $x-1$ terms cancel out, and what you're left with is $\frac{\Pi\_{i=1}^nk\_i}{\Pi\_{i=1}^n\ell\_i}$.


---

