On Aug 7, 2010, at 5:57 AM, smichr wrote: > I've asked about factoring before but am just jotting down some > observations that I've made in the last few days. I was talking with > Aaron the other day about a routine and suggested he should use > factoring. He says, "that's gong to be expensive." I got to thinking. > > There are really 3 (at least) types of factoring: > > 1) factoring that can be done by inspection of factors. I call this > separation. Pursued recursively, it leads to a possible separation of > variables: > > x + x*y + a + a*y > x*(1 + y) + a*(1 + y) > (x+a)*(1+y)
> > This should be very fast factoring since you are looking for existing > factors, not extractable factors. separatevars should be re-written to > not use factor since that expensive operation is not needed for this. Hmm. At first, I didn't think this would always work in the general case, but actually, now I am not so sure. If you consider the expansion of such a separated expression, I think it should always work, actually. Of course, such a routine should be timed against the regular factor() to see if it is really faster. > > 2) factoring that can be done be extraction of common bases: > > x + x**2 > x*(1 + x) > > This should be pretty fast since you have the factor candidates > already visible but you need to see if they can be extracted from > other bases. This sort of factoring is available through terms_gcd > > 3) factoring that can be done only by identifying potential factors > and doing trial division. > > x**2 - 1 > (x+1)*(x-1) > > This is available through factor, but perhaps factor should try the > other simpler methods before resorting to level 3 factoring. Actually, the full factoring provided by factor() does more than just trial division. Trial division only gives you irreducible factors of degree 1. But we know that over the rationals, irreducible polynomials can have arbitrarily hight degree. For example, do factor(x**n - 1) for various n. All the resulting polynomials will be irreducible. The full factor() routine uses a non-trivial algorithm called the EEZ algorithm to find all the irreducible factors over QQ (or ZZ). I believe it might actually does do things like trial division first, and gcd factor before the more advanced things. I'm not positive, though. You can check in factortools.py (or wait until Mateusz replies). Aaron Meurer -- You received this message because you are subscribed to the Google Groups "sympy-patches" group. To post to this group, send email to sympy-patc...@googlegroups.com. To unsubscribe from this group, send email to sympy-patches+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sympy-patches?hl=en.
