Thank you! On Tuesday, November 23, 2021 at 1:29:40 AM UTC+2 asme...@gmail.com wrote:
> There is this issue about making functions like degree() handle > polynomials in factored form > https://github.com/sympy/sympy/issues/6322. Most things aren't > implemented yet. If you do want just a specific term, your best bet is > to use series(), as this works quite well on polynomials without > expanding them. > > Aaron Meurer > > On Mon, Nov 22, 2021 at 8:14 AM Paul Royik <distan...@gmail.com> wrote: > > > > 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+un...@googlegroups.com. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/sympy/540b2242-930e-43c4-854d-6e1442fc6cf7n%40googlegroups.com > . > -- 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/11fd1567-90fc-4cce-95fd-95ef6b6648ben%40googlegroups.com.
