Polynomial Evaluation

[RagonEbker]

Hello,
I want to understand how Sympy evaluates polynomials. Does it use horners method?

[oscarbenjamin]

Can you show code to demonstrate what you mean by SymPy evaluating a polynomial?

[RagonEbker]

For example here:

deg = 40
p = Poly(random_poly(x,deg,0,10),x)


start_time = time.time()
p(100)
print("--- %s seconds ---" % (time.time() - start_time))


q = p.as_expr()
start_time = time.time()
q.subs(x,100)
print("--- %s seconds ---" % (time.time() - start_time))

outputs:
--- 0.00011587142944335938 seconds ---
--- 0.028937339782714844 seconds ---

So, evaluating a poly is a lot faster than evaluating the expression itself. Does that lie in the usage of Horners method?

[oscarbenjamin]

The main difference is just that Poly uses more efficient internal representations than SymPy's ordinary symbolic expressions. For Poly the method is here:

sympy/sympy/polys/densetools.py

Lines 288 to 314 in 2f80497

	def dmp_eval(f, a, u, K):
	"""
	Evaluate a polynomial at ``x_0 = a`` in ``K[X]`` using the Horner scheme.
	Examples
	========
	>>> from sympy.polys import ring, ZZ
	>>> R, x,y = ring("x,y", ZZ)
	>>> R.dmp_eval(2*x*y + 3*x + y + 2, 2)
	5*y + 8
	"""
	if not u:
	return dup_eval(f, a, K)
	if not a:
	return dmp_TC(f, K)
	result, v = dmp_LC(f, K), u - 1
	for coeff in f[1:]:
	result = dmp_mul_ground(result, a, v, K)
	result = dmp_add(result, coeff, v, K)
	return result