Consider the following polynomial:

This is a fourth-order polynomial. To evaluate this thing, you might write the following code in Python.

```
def f(x):
return x**4 + x**3 + x**2 + x + 1
```

The problem is that calculating exponents is computationally expensive, so you might try to create a closed form of the equation. In this example, you can use the well known generating function:

This reduces the number of exponents that Python has to deal with. Watch the division by zero error if you let x=1!

```
def genf(x):
return (1 - x**5)/(1-x)
```

If we could reduce or eliminate the number of exponents even further, we might expect that the code would run faster. Fortunately, you can apply Horner’s Rule to this problem. The rule removes the exponents by factorizing the equation into a series of multiplication and addition steps:

The equation, now missing the expensive exponents, can be implemented like this:

```
def hornerf(x):
return (((x+1)*x+1)*x+1)*x+1
```

So now you’re probably thinking, “Show me the money!”

The following code is a test harness that counts how much time it takes to execute the functions on a large set of numbers.

```
def timeit(fn):
begin = time.time()
for element in bigset:
fn(element)
end = time.time()
return end - begin
```

The following is a transcript of the test run on my laptop:

```
>>> ================================ RESTART ================================
>>> def f(x):
return x**4 + x**3 + x**2 + x + 1
>>> def genf(x):
return (1 - x**5)/(1-x)
>>> def hornerf(x):
return (((x+1)*x+1)*x+1)*x+1
>>> import time
>>> bigset = range(2,1000000)
>>> def timeit(fn):
begin = time.time()
for element in bigset:
fn(element)
end = time.time()
return end - begin
>>> timeit(f)
9.2969999313354492
>>> timeit(genf)
4.4679999351501465
>>> timeit(hornerf)
2.1099998950958252
```

In this example, you could gain a speed improvement of over 70% from eliminating the exponents in your code. Although not all optimizations will be this dramatic, you will almost always gain some improvement by eliminating exponents.

Thanks to D Yoo