Evaluating a polynomial with nested multiplication

What is an efficient method for evaluating $p(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_0$ at a given $x$?

Horner's scheme: $n$ multiplications and $n$ additions. Rewrite $p(x)=(\cdots((a_nx+a_{n-1})x+a_{n-2})x+\cdots)x+a_0$ and evaluate from the inside out, starting with $b=a_n$ and repeating $b\leftarrow bx+a_k$. Computing each power separately costs $O(n^2)$ multiplications; Horner is $O(n)$ and also numerically well behaved.