Estrin.jl

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

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

add Estrin

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

Given an arbitrary polynomial

one can group adjacent terms into sub-expressions of the form $(A + Bx)$ and rewrite it as a polynomial in $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

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 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.