Thank you. Yes, in some cases I just need a degree or a leading term. On Monday, November 22, 2021 at 3:34:17 PM UTC+2 Oscar wrote:
> On Mon, 22 Nov 2021 at 09:18, Paul Royik <distan...@gmail.com> wrote: > > > > `(x-2)**9000` takes much time, but `(x-6)**100*(2-x)**9000` takes > forever. > > It's slow because it involves explicit coefficient calculations with > very large polynomials. Note that if you don't use Poly and you don't > expand the expressions then it's very fast. This kind of example > pushes towards the limit where the Poly representation is not useful > any more. In other words it's better not to expand these powers and > products but just work with those expressions as they are (which SymPy > can do just fine). I think that it would be useful to have a kind of > Poly representation that does not expand everything but still enables > other Poly methods like `degree`, `coeff` etc to work but that isn't > available so Poly always has to expand everything. > > The fastest library I know of for this sort of thing is flint which > can do this in about half a second on this laptop: > > In [1]: import flint > > In [3]: p1 = flint.fmpz_poly([-6, 1]) > > In [4]: p1 > > Out[4]: x + (-6) > > In [5]: p2 = flint.fmpz_poly([2, -1]) > > In [6]: p2 > > Out[6]: (-1)*x + 2 > > In [7]: %time _ = p1**100*p2**9000 > CPU times: user 597 ms, sys: 58.9 ms, total: 656 ms > Wall time: 665 ms > > I won't show the output but it's a 9100 degree polynomial with > coefficients that are 4000 (decimal) digit integers. Note that > although flint can do this example reasonably quickly it's still not > hard to push it a bit further and get something that takes too long or > consumes all the memory in your computer etc. Fundamentally if you > manipulate arbitrarily large non-sparse polynomials in explicit > representations then some things are going to hit up against the > limits of your computer. > > I would like to make it so that flint can be used to speed up internal > calculations in SymPy. Otherwise for raw low-level things like this > the fact that SymPy is a pure Python library will typically mean that > even with the best algorithms it will still be about 100x slower than > something like flint which is implemented in a mix of C and assembly > language. > > Broadly for two polynomials of degree d1 and d2 the algorithmic > complexity of the basic multiplication algorithm is O(d1 * d2) so > computing (x-6)**100*(2-x)**9000 should be expected to take about 100x > longer than (2-x)**9000. Faster algorithms are based on Karatsuba or > Schönhage–Strassen etc but SymPy doesn't have those. It looks like > flint has a whole bunch implemented: > > http://flintlib.org/sphinx/fmpz_poly.html#multiplication > https://fredrikj.net/python-flint/ > > -- > Oscar > -- 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 view this discussion on the web visit https://groups.google.com/d/msgid/sympy/540b2242-930e-43c4-854d-6e1442fc6cf7n%40googlegroups.com.
