Optimum factoring of multinomial expression

[brombo]

Does sympy have the capability to optimally factor (minimum number of numerical operations) a polynomial or better yet a multinomial for numerical evaluation.  The simple example for a polynomial would be consider the polynomial -

y = a*x**3+b*x**2+c*x+d

then the  optimal factorization (minimizes number of numerical operations) would be -

y  = ((a*x+b)*x+c)*x+d

What are sympy's the current capabilities?

[Oscar Benjamin]

This particular example can be handled with horner:

In [1]: a, b, c, d, x = symbols('a, b, c, d, x')

In [2]: y = a * x ** 3 + b * x ** 2 + c * x + d

In [3]: print(y)
a*x**3 + b*x**2 + c*x + d

In [4]: print(horner(y))
d + x*(c + x*(a*x + b))

In the multivariate case the result depends on the ordering of the symbols e.g.:

In [9]: x, y = symbols("x, y")

In [10]: p = x ** 2 * y + y ** 2 * x + x ** 2 + y ** 2

In [11]: print(horner(p, x, y))
x*(x*(y + 1) + y**2) + y**2

In [12]: print(horner(p, y, x))
x**2 + y*(x**2 + y*(x + 1))

I have heard of algorithms that attempt to find an optimal ordering
for hornerisation but I don't think any is implemented in sympy.

--
Oscar

[Chris Smith]

See also the examples in https://github.com/sympy/sympy/issues/23072

/c

[Aaron Meurer]

There are different algorithms for multivariate horner. See the discussion at https://github.com/sympy/sympy/issues/11349. There is a pull request for that issue that never got merged. If you're interested in the multivariate case, you may want to try reviving that work.

Aaron Meurer

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/6ec97381-bf07-4472-b452-9cb751080562n%40googlegroups.com.