Estrin's scheme using sympy

Question

I am wondering if it is possible to use the symbolical capabilities of symbolic python in such a way that given a multivariate polynomial, it factorizes the polynomial in order to use Estrin's scheme. I expect have some profit from it because the terms in the factorized polynomial could be evaluated using fused multiply-add (FMA).

For one polynomial the factorization can be performed by hand of course, but the task become enormous for a long list of polynomial as indeed is my case.

Answer 1

Perhaps something like this:

def estrin_eval(coeffs, x):
    """return Estrin evaluation of polynomial with coefficients
    given in order low to high
    
    Examples
    ========
    
    >>> from sympy import x
    >>> estrin_eval([1,1,2,5], x)
    x**2*(5*x + 2) + x + 1
    >>> estrin_eval(range(1,9), x)
    x**4*(x**2*(8*x+7) + 6*x + 5) + x**2*(4*x+3)+2*x+1
    >>> _.expand()
    8*x**7 + 7*x**6 + 6*x**5 + 5*x**4 + 4*x**3 + 3*x**2 + 2*x + 1
    >>> estrin_eval(range(1,9), 7) == _.subs(x, 7)
    True
    """
    n = len(coeffs)
    m = 1
    do = 0
    while m < n:
        m*= 2
        do+=1
    ans = list(coeffs) + [0]*(m -n)
    for i in range(do):
        for j in range(len(ans)//2):
            ans[j:j+2] = [ans[j]+x*ans[j+1]]
        x*=x
    return ans[0]