I have a preliminary implementation below that I can write up as a pull
request if people would prefer to take a look that way. I have not
performed any of the sympy tests yet but will do so later this afternoon.
class MyRootOf(RootOf):
__doc__ = RootOf.__doc__
def __init__(self, *args, **kwds):
RootOf.__init__(self, *args, **kwds)
def _eval_power(self, exponent):
if exponent >= self.poly.degree():
exponent = int(exponent)
result = 1
base = self.poly.gen
modulus = self.poly
while exponent > 0:
if (exponent % 2):
result = reduced(result*base, [modulus])[1]
exponent >>= 1
base = reduced(base*base, [modulus])[1]
return result.subs(self.poly.gen,self).as_expr()
return RootOf._eval_power(self, exponent)
This is a basic implementation of a modular exponentiation algorithm. The
basic idea is that since a root $b$ satisfies $p(b) = c*b**n = q(b)$ then
$b**n = - (1/c) * q(b)$. Here is a simple test:
f = 3*y**5 + 2*y - 1
root = MyRootOf(f,0)
print root**5
-2*RootOf(3*y**5 + 2*y - 1, 0)/3 + 1/3
>From what I gathered the method _eval_power() is called every time a Sympy
Expr subtype is exponentiated. This makes it so that p.eval(b) or p.subs(b)
uses the above modular exponentiation algorithm. Just overloading __pow__()
doesn't cut it.
I have some preliminary timings as well demonstrating that expansions of
polynomial expressions in this new RootOf is about x1.5 - x2 faster than
the original behavior which keeps track of all the higher powers.
I tried finding a way to make expressions like
root**4 * (1 + root)
symplify appropriately. But after diving into how Sympy handle's Mul's I
see that the default behavior of expressions like x*(1+x) is to not
automatically expand. I doubt that this behavior should be changed since
it'll impact so many other computations. However, if somebody know of how I
can default expand expressions involving RootOf / MyRootOf objects I would
greatly appreciate the feedback and suggestions.
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sympy.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sympy/bf63ac31-569a-4bcb-b9fd-ae6662d8c6e2%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
