[Tutor] A little math and Python: Horner's rule [horner's r

[Sean 'Shaleh' Perry]

> 
> One technique we can use to speed up a function is to reduce the amount of
> work it does.  *grin* In Python, looking up a module function does take
> some work, as does list construction, so I've pulled both of these outside
> of the f4() function.
> 
> f4() is an improvement, but, surprisingly, it's still a bit slower than
> the native Python implementation f2().  Very odd!  I'll have to glare
> confusedly at my C code and see where I'm doing something stupid.
> 
> 
> I've placed my 'hornerc' extension here for intrepid souls:
> 
>     http://hkn.eecs.berkeley.edu/~dyoo/python/horner/
> 
> 
> One lesson I'm learning from this is that coding in C is not magic fairy
> dust --- It's possible that just recoding an algorithm in C may even slow
> things down if we're not careful!  Premature optimization is the root of
> all evil.
> 
> 

you went from a simple function with hard coded internals to an abstracted
function.  What's more f4() depends on a global.  For a proper speed comparison
you should use a python implementation that looks like your C implementation.


starting simply, this is hard coded for a 6 item list.

def f5(l, x):
    return((((l[-6] * x + l[-5]) * x + l[-4]) * x + l[-3]) * x + l[-2]) * x +
l[-1]

the next step would be an arbitrary list.  Then compare the numbers.  This
should help point out any other overheads.