Opened 8 years ago

Closed 12 months ago

Last modified 11 months ago

#12560 closed enhancement (fixed)

Artin-Hasse exponential

Reported by: magfrump Owned by: roed
Priority: major Milestone: sage-8.5
Component: padics Keywords: sd87, padicIMA
Cc: caruso, spancratz Merged in:
Authors: Mitchell Owen, Sebastian Pancratz, Xavier Caruso Reviewers: David Roe
Report Upstream: N/A Work issues:
Branch: 89cd40c (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by caruso)

Add Artin-Hasse exponential to Zp, Qp and their extensions.

Attachments (1)

12560.patch (5.9 KB) - added by magfrump 8 years ago.

Download all attachments as: .zip

Change History (61)

Changed 8 years ago by magfrump

comment:1 Changed 8 years ago by magfrump

  • Status changed from new to needs_review

comment:2 follow-up: Changed 8 years ago by dsm

Two points, one trivial and one not:

(1) Shouldn't it be "Artin-Hasse exponential" and not "Artin Hasse Exponential"?

(2) There really aren't any tests which demonstrate that what the function returns is actually the A-H exp, as opposed to some other similar-looking element in the ring. Probably there should be something in TESTS: which verifies some known properties.

comment:3 in reply to: ↑ 2 Changed 8 years ago by magfrump

(1) agreed

(2) also agreed, I'm planning to add some doctests to that effect today.

comment:4 Changed 8 years ago by dsm

  • Status changed from needs_review to needs_work

comment:5 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 3 years ago by kedlaya

Ping. This looks like low-hanging fruit; it just needs some more convincing doctests.

comment:10 Changed 3 years ago by chapoton

  • Branch set to public/12560
  • Commit set to 64732d222ed07af48c6a61a0470825fc420b302c

I made a branch, and refreshed it, but did not manage to make it compile..


New commits:

64732d2trac 12560 Artin-Hasse exponential (not compiling)
Last edited 3 years ago by chapoton (previous) (diff)

comment:11 Changed 3 years ago by git

  • Commit changed from 64732d222ed07af48c6a61a0470825fc420b302c to 12f3dd7535d107b093f8930135a4f5077a5c8a96

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

ead1d14Merge branch 'public/12560' in 7.4.b2
12f3dd7trac 12560 more doc

comment:12 Changed 3 years ago by git

  • Commit changed from 12f3dd7535d107b093f8930135a4f5077a5c8a96 to 9ce6f573c5637b276fa859e09616be94bb30f7e5

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

9ce6f57work on Artin_Hasse exp, still not ok

comment:13 Changed 3 years ago by git

  • Commit changed from 9ce6f573c5637b276fa859e09616be94bb30f7e5 to ebee714a6ebe946ee505f6f75e5ca20db5fc1df8

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

ebee714trac 12560 better, and working

comment:14 Changed 3 years ago by git

  • Commit changed from ebee714a6ebe946ee505f6f75e5ca20db5fc1df8 to 555bcaf466a1e7f64cdf319ca1077ac14f6ed5d2

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

555bcaftrac 12560 more doctests

comment:15 Changed 3 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-7.4
  • Status changed from needs_work to needs_review

ok, ready. Needs review.

comment:16 Changed 3 years ago by chapoton

  • Description modified (diff)
  • Summary changed from Artin Hasse Exponential to Artin-Hasse exponential

comment:17 Changed 3 years ago by git

  • Commit changed from 555bcaf466a1e7f64cdf319ca1077ac14f6ed5d2 to 18a5e553e186221173f718c11c3fbaff7dc685b1

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

18a5e55trac 12560 more tests

comment:18 Changed 3 years ago by chapoton

comment:19 Changed 3 years ago by roed

  • Status changed from needs_review to needs_work

