Hi Chris, On Wed, Nov 26, 2014 at 11:56 AM, Chris Swierczewski <cswie...@gmail.com> wrote: > Hello, > > Thanks for the quick response! > >> This is what I get: >> ... >> So looks like it hasn't been implemented yet. > > Right on. I'll start poking around, then. > >> Good question. First, I would implement RootOf.mypow(n) and see if you >> can figure out how to get the answer you want. That's the hard part. >> What's the algorithm to determine which powers simplify and which not? > > I was considering starting with a binary method like the one outlined here: > > http://en.wikipedia.org/wiki/Modular_exponentiation > > (I remember this from a number theory course I took with William Stein back > in my undergraduate days!) I guess the simplification convention, if there is > one, is to reduce modulo the leading term of the polynomial. So if `alpha` is > a root of > > f(x) = c x**n + lower_order_terms(x) > > then > > alpha**n = lower_order_terms(alpha) / c > > Any high power of the root can be given in terms of lower powers. The harder > part will be making this fast. (To my knowledge the binary method is the most > common fast approach.)
I see, yes, that should work. Clever. > >> Then the next question is how to hook this up into sympy, so that it >> simplifies automatically, I guess one would need to add an if >> statement into the Pow simplification somewhere. > > The more I think about it the more it looks like the bulk of the problem is > to implement modular exponentiation of polynomials... > > I'll implement a "mypow" first and see what people have to say about making > this play nice with everything. Exactly, that's always my approach to first implement the algorithm and then worry how to best hook it up in sympy (or any other software). Let us know if you run into any problems. Thanks for working on this, that would be a great addition to RootOf. Ondrej -- 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+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. 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/CADDwiVARTrP6t5KucJ3zjJMhpONdCTirfZmat5-s8uq7CgniFg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.