Repository: sympy/sympy
Pull request: Convert more Pow expressions to field elements
#### References to other Issues or PRs

Fixes #13947

#### Brief description of what is fixed or changed

The `FracField._rebuild_expr` method did not try hard enough to express a given Pow in terms of field generators: it just expected the exponent to be integer, and the base be in the field. This missed, for example, that `Z(2**pi)` contains `2**(-pi)`. Now the Pow and ExpBase instances are treated more carefully, by comparing their bases to the bases of Pow or ExpBase among generators, and seeking an integer ratio of exponents.

Problem statement:
integrate(a**t /(a**t+1), t) sucess but a**(t-s)/(a**t+1) fail 
No matter whether `conds='none'`.

``` python
import sympy as sm
print(sm.__version__)
# 1.1.1
from sympy import *
a, t, s = symbols('a t s')
f = a**t/(a**t+1)
integrate(f, t)
# >> log(a**t + 1)/log(a)
g = a**(t-s)/(a**t+1) 
integrate(g, t)
# hoping : a**(-s) log(a**t + 1)/log(a)
# but failed:
# CoercionFailed: can't convert exp(-s*log(a)) of type exp to ZZ(log(a),exp(s*log(a)))
```

And the error stack is
```
---------------------------------------------------------------------------
CoercionFailed                            Traceback (most recent call last)
<ipython-input-35-ff749dece9c9> in <module>()
----> 1 integrate(g, t)

/usr/lib/python3.5/site-packages/sympy/integrals/integrals.py in integrate(*args, **kwargs)
   1293     if isinstance(integral, Integral):
   1294         return integral.doit(deep=False, meijerg=meijerg, conds=conds,
-> 1295                              risch=risch, manual=manual)
   1296     else:
   1297         return integral

/usr/lib/python3.5/site-packages/sympy/integrals/integrals.py in doit(self, **hints)
    484                     function, xab[0],
    485                     meijerg=meijerg1, risch=risch, manual=manual,
--> 486                     conds=conds)
    487                 if antideriv is None and meijerg1 is True:
    488                     ret = try_meijerg(function, xab)

/usr/lib/python3.5/site-packages/sympy/integrals/integrals.py in _eval_integral(self, f, x, meijerg, risch, manual, conds)
    778         if risch is not False:
    779             try:
--> 780                 result, i = risch_integrate(f, x, separate_integral=True, conds=conds)
    781             except NotImplementedError:
    782                 pass

/usr/lib/python3.5/site-packages/sympy/integrals/risch.py in risch_integrate(f, x, extension, handle_first, separate_integral, rewrite_complex, conds)
   1727         fa, fd = fa.cancel(fd, include=True)
   1728         if case == 'exp':
-> 1729             ans, i, b = integrate_hyperexponential(fa, fd, DE, conds=conds)
   1730         elif case == 'primitive':
   1731             ans, i, b = integrate_primitive(fa, fd, DE)

/usr/lib/python3.5/site-packages/sympy/integrals/risch.py in integrate_hyperexponential(a, d, DE, z, conds)
   1457 
   1458     g1, h, r = hermite_reduce(a, d, DE)
-> 1459     g2, b = residue_reduce(h[0], h[1], DE, z=z)
   1460     if not b:
   1461         i = cancel(a.as_expr()/d.as_expr() - (g1[1]*derivation(g1[0], DE) -

/usr/lib/python3.5/site-packages/sympy/integrals/risch.py in residue_reduce(a, d, DE, z, invert)
   1215     z = z or Dummy('z')
   1216     a, d = a.cancel(d, include=True)
-> 1217     a, d = a.to_field().mul_ground(1/d.LC()), d.to_field().mul_ground(1/d.LC())
   1218     kkinv = [1/x for x in DE.T[:DE.level]] + DE.T[:DE.level]
   1219 

/usr/lib/python3.5/site-packages/sympy/polys/polytools.py in mul_ground(f, coeff)
   1204         """
   1205         if hasattr(f.rep, 'mul_ground'):
-> 1206             result = f.rep.mul_ground(coeff)
   1207         else:  # pragma: no cover
   1208             raise OperationNotSupported(f, 'mul_ground')

/usr/lib/python3.5/site-packages/sympy/polys/polyclasses.py in mul_ground(f, c)
    405     def mul_ground(f, c):
    406         """Multiply ``f`` by a an element of the ground domain. """
--> 407         return f.per(dmp_mul_ground(f.rep, f.dom.convert(c), f.lev, f.dom))
    408 
    409     def quo_ground(f, c):

/usr/lib/python3.5/site-packages/sympy/polys/domains/domain.py in convert(self, element, base)
    156                     pass
    157 
--> 158         raise CoercionFailed("can't convert %s of type %s to %s" % (element, type(element), self))
    159 
    160     def of_type(self, element):

CoercionFailed: can't convert exp(-s*log(a)) of type exp to ZZ(log(a),exp(s*log(a)))
```

