Skip to main content
7 of 7
added 6 characters in body
Michael Hardy
  • 1
  • 12
  • 85
  • 126

This argument is problematic; see Andrej Bauer's comment below.


Sure. I have no idea what an efficient algorithm looks like, but since you only asked whether it's possible I'll offer a terrible one.

Lemma: Let $f(z) = z^n + a_{n-1} z^{n-1} + \cdots + a_0$ be a complex polynomial and let $R = \max(1, |a_{n-1}| + \cdots + |a_0|)$. Then all the roots of $f$ lie in the circle of radius $R$ centered at the origin.

Proof. If $|z| > R$, then $|z|^n > R |z|^{n-1} \ge |a_{n-1} z^{n-1}| + \cdots + |a_0|$, so by the triangle inequality no such $z$ is a root.

Now subdivide the disk of radius $R$ into, say, a mesh of squares of side length $\varepsilon > 0$ and evaluate the polynomial at all the lattice points of the mesh. As the mesh size tends to zero you'll find points that approximate the zeroes to arbitrary accuracy.

There are also lots of specialized algorithms for finding roots of polynomials at the Wikipedia article.

Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741