On Aug 10, 1:23 am, Mateusz Paprocki <matt...@gmail.com> wrote: > Hi, > > > > On Sat, Aug 07, 2010 at 04:57:18AM -0700, 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. > > > 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. > > I implemented a simple symbolic factor() function on polys11, e.g.: > > In [1]: factor((x**2 + 4*x + 4)**10000000/(x**2 + 1), extension=I) > Out[1]: > 20000000 > (2 + x) > ─────────────── > (x + ⅈ)⋅(x - ⅈ) > > Previously one had to use frac=True flag and it hanged anyway due > to the huge exponent (really due to expand()). However, this case: > > factor((x + y)**100*z**2 + 2*(x + y)**100*z + (x + y)**100) >
Maybe we can try that gist thing to continue the discussion. I have a little routine at git://gist.github.com/518588.git that is the most pythonic think I've come up with yet that does a naive separation of bases (type 1 factoring in this discussion). I envision the whole factoring procedure to look like this: naively separate eq into a product of adds a*x**2 - a*x + b*x**2 - b*x ->(a+b)*(x**3 - x) for each factor in above, do a gcd_removal; the x**2 and x could also represent something like exp(a+b) and exp(a)--powers that have bases that can be extracted multiplicatively. ->(a+b)*x*(x**2-1) Finally, for each add in the above, do a full factoring: ->(a+b)*x*(x+1)*(x-1) No expansion is done until this last step. -- 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.
