What is the Horner’s Rule used for? It lets us write a polynomial in such a form which require less multiplications, as shown from the Wikipedia’s page:

In practice, **how much is it worth it?** I was curious to see how good would it make the code performance. Here I’m using Matlab R2018a.

In the first part, we compute a simple 10th degree polynomial *p(x)* with a fixed value of *x* and do this computation 1 million times. Translating this into a code we obtain the following:

1 2 3 4 5 6 |
x=123456789; tic for i=[1:1000000] p=x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1; end toc |

Repeating this measurement 10 times I obtained a mean value of 1,6 seconds.

Now the same with Horner’s Rule:

1 2 3 4 5 6 |
x=123456789; tic for i=[1:1000000] p=1+x*(1+x*(1+x*(1+x*(1+x*(1+x*(1+x*(1+x*(1+x*(1+x))))))))); end toc |

In this case the mean elapsed time value was 0,038 seconds, which means ~40 times faster.

Let’s try with matrices instead of scalar as x value. In particular I assigned a 10 by 10 matrix to x in the first line:

1 |
x=magic(10); |

How much did the classical polynomial take? 31,55 seconds.

How much with the Horner’s Rule? 10,06 seconds, which means ~3 times faster.

With a 20 by 20 matrix the result is similar (50 s versus 16,6 s : ~3 times faster) as well as with a 30 by 30 matrix (110,5 s versus 38,5 s: ~2,9 times faster)

According to this small tests, **the Horner’s Rule makes lot of difference**.

But how to convert a polynomial with Matlab? The native functions would simplify the job:

1 2 3 |
syms x p = @(x) x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1; horner(p,x) |

The above code snippet needs a time (also less than) ~0.1 seconds.

## Leave a Reply