Hints from issue discussion:
I don't know much about `integral` module so I read `integral.py` file and saw we can try to integrate with different methods, namely: `Full Risch algorithm`, `The Meijer G-Function algorithm` and `The "manual integration" algorithm`.
While i was getting error with first two, with `manual integration`i got :
 
`>>> integrate(g, t ,manual = 1)`
`Piecewise((zoo*Piecewise((zoo*a**t, Eq(log(a), 0)), (log(a**t*log(a) + log(a))/log(a), True)), Eq(a**s, 0)), (a**(-s)*log(a**t + 1)/log(a), True))`

Which is even better result than expected I think (because `a = 0` is in the domain so returning integral at that point is not that bad), though I am confused why there is `zoo` instead of `oo` (maybe because `oo ⊂ zoo`). 
So, **if I am correct**, issue reduces to why can't the the other methods cant evaluate the integral and if they cant then why not pass it to another algo ?

The error here is a bug. Usually integrate does pass on to the different algorithms until it finds one that works, but if there is an exception that isn't expected, it results in a crash. So the issue here should be to fix the bug. 
@asmeurer  +1. So should it be solved by one best algorithm or just print maximum solved equation from the all possible algorithms as @jashan498  stated. Because I think that most precious and reliable algorithms are had been used in the module already. If these algorithms can't solve it more then it should return as much they can solve. I would like to work on this so can you guide me up? I have the knowledge of some of the integral algorithms that are looking in `integrals.py`
BTW `a**(t+s)/(a**t+1)` works so I guess may something about zero detection wrong ?
Anyway thank you fix the bug.
@asmeurer I would like to fix this bug. Can you please guide me?
Looks like the polys code isn't recognizing that `exp(-s*log(a))` is `1/exp(s*log(a))`. 
A simpler case

```pytb
>>> ZZ.frac_field(exp(x))(exp(-x))
Traceback (most recent call last):
  File "./sympy/polys/fields.py", line 221, in _rebuild
    return domain.convert(expr)
  File "./sympy/polys/domains/domain.py", line 145, in convert
    return self.from_sympy(element)
  File "./sympy/polys/domains/gmpyintegerring.py", line 39, in from_sympy
    raise CoercionFailed("expected an integer, got %s" % a)
sympy.polys.polyerrors.CoercionFailed: expected an integer, got exp(-x)

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "./sympy/polys/fields.py", line 234, in from_expr
    frac = self._rebuild_expr(expr, mapping)
  File "./sympy/polys/fields.py", line 228, in _rebuild_expr
    return _rebuild(sympify(expr))
  File "./sympy/polys/fields.py", line 224, in _rebuild
    return domain.get_field().convert(expr)
  File "./sympy/polys/domains/domain.py", line 145, in convert
    return self.from_sympy(element)
  File "./sympy/polys/domains/gmpyrationalfield.py", line 45, in from_sympy
    raise CoercionFailed("expected `Rational` object, got %s" % a)
sympy.polys.polyerrors.CoercionFailed: expected `Rational` object, got exp(-x)

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "./sympy/polys/domains/domain.py", line 84, in __call__
    return self.new(*args)
  File "./sympy/polys/domains/fractionfield.py", line 40, in new
    return self.field.field_new(element)
  File "./sympy/polys/fields.py", line 199, in field_new
    return self.from_expr(element)
  File "./sympy/polys/fields.py", line 236, in from_expr
    raise ValueError("expected an expression convertible to a rational function in %s, got %s" % (self, expr))
ValueError: expected an expression convertible to a rational function in Rational function field in exp(x) over ZZ with lex order, got exp(-x)
```

Commit message: Convert more Pow expressions to field elements

Fixes #13947

The `FracField._rebuild_expr` method did not try hard enough to express
a given Pow in terms of field generators: it just expected the exponent
to be integer, and the base be in the field. This missed, for example,
that `Z(2**pi)` contains `2**(-pi)`. Now the Pow and ExpBase instances
are treated more carefully, by comparing their bases to the bases of
Pow or ExpBase among generators, and seeking an integer ratio of exponents.

Patch to review:
diff --git a/sympy/integrals/tests/test_risch.py b/sympy/integrals/tests/test_risch.py
index 821338146a76..f8b9d29c06a5 100644
--- a/sympy/integrals/tests/test_risch.py
+++ b/sympy/integrals/tests/test_risch.py
@@ -353,6 +353,13 @@ def test_integrate_hyperexponential_returns_piecewise():
     # TODO: Add a test where two different parts of the extension use a
     # Piecewise, like y**x + z**x.
 
+def test_issue_13947():
+    a, t, s = symbols('a t s')
+    assert risch_integrate(2**(-pi)/(2**t + 1), t) == \
+        2**(-pi)*t - 2**(-pi)*log(2**t + 1)/log(2)
+    assert risch_integrate(a**(t - s)/(a**t + 1), t) == \
+        exp(-s*log(a))*log(a**t + 1)/log(a)
+
 def test_integrate_primitive():
     DE = DifferentialExtension(extension={'D': [Poly(1, x), Poly(1/x, t)],
         'Tfuncs': [log]})
