Generic p-adic log and exp

[mmasdeu]

Here is a patch which seems to fix a number of problems with the p-adic logarithm and exponential.

They are generic functions that should work with all of current p-adic types.

We get run times about x20/x80 faster than the current implementation (in the cases where the current implementation worked).

Apply

1. attachment: trac_12575_exp_logs-nowhitespace.2.patch
2. attachment: trac_12575_log_fix.patch
3. attachment: trac_12575_doctest.patch
4. attachment: trac_12575_review.patch
5. attachment: 12575_review_review.patch
6. attachment: trac_12575_review_review_review.patch

Depends on #13539
Depends on #14294

CC: @roed314

Component: padics

Keywords: exp, log

Author: Amnon Besser, Marc Masdeu, Julian Rueth

Reviewer: David Loeffler, David Roe, Julian Rueth

Merged: sage-5.9.beta2

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

[williamstein]

comment:1

This code breaks stuff elsewhere, e.g., when p=2. See this traceback I got by running "sage -t":

sage -t  devel/sage/sage/rings/finite_rings/integer_mod.pyx
**********************************************************************
File "/mnt/usb1/scratch/wstein/sage-5.0.beta2-sage.math.washington.edu-x86_64-Linux/devel/sage-main/sage/rings/finite_rings/integer_mod.pyx", line 1043:
    sage: mod(225,2^5*3^2).nth_root(4, all=True)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/wstein/sage-5.0.beta2-sage.math.washington.edu-x86_64-Linux/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/wstein/sage-5.0.beta2-sage.math.washington.edu-x86_64-Linux/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/wstein/sage-5.0.beta2-sage.math.washington.edu-x86_64-Linux/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_26[7]>", line 1, in <module>
        mod(Integer(225),Integer(2)**Integer(5)*Integer(3)**Integer(2)).nth_root(Integer(4), all=True)###line 1043:
    sage: mod(225,2^5*3^2).nth_root(4, all=True)
      File "integer_mod.pyx", line 1121, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root (sage/rings/finite_rings/integer_mod.c:9981)
        L.append(mod(self, p**k).nth_root(n, all=True, algorithm=algorithm))
      File "integer_mod.pyx", line 1194, in sage.rings.finite_rings.integer_mod.IntegerMod_abstract.nth_root (sage/rings/finite_rings/integer_mod.c:11789)
        plog = R(self).log()
      File "padic_generic_element.pyx", line 1115, in sage.rings.padics.padic_generic_element.pAdicGenericElement.log (sage/rings/padics/padic_generic_element.c:8542)
      File "padic_generic_element.pyx", line 1138, in sage.rings.padics.padic_generic_element.pAdicGenericElement._log (sage/rings/padics/padic_generic_element.c:8827)
      File "element.pyx", line 1799, in sage.structure.element.RingElement.__div__ (sage/structure/element.c:13262)
      File "coerce.pyx", line 797, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:7500)
    TypeError: unsupported operand parent(s) for '/': '2-adic Ring of fixed modulus 2^5' and 'Rational Field'
**********************************************************************

[mmasdeu]

comment:2

This time the even-nest prime is not to blame: the problem still came (as we discussed with David in SageDays36) from not being able to construct a parent of a p-adic with increased precision (in a generic way). This should be resolved when templates get implemented.

Meanwhile, I have tweaked it so that it works. It now passes all the tests in devel/sage/sage/rings.

[loefflerd]

comment:5

Applying this patch and building gives a Sphinx error message:

docstring of sage.rings.padics.padic_generic_element:1: ERROR: Unexpected indentation.

[loefflerd]

Attachment: trac_12575_fix_docs.patch.gz

Apply over previous patch

[loefflerd]

comment:6

Apply trac_12575_exp_logs.patch, trac_12575_fix_docs.patch

(for the patchbot).

The patch I've just uploaded corrects dozens of Sphinx formatting issues in padic_generic_element, so the documentation actually builds correctly and looks half right (neither of which were true before). But still this can't go in as is: the documentation of _log needs to explain what it actually does and how it relates to log; and some explanation of how the prec parameter is handled in _naive_shifted_log is needed -- the code does some calculations with the prec argument that were not at all obvious to me. So we need a third patch (on top of the two that are already here).

[mmasdeu]

comment:7

I addressed the issues you raised. The _naive_shifted_log() has been renamed to _shifted_log(), I think that it is better. Also I have eliminated the _log() function since at the end of the developing it had become too short. I included that code in the log() itself. All is included in one patch.