On Mon, 22 Nov 2021 at 09:18, Paul Royik <[email protected]> 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAHVvXxT13vfYmh0bYJmr7%2B2N5VgLbkoAtpaG1nFbMfLUJ-tkag%40mail.gmail.com.
