speed up powers of lazy Taylor series

[mantepse]

As remarked in #32324 comment:105, the computation of the square root of a lazy series is very slow.

Depends on #32324

Component: combinatorics

Keywords: LazyPowerSeries

Author: Travis Scrimshaw

Branch/Commit: b237921

Reviewer: Martin Pepin

Issue created by migration from https://trac.sagemath.org/ticket/34350

[tscrim]

comment:1

Using a the naïve version using the Taylor series speeds things up considerably:

sage: L.<z> = LazyLaurentSeriesRing(QQ)
sage: f = sqrt(1 + z)
sage: %time f[200]
CPU times: user 254 ms, sys: 4.21 ms, total: 258 ms
Wall time: 258 ms

versus before

sage: %time f[200]
CPU times: user 2.39 s, sys: 1.83 ms, total: 2.4 s
Wall time: 2.4 s

Another example:

sage: q = ZZ['q'].fraction_field().gen()
sage: L.<z> = LazyLaurentSeriesRing(q.parent())
sage: f = (1 - z)^q
sage: f
1 - q*z + ((q^2 - q)/2)*z^2 + ((-q^3 + 3*q^2 - 2*q)/6)*z^3 + ((q^4 - 6*q^3 + 11*q^2 - 6*q)/24)*z^4 + ((-q^5 + 10*q^4 - 35*q^3 + 50*q^2 - 24*q)/120)*z^5 + ((q^6 - 15*q^5 + 85*q^4 - 225*q^3 + 274*q^2 - 120*q)/720)*z^6 + O(z^7)
sage: %time f[200]
CPU times: user 439 ms, sys: 0 ns, total: 439 ms
Wall time: 439 ms

versus before

sage: %time c = f[200]
CPU times: user 10.3 s, sys: 9.75 ms, total: 10.3 s
Wall time: 10.3 s

---

Last 10 new commits:

9d6579b	improve documentation, move zero, one, characteristic, etc. to ABC
feba6b8	Working more on `__call__` for LazySymFunc.
3f3e0f2	Merge branch 'public/rings/lazy_talyor_series-32324' of https://github.com/sagemath/sagetrac-mirror into public/rings/lazy_talyor_series-32324
6727228	Merge branch 'public/rings/lazy_talyor_series-32324' of trac.sagemath.org:sage into t/32324/public/rings/lazy_talyor_series-32324
028796d	Fixing numerous issues with `__call__` and expanding its functionality. Moving plethysm to a Stream_plethysm.
9fb155f	Removing unused code from previous version.
7f9dbb1	Some last doc fixes and tweaks.
4e03fee	remove unused local variable
e780472	Addressing the linter complaint.
465fe7c	Speeding up powers of lazy series by using a different algorithm.

[tscrim]

Author: Travis Scrimshaw

[tscrim]

Commit: 465fe7c

[tscrim]

Branch: public/rings/speedup_powers_lazy_series-34350

[tscrim]

Dependencies: #32324

[tscrim]

comment:2

I based this off #32324 since that is positively reviewed, although I can remove this if necessary.

[Kerl13]

Changed branch from public/rings/speedup_powers_lazy_series-34350 to u/MartinPepin/34350

[Kerl13]

Reviewer: MartinPepin

[Kerl13]

Changed commit from 465fe7c to d4450fb

[Kerl13]

comment:4

I reproduced the time difference, that's indeed huge!

I also took the opportunity to update the docstring for __pow__ with your examples. Before that it was only documenting integer powers. Once you have reviewed this change I think it's good to go.

---

New commits:

7b55ef5	Speeding up powers of lazy series by using a different algorithm.
d4450fb	Update lazy_series' `__pow__` docstring

[tscrim]

Changed reviewer from MartinPepin to Martin Pepin

[tscrim]

comment:5

Hi Martin P. Thanks for the review. Can you quickly do two minor little tweaks to follow our docstring conventions:

-        - ``n`` -- the power to which to raise the series. This may be an
-          integer, a rational number, an element of the base ring, or an other
-          series.
+        - ``n`` -- the power to which to raise the series; this may be a
+          rational number, an element of the base ring, or another series

             sage: f
-            1 - q*z + ((q^2 - q)/2)*z^2 + ((-q^3 + 3*q^2 - 2*q)/6)*z^3 + ((q^4 - 6*q^3 + 11*q^2 - 6*q)/24)*z^4 + ((-q^5 + 10*q^4 - 35*q^3 + 50*q^2 - 24*q)/120)*z^5 + ((q^6 - 15*q^5 + 85*q^4 - 225*q^3 + 274*q^2 - 120*q)/720)*z^6 + O(z^7)
+            1 - q*z + ((q^2 - q)/2)*z^2 + ((-q^3 + 3*q^2 - 2*q)/6)*z^3
+             + ((q^4 - 6*q^3 + 11*q^2 - 6*q)/24)*z^4
+             + ((-q^5 + 10*q^4 - 35*q^3 + 50*q^2 - 24*q)/120)*z^5
+             + ((q^6 - 15*q^5 + 85*q^4 - 225*q^3 + 274*q^2 - 120*q)/720)*z^6
+             + O(z^7)
         """

Once you do those, you can set a positive review.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b237921

Formatting issues / docstring conventions

[sagetrac-git]

Changed commit from d4450fb to b237921

[vbraun]

Changed branch from u/MartinPepin/34350 to b237921