diff --git a/sympy/polys/fields.py b/sympy/polys/fields.py
index 1917501d57ee..8927724ad738 100644
--- a/sympy/polys/fields.py
+++ b/sympy/polys/fields.py
@@ -6,8 +6,10 @@
 
 from sympy.core.compatibility import is_sequence, reduce, string_types
 from sympy.core.expr import Expr
+from sympy.core.mod import Mod
 from sympy.core.symbol import Symbol
 from sympy.core.sympify import CantSympify, sympify
+from sympy.functions.elementary.exponential import ExpBase
 from sympy.polys.rings import PolyElement
 from sympy.polys.orderings import lex
 from sympy.polys.polyerrors import CoercionFailed
@@ -204,6 +206,8 @@ def field_new(self, element):
 
     def _rebuild_expr(self, expr, mapping):
         domain = self.domain
+        powers = tuple((gen, *gen.as_base_exp()) for gen in mapping.keys()
+            if gen.is_Pow or isinstance(gen, ExpBase))
 
         def _rebuild(expr):
             generator = mapping.get(expr)
@@ -214,16 +218,24 @@ def _rebuild(expr):
                 return reduce(add, list(map(_rebuild, expr.args)))
             elif expr.is_Mul:
                 return reduce(mul, list(map(_rebuild, expr.args)))
-            elif expr.is_Pow and expr.exp.is_Integer:
-                return _rebuild(expr.base)**int(expr.exp)
-            else:
-                try:
-                    return domain.convert(expr)
-                except CoercionFailed:
-                    if not domain.is_Field and domain.has_assoc_Field:
-                        return domain.get_field().convert(expr)
-                    else:
-                        raise
+            elif expr.is_Pow or isinstance(expr, ExpBase):
+                b, e = expr.as_base_exp()
+                # look for bg**eg whose integer power may be b**e
+                choices = tuple((gen, bg, eg) for gen, bg, eg in powers
+                    if bg == b and Mod(e, eg) == 0)
+                if len(choices) > 0:
+                    gen, bg, eg = choices[0]
+                    return mapping.get(gen)**(e/eg)
+                elif e.is_Integer:
+                    return _rebuild(expr.base)**int(expr.exp)
+
+            try:
+                return domain.convert(expr)
+            except CoercionFailed:
+                if not domain.is_Field and domain.has_assoc_Field:
+                    return domain.get_field().convert(expr)
+                else:
+                    raise
 
         return _rebuild(sympify(expr))
 
diff --git a/sympy/polys/tests/test_fields.py b/sympy/polys/tests/test_fields.py
index 92a5b5659270..eaf849b04177 100644
--- a/sympy/polys/tests/test_fields.py
+++ b/sympy/polys/tests/test_fields.py
@@ -1,6 +1,6 @@
 """Test sparse rational functions. """
 
-from sympy.polys.fields import field, sfield, FracField
+from sympy.polys.fields import field, sfield, FracField, FracElement
 from sympy.polys.rings import ring
 from sympy.polys.domains import ZZ, QQ
 from sympy.polys.orderings import lex
@@ -129,6 +129,12 @@ def test_FracElement_from_expr():
     raises(ValueError, lambda: F.from_expr(2**x))
     raises(ValueError, lambda: F.from_expr(7*x + sqrt(2)))
 
+    assert isinstance(ZZ[2**x].get_field().convert(2**(-x)),
+        FracElement)
+    assert isinstance(ZZ[x**2].get_field().convert(x**(-6)),
+        FracElement)
+
+
 def test_FracElement__lt_le_gt_ge__():
     F, x, y = field("x,y", ZZ)
 


Code review comments:
diff_hunk: @@ -214,16 +218,24 @@ def _rebuild(expr):
                 return reduce(add, list(map(_rebuild, expr.args)))
             elif expr.is_Mul:
                 return reduce(mul, list(map(_rebuild, expr.args)))
-            elif expr.is_Pow and expr.exp.is_Integer:
-                return _rebuild(expr.base)**int(expr.exp)
-            else:
-                try:
-                    return domain.convert(expr)
-                except CoercionFailed:
-                    if not domain.is_Field and domain.has_assoc_Field:
-                        return domain.get_field().convert(expr)
-                    else:
-                        raise
+            elif expr.is_Pow or isinstance(expr, ExpBase):
+                b, e = expr.as_base_exp()
+                # look for bg**eg whose integer power may be b**e
+                choices = tuple((gen, bg, eg) for gen, bg, eg in powers
path: sympy/polys/fields.py
text: @user1:
This could have `for gen, (bg, eg) in powers` if `*` is omitted from `*gen.as_base_exp()` above.