Testing the efficiency of Horner’s Rule with MATLAB

Spread the word!

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:

unbenannt

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:

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

Now the same with Horner’s Rule:

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:

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:

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

Be the first to comment

Leave a Reply

Your email address will not be published.


*