Opened 5 months ago

Closed 4 months ago

#33223 closed enhancement (fixed)

make PARI the default for EllipticCurve_field.weierstrass_p()

Reported by: lorenz Owned by:
Priority: major Milestone: sage-9.6
Component: elliptic curves Keywords:
Cc: cremona, defeo, vdelecroix Merged in:
Authors: Lorenz Panny Reviewers: Sébastien Labbé, John Cremona, Samuel Lelièvre
Report Upstream: N/A Work issues:
Branch: fbffbf3 (Commits, GitHub, GitLab) Commit: fbffbf383fa009c6861365c09e9dbeb788858d4d
Dependencies: #33224 Stopgaps:

Status badges

Description (last modified by lorenz)

On 9.5.rc3:

sage: E = EllipticCurve(GF(65537), [1, 2, 3, 4, 5])
sage: %timeit E.weierstrass_p(prec=1000)
229 ms ± 1.81 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit E.weierstrass_p(prec=1000, algorithm='pari')
52.1 ms ± 1.15 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

PARI is significantly faster in all examples I've tried. We should use it by default instead of Sage's own implementation.

Change History (23)

comment:1 Changed 5 months ago by lorenz

  • Description modified (diff)

comment:2 Changed 5 months ago by lorenz

  • Dependencies set to #33224
  • Summary changed from make PARI the default for EllipticCurve_field.weierstrass_p to make PARI the default for EllipticCurve_field.weierstrass_p()

comment:3 Changed 5 months ago by lorenz

  • Authors set to Lorenz Panny
  • Branch set to public/use_pari_ellwp_by_default
  • Cc cremona defeo added
  • Commit set to 6b2cd18fe119597f7f7df3f6ab5d48fc713a31de
  • Status changed from new to needs_review

New commits:

6b2cd18use PARI's ellwp() by default (it's faster than the "fast" implementation)

comment:4 Changed 5 months ago by lorenz

  • Cc vdelecroix added

comment:5 Changed 5 months ago by slabbe

  • Reviewers set to Sébastien Labbé
  • Status changed from needs_review to needs_work

I confirm the new default is better:

sage: %timeit E.weierstrass_p(prec=1000, algorithm='fast')
268 ms ± 580 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit E.weierstrass_p(prec=1000, algorithm='pari')
58.3 ms ± 160 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit E.weierstrass_p(prec=1000, algorithm='quadratic')
86.4 ms ± 167 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
sage: %timeit E.weierstrass_p(prec=1000)
57.7 ms ± 197 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

While reviewing, I noticed typos in the documentation:

sage: E.weierstrass_p??

I suggest to fix as follows:

-        - ``mprec`` - precision
+        - ``prec`` - precision

-        - ``algorithm`` - string (default:``None``) an algorithm identifier
-                      indicating using the ``pari``, ``fast`` or ``quadratic``
-                      algorithm. If the algorithm is ``None``, then this
-                      function determines the best algorithm to use.
+        - ``algorithm`` - string (default: ``None``) an algorithm identifier
+          indicating using the ``pari``, ``fast`` or ``quadratic``
+          algorithm. If the algorithm is ``None``, then this
+          function determines the best algorithm to use.
Last edited 5 months ago by slelievre (previous) (diff)

comment:6 Changed 5 months ago by git

  • Commit changed from 6b2cd18fe119597f7f7df3f6ab5d48fc713a31de to 8daecaf95c13364d4466eb4ac7cc87ddd755d63a

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

8daecafdoc tweaks

comment:7 Changed 5 months ago by lorenz

  • Status changed from needs_work to needs_review

Thanks! Updated documentation.

comment:8 Changed 5 months ago by slabbe

  • Status changed from needs_review to needs_work

I checked the changes. Looks good. Only one thing.

I don't agree with the following change:

-        - ``algorithm`` - string (default:``None``) an algorithm identifier
-                      indicating using the ``pari``, ``fast`` or ``quadratic``
-                      algorithm. If the algorithm is ``None``, then this
-                      function determines the best algorithm to use.
+        - ``algorithm`` -- an algorithm name or (default) ``None``:
+          See :func:`sage.schemes.elliptic_curves.ell_wp.weierstrass_p`
+          for a list of possible values.

