2022-07-12

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 \cdot x + p_2 \cdot x^2 + p_3 \cdot 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 \cdot x + p_2 \cdot x^2 + p_3 \cdot x^3 + p_4 \cdot x^4 + x^5$

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

Paterson-Stockmeyer

Consider the $n$ -term monic polynomial where $n = 2 \cdot 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) \cdot 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 \cdot p_2$ subtracted.

$x^2 = x \cdot x$

$x^4 = x^2 \cdot x^2$

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

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

Random

Reference

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

V.Ya. Pan (1966). "Methods of Computing Values of Polynomials" doi
S. Winograd (1970). "On the number of multiplications necessary to compute certain functions" doi
M.O. Rabin & S. Winograd (1972). "Fast Evaluation of Polynomials by Rational Preparation" doi
D. Knuth (2011). "The Art of Computer Programming – Volume 2: Seminumerical Algorithms" isbn

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