Estrin.jl

Estrin.jl is an implementation of the Estrin's scheme for evaluating polynomials in Julia.

Installation

Type ] in the Julia REPL to use the package mode, then type the following command to install the package.

add Estrin

Usage

julia> using Estrin

# generate a random polynomial
julia> C = rand(10);

julia> poly = Poly(C);

# evaluate the polynomial at x = 1
julia> s = poly(1.0)

julia> s ≈ sum(C)
true

The Estrin's scheme

Given an arbitrary polynomial

P(x) = C_0 + C_1 x + C_2 x^2 + C_3 x^3 + ⋯ + C_n x^n

one can group adjacent terms into sub-expressions of the form $(A + Bx)$ and rewrite it as a polynomial in $x^2$:

P(x) = (C_0 + C_1x) + (C_2 + C_3 x) x^2 + ⋯ = Q(x^2).

These parameter can be calculated in parallel via SIMD, which can be more efficient than the traditional Horner's method.

However, it is obvious that the Estrin's scheme needed additional $N$ registers to store the intermediate results, which may be a bottleneck when the polynomial is large. Thus, the tile-based Estrin's scheme is proposed to reduce the number of registers needed. Instead of calculating the polynomial in one step, the tile-based Estrin's scheme divides the polynomial into multiple tiles (here I took the tiling size as $n = 16$), as

P(x) = C'_0 + C'_1 x^{n} + C'_2 x^{2n} + C'_3 x^{3n} + ⋯ = Q(x^{n})

where $C'_i$ is the coefficient of the $i$-th tile calculated by the Estrin's scheme. Then this process can be repeated recursively until the polynomial is small enough.

Benchmarks

Benchmarks scripts and results are stored in the following repo: https://github.com/ArrogantGao/Polynomial_Benchmarks. The results are shown below, where I compared the performance of Estrin's scheme (with and without tiling) with Horner's method and the Polynomials.jl package.