Polynomial evaluation

$$ \frac{p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + p_4 ⋅ x^4 + p_5 ⋅ x^5} {q_0 + q_1 ⋅ x + q_2 ⋅ x^2 + q_3 ⋅ x^3 + q_4 ⋅ x^4 + q_5 ⋅ x^5 + x^6} $$

Basic algorithms

Horners rule

For Monomial basis

p = p5
p = p * x + p4
p = p * x + p3
p = p * x + p2
p = p * x + p1
p = p * x + p0
q = x + q5
q = q * x + q4
q = q * x + q3
q = q * x + q2
q = q * x + q1
q = q * x + q0
r = p / q

Clenshaw algorithm

Generalization, specifically for Chebyshev basis.

https://en.wikipedia.org/wiki/Clenshaw_algorithm

De Castlejau's algorithm

For Bernstein basis

https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm

https://en.wikipedia.org/wiki/De_Boor%27s_algorithm

Easy polynomials

https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

https://en.wikipedia.org/wiki/Addition-chain_exponentiation

https://en.wikipedia.org/wiki/Vectorial_addition_chain

WNAF, Pippenger's algorithm, etc.

Preprocessing

$$ y = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + x^4 $$

would take three multiplications to evaluate

p = x + p3
p = p * x + p2
p = p * x + p1
p = p * x + p0

but can also be evaluated using only two by

$$ \begin{aligned} a &= (x + β_0) ⋅ x + β_1 & y &= (a + β_2) ⋅ a + β_3 \end{aligned} $$

with

$$ \begin{aligned} β_0 &= \frac12\p{a_3 - 1} & z &= a_2 - β_0 ⋅ \p{β_0 + 1} & β_1 &= a_1 - β_0 ⋅ z \\ β_2 &= z - 2 ⋅ β_1 & β_3 &= a_0 - β_1 ⋅ \p{β_1 + β_2} \end{aligned} $$

a = x + β0
a = a ⋅ x + β1
y = a + β2
y = y ⋅ a + β3

Pan's scheme for one polynomial

See §3.3 of the Pan's 1966 paper.

Assuming p monic

g2 = x * x
h2 = g2 + x

p1 = x + l1

g4_1 = (g2 + l3) * (h2 + l2) + l4
p5 = p1 * g4_1 + l5

g4_2 = (g2 + l7) * (h2 + l6) + l8
p9 = p5 * g4_2 + l9

# Output formulas
p1 = p1
p2 = p1 * x + a0
p3 = p1 * (g2 + a0) + a1
p4 = (p1 * (g2 + a0) + a1) * x + a2
p5 = p5
p6 = p5 * x + a0
p7 = p5 * (g2 + a0) + a1
p8 = (p5 * (g2 + a0) + a1) * x + a2
p9 = p9
p10 = p9 * x + a0
p11 = p9 * (g2 + a0) + a1
p12 = (p9 * (g2 + a0) + a1) * x + a2

(6,7)-term rat scheme: 4 + 5 muls.

p5 & p6

g2 = x * x
h2 = g2 + x

p1 = x + l1
g4_1 = (g2 + l3) * (h2 + l2) + l4
p5 = p1 * g4_1 + l5

p1 = x + l1
g4_1 = (g2 + l3) * (h2 + l2) + l4
p5 = p1 * g4_1 + l5
p6 = p5 * x + a0

above: 1 + 2 + 3 = 6 muls.

knuth explicits: 3 + 3 = 6 muls

$$ p(x) = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + p_3 ⋅ x^3 + p_4 ⋅ x^4 + x^5 $$

$$ q(x) = q_0 + q_1 ⋅ x + q_2 ⋅ x^2 + q_3 ⋅ x^3 + q_4 ⋅ x^4 + q_5 ⋅ x^5 + x^6 $$

Paterson-Stockmeyer

Consider the $n$-term monic polynomial where $n = 2 ⋅ k$

$$ p(x) = p_0 + p_1 ⋅ x + p_2 ⋅ x^2 + \cdots + p_{n-2} ⋅ x^{n-2} + x^{n-1} $$

We can rewrite it using two $k$-term monic polynomial $p_1$ and $p_2$:

$$ p(x) = p_1(x) + (x^k + a) ⋅ p_2(x) $$

Where $a = p_{k-1} -1$ and $p_2$ the top half of $p$ and $p_1$ is the lower half of $p$ with $a ⋅ p_2$ subtracted.


$x^2 = x ⋅ x$

$x^4 = x^2 ⋅ x^2$

$p(x) = p_0(x) + (x^4 + a_0) ⋅ p_1(x)$ with $p_0 = c_0 + c_1 ⋅ x + c_2 ⋅ x^2 + c_3 ⋅ x^3$

$p_0(x) = p_2(x) + (x^2 + a_0) ⋅ p_3(x)$

Random

Schwartz–Zippel lemma

https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

Vieta's formula

https://en.wikipedia.org/wiki/Vieta%27s_formulas

Frobenius Endomorphism

https://en.wikipedia.org/wiki/Frobenius_endomorphism

Abert method

https://en.wikipedia.org/wiki/Durand%E2%80%93Kerner_method

https://en.wikipedia.org/wiki/Aberth_method

Reference

https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity

http://eprints.maths.manchester.ac.uk/2700/3/fasi19.pdf

https://epubs.siam.org/doi/10.1137/0202007

https://onlinelibrary.wiley.com/doi/10.1002/cpa.3160250405

https://ethresear.ch/t/simple-guide-to-fast-linear-combinations-aka-multiexponentiations/7238

https://jbootle.github.io/Misc/pippenger.pdf

Remco Bloemen
Math & Engineering
https://2π.com