#12560 closed enhancement (fixed)
ArtinHasse exponential
Reported by:  magfrump  Owned by:  roed 

Priority:  major  Milestone:  sage8.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 )
Add ArtinHasse exponential to Zp, Qp and their extensions.
Attachments (1)
Change History (61)
Changed 7 years ago by
comment:1 Changed 7 years ago by
 Status changed from new to needs_review
comment:2 followup: ↓ 3 Changed 7 years ago by
comment:3 in reply to: ↑ 2 Changed 7 years ago by
(1) agreed
(2) also agreed, I'm planning to add some doctests to that effect today.
comment:4 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:5 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:6 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:7 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:8 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:9 Changed 3 years ago by
Ping. This looks like lowhanging fruit; it just needs some more convincing doctests.
comment:10 Changed 3 years ago by
 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:
64732d2  trac 12560 ArtinHasse exponential (not compiling)

comment:11 Changed 3 years ago by
 Commit changed from 64732d222ed07af48c6a61a0470825fc420b302c to 12f3dd7535d107b093f8930135a4f5077a5c8a96
comment:12 Changed 3 years ago by
 Commit changed from 12f3dd7535d107b093f8930135a4f5077a5c8a96 to 9ce6f573c5637b276fa859e09616be94bb30f7e5
Branch pushed to git repo; I updated commit sha1. New commits:
9ce6f57  work on Artin_Hasse exp, still not ok

comment:13 Changed 3 years ago by
 Commit changed from 9ce6f573c5637b276fa859e09616be94bb30f7e5 to ebee714a6ebe946ee505f6f75e5ca20db5fc1df8
Branch pushed to git repo; I updated commit sha1. New commits:
ebee714  trac 12560 better, and working

comment:14 Changed 3 years ago by
 Commit changed from ebee714a6ebe946ee505f6f75e5ca20db5fc1df8 to 555bcaf466a1e7f64cdf319ca1077ac14f6ed5d2
Branch pushed to git repo; I updated commit sha1. New commits:
555bcaf  trac 12560 more doctests

comment:15 Changed 3 years ago by
 Milestone changed from sage6.4 to sage7.4
 Status changed from needs_work to needs_review
ok, ready. Needs review.
comment:16 Changed 3 years ago by
 Description modified (diff)
 Summary changed from Artin Hasse Exponential to ArtinHasse exponential
comment:17 Changed 3 years ago by
 Commit changed from 555bcaf466a1e7f64cdf319ca1077ac14f6ed5d2 to 18a5e553e186221173f718c11c3fbaff7dc685b1
Branch pushed to git repo; I updated commit sha1. New commits:
18a5e55  trac 12560 more tests

comment:18 Changed 3 years ago by
reference for the random test: theorem 2.5 of
http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/AHrootofunity.pdf
comment:19 Changed 3 years ago by
 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 artinhasse exponential).  When
