Opened 2 years ago
Closed 17 months ago
#23344 closed enhancement (fixed)
padic square root
Reported by:  lubicz  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  padics  Keywords:  
Cc:  roed, caruso  Merged in:  
Authors:  Xavier Caruso  Reviewers:  David Lubicz 
Report Upstream:  N/A  Work issues:  
Branch:  3085538 (Commits)  Commit:  30855382d325dabb77a7fb1033fa44ba58fbc2f1 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket implements square root over padic fields (i.e. finite extension of Qp)
Change History (33)
comment:1 Changed 2 years ago by
comment:2 followup: ↓ 3 Changed 2 years ago by
If I am not mistaken, with the version of sage I am working with (8.0.rc0), the square root is working fine for elements of Qp (even if Qp is embeded in an extension) but not for elements of an extension of Qp (not in Q_p). Continuing your example :
sage: a=L.gen() sage: sqrt(4+19*a)  NotImplementedError Traceback (most recent call last) <ipythoninput5842761a28969> in <module>() > 1 sqrt(Integer(4)+Integer(19)*a) /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/functions/other.pyc in sqrt(x, *args, **kwds) 2002 except (AttributeError, TypeError): 2003 pass > 2004 return _do_sqrt(x, *args, **kwds) 2005 2006 # register sqrt in pynac symbol_table for conversion back from other systems /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/functions/other.pyc in _do_sqrt(x, prec, extend, all) 1903 z = I 1904 else: > 1905 z = SR(x) ** one_half 1906 1907 if all: /home/lubicz/sagemath/sage/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/symbolic/expression.cpp:25800)() 3882 relational_operator(base._gobj)) 3883 else: > 3884 x = g_pow(base._gobj, nexp._gobj) 3885 return new_Expression_from_GEx(base._parent, x) 3886 /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/rings/padics/CR_template.pxi in sage.rings.padics.qadic_flint_CR.CRElement.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:20012)() 672 elif exact_exp: 673 # exact_pow_helper is defined in padic_template_element.pxi > 674 right = exact_pow_helper(&ans.relprec, self.relprec, _right, self.prime_pow) 675 if ans.relprec > self.prime_pow.ram_prec_cap: 676 ans.relprec = self.prime_pow.ram_prec_cap /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/rings/padics/padic_template_element.pxi in sage.rings.padics.qadic_flint_CR.exact_pow_helper (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:15216)() 545 exp_val = mpz_get_si((<Integer>right.valuation(p)).value) 546 elif isinstance(_right, Rational): > 547 raise NotImplementedError 548 ansrelprec[0] = relprec + exp_val 549 if exp_val > 0 and mpz_cmp_ui(p.value, 2) == 0 and relprec == 1: NotImplementedError:
Another example which motivates my tickets since I am implementing in sagemath an improved version of the AGM algorithm :
sage: R.<x>=Zq(2^10, 20) sage: sqrt(1+8*x)  NotImplementedError Traceback (most recent call last) <ipythoninput1025d75e2ffffe> in <module>() > 1 sqrt(Integer(1)+Integer(8)*x) /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/functions/other.pyc in sqrt(x, *args, **kwds) 2002 except (AttributeError, TypeError): 2003 pass > 2004 return _do_sqrt(x, *args, **kwds) 2005 2006 # register sqrt in pynac symbol_table for conversion back from other systems /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/functions/other.pyc in _do_sqrt(x, prec, extend, all) 1903 z = I 1904 else: > 1905 z = SR(x) ** one_half 1906 1907 if all: /home/lubicz/sagemath/sage/src/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/symbolic/expression.cpp:25800)() 3882 relational_operator(base._gobj)) 3883 else: > 3884 x = g_pow(base._gobj, nexp._gobj) 3885 return new_Expression_from_GEx(base._parent, x) 3886 /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/rings/padics/CR_template.pxi in sage.rings.padics.qadic_flint_CR.CRElement.__pow__ (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:20012)() 672 elif exact_exp: 673 # exact_pow_helper is defined in padic_template_element.pxi > 674 right = exact_pow_helper(&ans.relprec, self.relprec, _right, self.prime_pow) 675 if ans.relprec > self.prime_pow.ram_prec_cap: 676 ans.relprec = self.prime_pow.ram_prec_cap /home/lubicz/sagemath/sage/local/lib/python2.7/sitepackages/sage/rings/padics/padic_template_element.pxi in sage.rings.padics.qadic_flint_CR.exact_pow_helper (/home/lubicz/sagemath/sage/src/build/cythonized/sage/rings/padics/qadic_flint_CR.c:15216)() 545 exp_val = mpz_get_si((<Integer>right.valuation(p)).value) 546 elif isinstance(_right, Rational): > 547 raise NotImplementedError 548 ansrelprec[0] = relprec + exp_val 549 if exp_val > 0 and mpz_cmp_ui(p.value, 2) == 0 and relprec == 1: NotImplementedError:
comment:3 in reply to: ↑ 2 Changed 2 years ago by
Replying to lubicz:
If I am not mistaken, with the version of sage I am working with (8.0.rc0), the square root is working fine for elements of Qp (even if Qp is embeded in an extension) but not for elements of an extension of Qp (not in Q_p).
I agree. The current implementation just calls off to Pari (see line 2774 in padic_generic_element.pyx
). It would be good if we could have a native implementation that worked for general extensions (not just unramified ones).
comment:4 Changed 19 months ago by
 Branch set to u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields
