sympy/sympy — pull request #8552 by cswiercz (2014-12-03 01:23:57+00:00)
Title: rootof: use modular exponentiaion with RootOf objects

Given a root of a polynomial of degree n any power of that root greater
than or equal to n can be written in terms of powers less than
n. Performing this modular reduction with RootOf expressions can curb
expression swell, at least with respect to handling large powers of the
root. In some cases this results in a performance improvement when
handling large degree expressions with RootOfs.

The change involves adding behavior to RootOf._eval_power() such that,
whenever an exponent greater than the root's defining polynomial's
degree is provided, a modular exponentiation algorithm is used to
determine the result. Otherwise, the default Expr._eval_power() is
called.

Example:

In [1]: r = RootOf(x**5 - 3*x**2 - 1,0)

In [2]: r**5
Out[2]:
2
⎛ 5 2 ⎞
3⋅RootOf⎝x - 3⋅x - 1, 0⎠ + 1

In [3]: r = RootOf(2*x**3 + 2*x - 1,0)

In [4]: p = random_poly(y, 20, -4, 4); q = random_poly(y, 20, -4, 4)

In [5]: %time (p.subs(y,r) * q.subs(y,r)).expand()
CPU times: user 103 ms, sys: 2.08 ms, total: 105 ms
Wall time: 109 ms
Out[5]:
2
⎛ 3 ⎞ ⎛ 3 ⎞
1023983⋅RootOf⎝2⋅x + 2⋅x - 1, 0⎠ 24609⋅RootOf⎝2⋅x + 2⋅x - 1, 0⎠ 13901
- ────────────────────────────────── + ─────────────────────────────── + ─────
2048 256 512

Without modular exponentiation / reduction the example expansion would
take approximately 340 ms.

Closes #8543.