prec=1
, the resulting padic element should have absolute precision 1, not the precision equal to the precision cap of the parent (probablyself.parent(c)
should beself.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
 Commit changed from 18a5e553e186221173f718c11c3fbaff7dc685b1 to 55d09894cda0349cbf0b9cf380e4b7cf932f4771
comment:21 Changed 3 years ago by
 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:
38b653e  trac 12560 adding doctest

comment:22 Changed 2 years ago by
 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 inartin_hasse_exp
(and actually not call it at each iteration of the main loop)?  I would use
None
instead of0
for the default ofprec
 It is enough to evaluate the ArtinHasse series up to
prec/self.valuation()
 Shouldn't we cache the coefficients of the ArtinHasse series and/or only compute them modulo
pi^prec
?
By the way, I think I can imagine faster algorithms for computing the ArtinHasse exponential but it will be for another ticket.
comment:23 Changed 2 years ago by
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 23 months ago by
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 nonnegative?
 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 21 months ago by
 Keywords sd87 added
comment:26 Changed 21 months ago by
 Commit changed from 38b653ee07cf4640ca68ee3a8d112859be890b55 to d6f21363c32ae4ca3f2eb85451cdde7f9a0394a3
comment:27 Changed 20 months ago by
 Milestone changed from sage7.4 to sage8.1
comment:28 Changed 9 months ago by
 Keywords padicIMA added
comment:29 Changed 8 months ago by
 Commit changed from d6f21363c32ae4ca3f2eb85451cdde7f9a0394a3 to 19d96590a2563cc383fd2c369a4ef78e38ad2a05
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
344df3d  Fix yet another bug in conversion from QpFP to QpCR (try again)

dd5d0cd  Change ccmp to not shortcircuit

f87dad8  Merge 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

8296e2c  Fix overflow issues

3de944a  Merge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/general_extensions

e7a5b08  Reduce further after remove

e639fae  Add keyword reduce_relative in cremove

319f6d4  Remove the debugging method _unit

2e27df5  Merge branch 't/23218/ramified_extensions_of_general_p_adic_rings_and_fields' into t/12560/public/12560

19d9659  Alternative implementation based on Newton iteration

comment:30 Changed 8 months ago by
 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 padic 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 8 months ago by
 Commit changed from 19d96590a2563cc383fd2c369a4ef78e38ad2a05 to f69a71136d1a6e5ce7bcb4ef69571bff9f1991d0
Branch pushed to git repo; I updated commit sha1. New commits:
f69a711  Implement several algorithms

comment:32 Changed 8 months ago by
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 ArtinHasse 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 ArtinHasse 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 8 months ago by
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 8 months ago by
 patchbot reports 2 failing doctests
 you need to document every single function, even with underscore names
comment:35 Changed 8 months ago by
 Commit changed from f69a71136d1a6e5ce7bcb4ef69571bff9f1991d0 to 8adededb9dcfef3fb0fc9e3e253564d4bf6639e1
Branch pushed to git repo; I updated commit sha1. New commits:
8adeded  Add doctests

comment:36 Changed 8 months ago by
 Status changed from needs_work to needs_review
I've added the missing doctests. The ticket is now ready for review.
comment:37 Changed 8 months ago by
You need to use
+ r"""
instead of
+ """
in every doc that contains latex commands somewhere (\log
for example)
comment:38 Changed 8 months ago by
and the branch does not apply on the latest beta..
comment:39 Changed 8 months ago by
 Commit changed from 8adededb9dcfef3fb0fc9e3e253564d4bf6639e1 to 37e39b87484ad4687575fd3fc57beb3818ebf298
comment:40 Changed 8 months ago by
 Commit changed from 37e39b87484ad4687575fd3fc57beb3818ebf298 to 6c20ffcbdeef22e6534e9e9f140dad9d33b35e55
Branch pushed to git repo; I updated commit sha1. New commits:
6c20ffc  Remove unnecessary imports

comment:41 Changed 8 months ago by
Thanks. Should be fixed.
comment:42 Changed 8 months ago by
 Commit changed from 6c20ffcbdeef22e6534e9e9f140dad9d33b35e55 to 7e04ba8c69522581818a0d8a0166b5f5131454f0
Branch pushed to git repo; I updated commit sha1. New commits:
7e04ba8  Remove another import and fix doctest

comment:43 Changed 8 months ago by
 Commit changed from 7e04ba8c69522581818a0d8a0166b5f5131454f0 to 46b5333f53a0507210ad38a65c9e2d7e470fe456
Branch pushed to git repo; I updated commit sha1. New commits:
46b5333  typos

comment:44 Changed 8 months ago by
 Commit changed from 46b5333f53a0507210ad38a65c9e2d7e470fe456 to 80ebfcf09b6648bee01588ddff75d1ac913c3eeb
Branch pushed to git repo; I updated commit sha1. New commits:
80ebfcf  more typos

comment:45 Changed 8 months ago by
 Description modified (diff)
comment:46 Changed 8 months ago by
 Commit changed from 80ebfcf09b6648bee01588ddff75d1ac913c3eeb to ae8be1bb2f85e10f80539477d5a0b93dc228ed65
Branch pushed to git repo; I updated commit sha1. New commits:
ae8be1b  Add some documentation

comment:47 Changed 8 months ago by
typo:
is not is the domain of convergence of the
comment:48 Changed 8 months ago by
 Commit changed from ae8be1bb2f85e10f80539477d5a0b93dc228ed65 to a67faa7e5626ff57cfea9757f2a2c992356ef51e
Branch pushed to git repo; I updated commit sha1. New commits:
a67faa7  Typo

comment:49 Changed 7 months ago by
 Commit changed from a67faa7e5626ff57cfea9757f2a2c992356ef51e to b0c787d27566f83f7f0a035bbe3eb8c3c84f547e
comment:50 Changed 7 months ago by
 Commit changed from b0c787d27566f83f7f0a035bbe3eb8c3c84f547e to 224a944ef398c43241ec2488edc1b2f511e7e345
comment:51 Changed 7 months ago by
 Commit changed from 224a944ef398c43241ec2488edc1b2f511e7e345 to 89cd40cbee77b5e877a86688828299e53600fe47
Branch pushed to git repo; I updated commit sha1. New commits:
89cd40c  Fix precision in _AHE_newton

comment:52 Changed 7 months ago by
 Dependencies #23218 deleted
 Milestone changed from sage8.1 to sage8.4
this seems to make some patchbots turn crazy, for some reason...
comment:53 Changed 7 months ago by
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 7 months ago by
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 7 months ago by
 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 7 months ago by
 Branch changed from public/12560 to 89cd40cbee77b5e877a86688828299e53600fe47
 Resolution set to fixed
 Status changed from positive_review to closed
comment:57 Changed 6 months ago by
 Commit 89cd40cbee77b5e877a86688828299e53600fe47 deleted
Is "Sebastian Pancrantz" a typo for "Sebastian Pancratz"?
comment:59 Changed 6 months ago by
 Cc spancratz added
comment:60 Changed 6 months ago by
 Milestone changed from sage8.4 to sage8.5
This should be retargeted for 8.5.
Two points, one trivial and one not:
(1) Shouldn't it be "ArtinHasse exponential" and not "Artin Hasse Exponential"?
(2) There really aren't any tests which demonstrate that what the function returns is actually the AH exp, as opposed to some other similarlooking element in the ring. Probably there should be something in TESTS: which verifies some known properties.