There's a decent chance this algorithm is already implemented and just not integrated into the RootOf object, so I would search around the polys code first.
Aaron Meurer On Wed, Nov 26, 2014 at 12:17 PM, Ondřej Čertík <[email protected]> wrote: > Hi Chris, > > On Wed, Nov 26, 2014 at 11:56 AM, Chris Swierczewski <[email protected]> > 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 [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/CADDwiVARTrP6t5KucJ3zjJMhpONdCTirfZmat5-s8uq7CgniFg%40mail.gmail.com. > For more options, visit https://groups.google.com/d/optout. -- 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/CAKgW%3D6%2BMPW_zcfzDpOKd8sPKpYChQG2sm0bNxTv8gEikk9sQzQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