comment:5 Changed 19 months ago by
 Commit set to e64d891c19b4b5bb1b2b8d666f16f02ad405c67e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e64d891  added square for unramified 2adic fields

comment:6 Changed 19 months ago by
 Branch changed from u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields to u/roed/ramified_extensions_of_general_p_adic_rings_and_fields
comment:7 Changed 19 months ago by
 Commit changed from e64d891c19b4b5bb1b2b8d666f16f02ad405c67e to e3a1c866f8fa3bc534e3434ab2ca066d470b5d5d
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
ce61f64  Improve base ring injections for relative extensions of padic fields

16477d3  Make conversion from residue field work for twostep extensions of padics

1c7cc71  Fix typo in section method for base ring injection in padic twostep extensions

8be1504  Fix bugs in creduce and ccoefficients for twostep padic extensions

d53df12  Add coerce_list back in to the _populate_coercion_lists_ call in pAdicExtensionGeneric.__init__

e68beee  Fix some padic doctests

635021a  Change _poly_rep to always return the polynomial representing the element, not the unit

67c1f14  Change the internal base ring for twostep extensions to not show precision when printing, fix bug in base ring coercion

8939981  Fix problems in expansion code

e3a1c86  Merge commit '8939981e4b02ac12b86f943d93a8baef25e9af51' of git://trac.sagemath.org/sage into t/23218/general_extensions

comment:8 Changed 19 months ago by
 Commit changed from e3a1c866f8fa3bc534e3434ab2ca066d470b5d5d to 65f28536ad731c289db6a150a200d179c4f80647
comment:9 Changed 19 months ago by
 Branch changed from u/roed/ramified_extensions_of_general_p_adic_rings_and_fields to u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields
comment:10 Changed 19 months ago by
 Branch changed from u/lubicz/ramified_extensions_of_general_p_adic_rings_and_fields to u/roed/ramified_extensions_of_general_p_adic_rings_and_fields
comment:11 Changed 19 months ago by
 Branch changed from u/roed/ramified_extensions_of_general_p_adic_rings_and_fields to u/roed/23344/2adic_sqrt
comment:12 Changed 19 months ago by
Several comments:
 you don't need your function
_artin_schreier
since Sage has already methods (e.g.roots
) for solving algebraic equations in finite fields
 in the
square_root
method,prec
shouldn't be the precision cap of the parent but the actual precision of the element, no?
 in the
square_root
method, use thesqrt
method for computing the square root modulo p (by the way, I don't understand why this part is needed)
ceil((prec+1)/2.0)
is also1 + prec // 2
, isn't it?
 I would say that our recursive implementation is slower that an iterative one, but I'm not sure
 maybe, you could at the same time complete the documentation of the method
sqrt
comment:13 followup: ↓ 14 Changed 19 months ago by
By the way, this ticket only implements sqrt
for unramified extensions of Q2
, is that right? (It's not what is written in the description of the ticket.)
sage: R.<a> = Zq(5^2) sage: sqrt(1+5*a) Traceback (most recent call last): ... NotImplementedError
comment:14 in reply to: ↑ 13 Changed 19 months ago by
Replying to caruso:
By the way, this ticket only implements
sqrt
for unramified extensions ofQ2
, is that right? (It's not what is written in the description of the ticket.)
Yeah, I think that's correct. It would be nice to have it also include an implementation for other primes, but that's not currently in the code.
comment:15 Changed 19 months ago by
My answer to the first comments of Xavier:
1) artin schreier is very efficient to solve equations of the form
x2=ax+b by using a square and multiply type algorithm it shoud perform in ln(n)2 (where n is the degree of Q_q / Q_p) operations in Q_2. I don't know what is the algorithm implemented in roots but it should be less efficient, no ?
2) yes I will make the change
3) I have search through the square_root method and I could find only to lines with the keyword sqrt :
 ans = self.parent()(self.pari().sqrt())
 z = self._inv_sqrt(prec)
