Julia High Performance - Second Edition

Horner's method

So, the first thing to do is to find a better algorithm, one that can replace the exponentiation into multiplications. This can be done by Horner's method, which is named after the nineteenth-century British mathematician, William George Horner:

1. This is accomplished by defining a sequence, as follows:

Here, b₀ is the value of the p(x) polynomial.

2. This algorithm can be implemented in Julia, as follows:

function poly_horner(x, a...)    b=zero(x)    for i = length(a):-1:1       b = a[i] + b * x    end    return b end 

3. We can then test and benchmark this for the same polynomial:

f_horner(x) = poly_horner(x, 1,2,3,4,5,6,7,8,9)    julia> ...