Mostly good; here are some issues to fix.

  • When prec=0, the precision should be taken from the precision of the element rather than the precision cap of the parent (the process of finding the right precision may be more involved than just copying the precision of the element; I haven't thought about what the right precision should be in terms of the derivative of the artin-hasse exponential).
  • When prec=1, the resulting p-adic element should have absolute precision 1, not the precision equal to the precision cap of the parent (probably self.parent(c) should be self.parent()(c,1)).
  • It would be good to have the reference to Thm 2.5 of Conrad's notes in the docstring.
  • It would be nice to have a test along the lines of
    sage: x = 3*Zp(3,30).random_element()
    sage: x.artin_hass_exp() == (sum(x^(p^i)/p^i for i in range(5)).exp()
    True
    

Thanks for reviving the ticket though!

comment:20 Changed 3 years ago by git

  • Commit changed from 18a5e553e186221173f718c11c3fbaff7dc685b1 to 55d09894cda0349cbf0b9cf380e4b7cf932f4771

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

8bd0943Merge branch 'public/12560' in 7.4.b3
55d0989trac 12560 more tests, not yet done

comment:21 Changed 3 years ago by chapoton

  • Commit changed from 55d09894cda0349cbf0b9cf380e4b7cf932f4771 to 38b653ee07cf4640ca68ee3a8d112859be890b55

There remains to handle your remarks about precision.

And also I am not very happy with all the imports that I have added, there may be a smarter way to avoid that.


New commits:

38b653etrac 12560 adding doctest

comment:22 Changed 2 years ago by caruso

  • Cc caruso added

I think that precision is fine.

Small other remarks:

  • Shouldn't we cpdef the function artin_hasse_exp?
  • Why do we need an external function floorlogp? Shouldn't we integrate it directy in artin_hasse_exp (and actually not call it at each iteration of the main loop)?
  • I would use None instead of 0 for the default of prec
  • It is enough to evaluate the Artin-Hasse series up to prec/self.valuation()
  • Shouldn't we cache the coefficients of the Artin-Hasse series and/or only compute them modulo pi^prec?

By the way, I think I can imagine faster algorithms for computing the Artin-Hasse exponential but it will be for another ticket.

comment:23 Changed 2 years ago by caruso

Also notice that the class pAdicGenericElement is a generic class whose instances and not only elements of Zp or Qp but also elements in finite extensions. However your code is definitely specific to Zp / Qp as its relies on integer lifts.

comment:24 Changed 2 years ago by tscrim

Comments only on the Cython aspects:

Don't include stdsage.pxi (#22896) or cysignals/signals.pxi (see, e.g., #23121).

You should use (#17668):

-        cdef Rational c = PY_NEW(Rational)
+        cdef Rational c = Rational.__new__(Rational)

With how Cython works, it is no worse to compactify:

cdef long floorlogp(long x, long b):
    """
    A fast way to find the floor of the log base ``b`` of ``x``.
    """
    cdef long t = b
    cdef long n = 0
    while t <= x:
        t *= b
        n += 1
    return n

However, isn't this just x // b since x and b are both non-negative?

-        cdef sage.rings.integer.Integer p_as_Integer
+        cdef Integer p_as_Integer
-        if self.valuation() < 1:
+        if self.valuation_c() < 1:

It would be great to use self.lift_c() instead of self.lift(), as self.lift() in all cases just redirects to self.lift_c(). However, the code is not properly set up to do this. :(

Since this is a cdef class, you can just use self._parent (which is a much faster call and cleaner Cython code).

Actually, as far as I can see, you don't need anything past

p_as_Integer = self.parent().prime()

when prec == 1 (other than maybe mpq_set_si(a[0], 1, 1)). So I would move that code block/special case before that. Actually, if I am reading the code correctly, you could do it as a special case before

a = <mpq_t *> sig_malloc(prec * sizeof(mpq_t))

comment:25 Changed 2 years ago by roed

  • Keywords sd87 added

comment:26 Changed 2 years ago by git

  • Commit changed from 38b653ee07cf4640ca68ee3a8d112859be890b55 to d6f21363c32ae4ca3f2eb85451cdde7f9a0394a3

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

e1af77fMerge branch 'public/12560' in 8.0
d6f2136trac 12560 cython cleanup

comment:27 Changed 2 years ago by chapoton

  • Milestone changed from sage-7.4 to sage-8.1

comment:28 Changed 14 months ago by roed

  • Keywords padicIMA added

comment:29 Changed 13 months ago by git

  • Commit changed from d6f21363c32ae4ca3f2eb85451cdde7f9a0394a3 to 19d96590a2563cc383fd2c369a4ef78e38ad2a05

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

344df3dFix yet another bug in conversion from QpFP to QpCR (try again)
dd5d0cdChange ccmp to not short-circuit
f87dad8Merge branch 'u/roed/ramified_extensions_of_general_p_adic_rings_and_fields' of trac.sagemath.org:sage into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields
8296e2cFix overflow issues
3de944aMerge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/general_extensions
e7a5b08Reduce further after remove
e639faeAdd keyword reduce_relative in cremove
319f6d4Remove the debugging method _unit
2e27df5Merge branch 't/23218/ramified_extensions_of_general_p_adic_rings_and_fields' into t/12560/public/12560
19d9659Alternative implementation based on Newton iteration

comment:30 Changed 13 months ago by caruso

  • Dependencies set to #23218

I've just written another implementation that solves the equation (with unknown y)

log(y) = x + x^p/p + x^(p^2)/p^2 + x^(p^3)/p^3 + ...

using a Newton scheme.

It works over any p-adic ring/field (that's why I make this ticket dependent from #23218). Moreover, it is expected to be fast as soon as there exists a fast implementation of the logarithm for this ring/field. For example:

sage: R = Zp(3,1000)
sage: x = 3 * R.random_element()
sage: %time y1 = x.artin_hasse_exp()
CPU times: user 9.14 s, sys: 0 ns, total: 9.14 s
Wall time: 9.16 s
sage: %time y2 = x.artin_hasse_exp_Newton()
CPU times: user 8 ms, sys: 4 ms, total: 12 ms
Wall time: 9.81 ms
sage: y1 == y2
True

However, with precision 20, artin_hasse_exp is faster because it is written in Cython.

comment:31 Changed 13 months ago by git

  • Commit changed from 19d96590a2563cc383fd2c369a4ef78e38ad2a05 to f69a71136d1a6e5ce7bcb4ef69571bff9f1991d0

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

f69a711Implement several algorithms

comment:32 Changed 13 months ago by caruso

I've added a "direct" implementation that just evaluates

exp(x + x^p/p + x^(p^2)/p^2 + ...)

An heuristic is used for choosing the fastest algorithm (hopefully), depending on the input and the methods available for this input.

I've also improved the computation of the Artin-Hasse series: the computation is now done modulo some power of p (and not in QQ as before) and the result is cached.

On my laptop, timings are now:

sage: R = Zp(3,1000)
sage: elt = 3 * R.random_element()
sage: %timeit elt.artin_hasse_exp()  # use the "direct" algorithm
100 loops, best of 3: 2.22 ms per loop
sage: %timeit elt.artin_hasse_exp(algorithm='direct')
100 loops, best of 3: 2.14 ms per loop
sage: %timeit elt.artin_hasse_exp(algorithm='newton')
100 loops, best of 3: 4.84 ms per loop
sage: %timeit elt.artin_hasse_exp(algorithm='series')
100 loops, best of 3: 17.4 ms per loop

And for an extension:

sage: S.<pi> = R.extension(x^2 + 3)
sage: elt = pi * S.random_element()
sage: %timeit elt.artin_hasse_exp()  # use the "series" algorithm
10 loops, best of 3: 121 ms per loop
sage: %timeit elt.artin_hasse_exp(algorithm='direct')
Traceback (most recent call last):
...
NotImplementedError: One factor of the Artin-Hasse exponential does not converge
sage: %timeit elt.artin_hasse_exp(algorithm='newton')
1 loop, best of 3: 333 ms per loop
sage: %timeit elt.artin_hasse_exp(algorithm='series')
10 loops, best of 3: 121 ms per loop

comment:33 Changed 13 months ago by roed

Great! Let me know when this is ready for review. I may wait until #23218 is merged into a beta so that I can see the changes.

comment:34 Changed 13 months ago by chapoton

  • patchbot reports 2 failing doctests
  • you need to document every single function, even with underscore names

comment:35 Changed 13 months ago by git

  • Commit changed from f69a71136d1a6e5ce7bcb4ef69571bff9f1991d0 to 8adededb9dcfef3fb0fc9e3e253564d4bf6639e1

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

8adededAdd doctests

comment:36 Changed 13 months ago by caruso

  • Status changed from needs_work to needs_review

I've added the missing doctests. The ticket is now ready for review.

comment:37 Changed 13 months ago by chapoton

You need to use

+        r"""

instead of

+        """

in every doc that contains latex commands somewhere (\log for example)

comment:38 Changed 13 months ago by chapoton

and the branch does not apply on the latest beta..

comment:39 Changed 13 months ago by git

  • Commit changed from 8adededb9dcfef3fb0fc9e3e253564d4bf6639e1 to 37e39b87484ad4687575fd3fc57beb3818ebf298

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

cd10699Fix doctest
37e39b8Merge branch 'develop' into t/12560/public/12560

comment:40 Changed 13 months ago by git

  • Commit changed from 37e39b87484ad4687575fd3fc57beb3818ebf298 to 6c20ffcbdeef22e6534e9e9f140dad9d33b35e55

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

6c20ffcRemove unnecessary imports

comment:41 Changed 13 months ago by caruso

Thanks. Should be fixed.

comment:42 Changed 13 months ago by git

  • Commit changed from 6c20ffcbdeef22e6534e9e9f140dad9d33b35e55 to 7e04ba8c69522581818a0d8a0166b5f5131454f0

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

7e04ba8Remove another import and fix doctest

comment:43 Changed 13 months ago by git

  • Commit changed from 7e04ba8c69522581818a0d8a0166b5f5131454f0 to 46b5333f53a0507210ad38a65c9e2d7e470fe456

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

46b5333typos

comment:44 Changed 13 months ago by git

  • Commit changed from 46b5333f53a0507210ad38a65c9e2d7e470fe456 to 80ebfcf09b6648bee01588ddff75d1ac913c3eeb

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

80ebfcfmore typos

comment:45 Changed 13 months ago by caruso

  • Authors changed from Mitchell Owen, Sebastian Pancrantz to Mitchell Owen, Sebastian Pancrantz, Xavier Caruso
  • Description modified (diff)

comment:46 Changed 13 months ago by git

  • Commit changed from 80ebfcf09b6648bee01588ddff75d1ac913c3eeb to ae8be1bb2f85e10f80539477d5a0b93dc228ed65

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

ae8be1bAdd some documentation

comment:47 Changed 13 months ago by chapoton

typo:

is not is the domain of convergence of the

comment:48 Changed 13 months ago by git

  • Commit changed from ae8be1bb2f85e10f80539477d5a0b93dc228ed65 to a67faa7e5626ff57cfea9757f2a2c992356ef51e

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

a67faa7Typo

comment:49 Changed 12 months ago by git

  • Commit changed from a67faa7e5626ff57cfea9757f2a2c992356ef51e to b0c787d27566f83f7f0a035bbe3eb8c3c84f547e

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

db3de67Merge branch 'develop' into t/12560/public/12560
b0c787dSmall fixes (after David's review on Zulip)

comment:50 Changed 12 months ago by git

  • Commit changed from b0c787d27566f83f7f0a035bbe3eb8c3c84f547e to 224a944ef398c43241ec2488edc1b2f511e7e345

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

357f270Remove reference from padic_generic_element.pyx
224a944Small fixes

comment:51 Changed 12 months ago by git

  • Commit changed from 224a944ef398c43241ec2488edc1b2f511e7e345 to 89cd40cbee77b5e877a86688828299e53600fe47

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

89cd40cFix precision in _AHE_newton

comment:52 Changed 12 months ago by chapoton

  • Dependencies #23218 deleted
  • Milestone changed from sage-8.1 to sage-8.4

this seems to make some patchbots turn crazy, for some reason...

comment:53 Changed 12 months ago by caruso

I don't see anything in the ticket that is executed at startup, except this line:

_AHE_coefficients_cache = { }

but I don't except this to cause slowness.

comment:54 Changed 12 months ago by chapoton

This is very probably not the fault of anything in this ticket. Probably a new bug of the patchbot, maybe on the server side..

comment:55 Changed 12 months ago by roed

  • Reviewers set to David Roe
  • Status changed from needs_review to positive_review

I ran tests locally and they all passed. Looks good to me.

comment:56 Changed 12 months ago by vbraun

  • Branch changed from public/12560 to 89cd40cbee77b5e877a86688828299e53600fe47
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:57 Changed 11 months ago by jdemeyer

  • Commit 89cd40cbee77b5e877a86688828299e53600fe47 deleted

Is "Sebastian Pancrantz" a typo for "Sebastian Pancratz"?

comment:58 Changed 11 months ago by jdemeyer

  • Authors changed from Mitchell Owen, Sebastian Pancrantz, Xavier Caruso to Mitchell Owen, Sebastian Pancratz, Xavier Caruso

I'm assuming that it is, correct me if I'm wrong.

comment:59 Changed 11 months ago by jdemeyer

  • Cc spancratz added

comment:60 Changed 11 months ago by embray

  • Milestone changed from sage-8.4 to sage-8.5

This should be re-targeted for 8.5.

Note: See TracTickets for help on using tickets.