the first one is for calling the pari implementation and the second one is a call to the inverse square root method.
4) yes I will make the change
5) ok
6) Ok
7) I will extend the implementation for odd primes p.
Thanks for your comments and you help !
comment:16 Changed 19 months ago by
 Branch changed from u/roed/23344/2adic_sqrt to u/caruso/23344/2adic_sqrt
comment:17 Changed 19 months ago by
 Commit changed from 65f28536ad731c289db6a150a200d179c4f80647 to 61ba7013effe7fd0365f999562afc11e2386142e
I've pushed a new implementation which works over any extension of Qp
for p > 2 and any unramified extension of Q2
(the case of ramified extensions of Q2
is much more subtle).
PS: I've deleted your code; feel free to revert my changes if you think that it's appropriate.
New commits:
830dbba  Merge branch 'develop' into t/23344/23344/2adic_sqrt

61ba701  square root over almost all padic fields (except ramified extension of Q2)

comment:18 Changed 18 months ago by
 Commit changed from 61ba7013effe7fd0365f999562afc11e2386142e to 88e08b2d5d2956d0c4e33b3f4066478774d691d8
Branch pushed to git repo; I updated commit sha1. New commits:
88e08b2  square root for all padic fields

comment:19 Changed 18 months ago by
 Status changed from new to needs_review
I've extended my implementation to all padic fields (including ramified extensions of Q_2).
Needs review.
comment:20 Changed 18 months ago by
 Branch changed from u/caruso/23344/2adic_sqrt to u/lubicz/23344/2adic_sqrt
comment:21 Changed 18 months ago by
 Commit changed from 88e08b2d5d2956d0c4e33b3f4066478774d691d8 to 332fe2c09953fd794804d7b4d9437e0c1ae5f059
Branch pushed to git repo; I updated commit sha1. New commits:
332fe2c  positive review

comment:22 Changed 18 months ago by
In def _square_root(self):
 replaced parent = self.parent() by ring = self.parent()
 corrected a bug in the computation of ArtinSchreier equation (carac 2).
Pushed the changes on trac.
comment:23 Changed 18 months ago by
 Status changed from needs_review to positive_review
comment:24 Changed 18 months ago by
 Reviewers set to David Lubicz
comment:25 Changed 18 months ago by
 Status changed from positive_review to needs_work
patchbot reports failing doctests..
comment:26 Changed 18 months ago by
It looks like many of the failures result from different choices of square root, but I agree that they need to be fixed.
comment:27 Changed 18 months ago by
 Branch changed from u/lubicz/23344/2adic_sqrt to u/caruso/23344/2adic_sqrt
comment:28 Changed 18 months ago by
 Commit changed from 332fe2c09953fd794804d7b4d9437e0c1ae5f059 to 30855382d325dabb77a7fb1033fa44ba58fbc2f1
comment:29 Changed 18 months ago by
 Status changed from needs_work to needs_review
As David pointed out, the issue was due to the choice/ordering of square roots (which was not consistent when precision varies). I fixed it. Let's see what the patchbot says now.
comment:30 Changed 18 months ago by
 Description modified (diff)
comment:32 Changed 18 months ago by
 Status changed from needs_review to positive_review
OK. So, I give a positive review to this ticket again. Please change this if you disagree.
comment:33 Changed 17 months ago by
 Branch changed from u/caruso/23344/2adic_sqrt to 30855382d325dabb77a7fb1033fa44ba58fbc2f1
 Resolution set to fixed
 Status changed from positive_review to closed
Doesn't this already work? This field
L
is an example from the docstring forQp.extension
.The syntax
sqrt(L(4+19))
also works.