5
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 7
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Oct 24, 2010 at 15:45
  • $\begingroup$ 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. $\endgroup$
    – Matt Groff
    Oct 24, 2010 at 15:53
  • 2
    $\begingroup$ This seems like a classical question in numerical analysis. Nothing to do with tcs... $\endgroup$
    – Sariel Har-Peled
    Oct 25, 2010 at 17:53
  • 2
    $\begingroup$ @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? $\endgroup$
    – Peter Shor
    Oct 25, 2010 at 17:55
  • 1
    $\begingroup$ @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. $\endgroup$
    – Matt Groff
    Oct 25, 2010 at 21:13

1 Answer 1

Reset to default
11
$\begingroup$

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}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.