Because for any user that get there, it is force one more step to get the possible values which is very often a question that comes to mind. Also, for normal user, they might just not be able to get to this other method.

In summary, I think it is better to leave it with an explicit list even if the information is doubled.

comment:9 Changed 5 months ago by cremona

I agree with slabbe's comment. (I hate it when a function has a *kwds argument and the docstring does not explain them but sends you some where else, which is similar.)

comment:10 Changed 5 months ago by git

  • Commit changed from 8daecaf95c13364d4466eb4ac7cc87ddd755d63a to 741f1dbf46422ff3e36b4af586593d4ee76c21d1

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

741f1dbun-deduplicate documentation per comments in #33223

comment:11 Changed 5 months ago by lorenz

  • Status changed from needs_work to needs_review

Alright, makes sense. I changed it back (and added a comment to ell_wp.py to remind people of the duplication).

comment:12 Changed 5 months ago by slabbe

  • Status changed from needs_review to needs_work

Thanks for the changes.

I still have some comments with respect to coding conventions in sage with respect to documentation. Sorry if it is troublesome: it is just some details.

The following change

-        - ``algorithm`` - string (default:``None``) an algorithm identifier
+        - ``algorithm`` -- string or (default) ``None``: an algorithm

does not respect the coding convention for the documentation. See https://doc.sagemath.org/html/en/developer/coding_basics.html To be more precise, please keep string (default:``None``) as is (twice).

Also, it would more exact to write ``'pari'`` ``'fast'`` ``'quadratic'`` as opposed to ``pari`` ``fast`` ``quadratic``. Observe that ``None`` is okay, since it is not about the string ``'None'``.

Last edited 5 months ago by slabbe (previous) (diff)

comment:13 Changed 5 months ago by git

  • Commit changed from 741f1dbf46422ff3e36b4af586593d4ee76c21d1 to 07045c28c66022d5e2bd33233a8666d52daab0bf

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

07045c2follow doc formatting convention

comment:14 Changed 5 months ago by lorenz

  • Status changed from needs_work to needs_review

The reason I'd changed it was precisely that None is not a string, so saying that this parameter is "a string which defaults to None" is not type-correct. Realistically speaking it's clear enough either way.

comment:15 Changed 5 months ago by slelievre

How about:

        - ``algorithm`` -- string or ``None`` (default: ``None``):
          a choice of algorithm among ``"pari"``, ``"fast"``
          ``"quadratic"``; or ``None`` to let this function
          determine the best algorithm to use.

comment:16 Changed 5 months ago by git

  • Commit changed from 07045c28c66022d5e2bd33233a8666d52daab0bf to fbffbf383fa009c6861365c09e9dbeb788858d4d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

bf799aduse PARI's ellwp() by default (it's faster than the "fast" implementation)
fbffbf3doc tweaks

comment:17 Changed 5 months ago by lorenz

Done, and squashed all the documentation edits to untangle the commit history a bit.

comment:18 Changed 5 months ago by slelievre

  • Reviewers changed from Sébastien Labbé to Sébastien Labbé, John Cremona, Samuel Lelièvre

Looks good to me if other reviewers agree.

comment:19 follow-up: Changed 5 months ago by cremona

Fine by me. The moral of this story is never to label an algorithm as 'fast'.

comment:20 in reply to: ↑ 19 Changed 5 months ago by slabbe

Replying to cremona:

Fine by me. The moral of this story is never to label an algorithm as 'fast'.

Indeed!

comment:21 Changed 5 months ago by slabbe

  • Status changed from needs_review to positive_review

I confirm that make works including the doc:

[sagemath_doc_html-none] Build finished.

and All tests passed! in folder sage -tp src/sage/schemes/elliptic_curves.

Last edited 5 months ago by slabbe (previous) (diff)

comment:22 Changed 5 months ago by lorenz

Thanks everyone!

comment:23 Changed 4 months ago by vbraun

  • Branch changed from public/use_pari_ellwp_by_default to fbffbf383fa009c6861365c09e9dbeb788858d4d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.