search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 479 forks source link

interface sympy Diophantine function(s) #16590

Closed rwst closed 9 years ago

rwst commented 10 years ago

In sympy the solution of Diophantine equations is available for several types of equations (http://docs.sympy.org/latest/modules/solvers/diophantine.html). This meta-ticket aims at

It is however not possible to directly make the resp. sympy functions fully usable with Sage, from within Sage. If desired that must be done in sympy.

Until then there is the following workaround:

sage: from sympy.solvers.diophantine import *
sage: from sympy import sympify
sage: var('x,y,m')
(x, y, m)
sage: diop_solve(sympify(x**2 + y**2 - 5))
{(-2, -1), (-2, 1), (2, -1), (2, 1)}
sage: diop_solve(sympify(x**2 - 3*y**2 - 1))
{(-sqrt(3)*(-sqrt(3) + 2)**t/2 + (-sqrt(3) + 2)**t + sqrt(3)*(sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t,
  -sqrt(3)*(-sqrt(3) + 2)**t/3 + (-sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t/2 + sqrt(3)*(sqrt(3) + 2)**t/3)}

CC: @JohnCremona

Component: number theory

Keywords: pellian, integers, solution

Author: Ralf Stephan

Branch/Commit: 9a8c2f3

Reviewer: Kannappan Sampath, Travis Scrimshaw

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

rwst commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,7 +1,7 @@
 In sympy solution of Diophantine equations is available for several types of equations. This meta-ticket aims at

 * making the resp. sympy functions fully usable with Sage
-  1. symbolic expressions
+  1. symbolic expressions (#16591)
   2. univariate polynomials
   3. multivariate polynomials
   4. quadratic forms
rwst commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-In sympy solution of Diophantine equations is available for several types of equations. This meta-ticket aims at
+In sympy the solution of Diophantine equations is available for several types of equations (http://docs.sympy.org/latest/modules/solvers/diophantine.html). This meta-ticket aims at

 * making the resp. sympy functions fully usable with Sage
   1. symbolic expressions (#16591)
rwst commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,10 +1,10 @@
 In sympy the solution of Diophantine equations is available for several types of equations (http://docs.sympy.org/latest/modules/solvers/diophantine.html). This meta-ticket aims at

-* making the resp. sympy functions fully usable with Sage
-  1. symbolic expressions (#16591)
-  2. univariate polynomials
-  3. multivariate polynomials
+* implementing a global `solve_diophantine()` function that wraps the sympy functionality and takes
+  1. symbolic expressions (up to order 2)
+  2. univariate polynomials (up to order 2)
+  3. multivariate polynomials (up to order 2)
   4. quadratic forms
-  5. lists of linear 1/2/3
-* implementing a global `solve_diophantine()` function that wraps the sympy functionality
 * where useful implementing member functions `solve_diophantine()`
+
+It is however not possible to directly make the resp. sympy functions fully usable with Sage, from within Sage. If desired that must be done in sympy.
rwst commented 10 years ago

Description changed:

--- 
+++ 
@@ -8,3 +8,17 @@
 * where useful implementing member functions `solve_diophantine()`

 It is however not possible to directly make the resp. sympy functions fully usable with Sage, from within Sage. If desired that must be done in sympy.
+
+Until then there is the following workaround:
+
+```
+sage: from sympy.solvers.diophantine import *
+sage: from sympy import sympify
+sage: var('x,y,m')
+(x, y, m)
+sage: diop_solve(sympify(x**2 + y**2 - 5))
+{(-2, -1), (-2, 1), (2, -1), (2, 1)}
+sage: diop_solve(sympify(x**2 - 3*y**2 - 1))
+{(-sqrt(3)*(-sqrt(3) + 2)**t/2 + (-sqrt(3) + 2)**t + sqrt(3)*(sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t,
+  -sqrt(3)*(-sqrt(3) + 2)**t/3 + (-sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t/2 + sqrt(3)*(sqrt(3) + 2)**t/3)}
+```
rwst commented 10 years ago
comment:5

However, the last solution shown in the workaround is incomplete, see https://github.com/sympy/sympy/issues/7671. Still, it would be good to have the functionality at hand in Sage.

rwst commented 10 years ago
comment:6
sage: sage: from sympy.solvers.diophantine import *
sage: sage: from sympy import sympify
sage: diop_solve(sympify(x*y-10))
{(-10, -1), (-5, -2), (-2, -5), (-1, -10), (1, 10), (2, 5), (5, 2), (10, 1)}

sage: solve(x*y==10,x)
[x == 10/y]
sage: assume(x,'integer')
sage: assume(y,'integer')
sage: solve(x*y==10,x,y,solution_dict=True)
([{x: 10/y}], [1])

Solve with assumption 'integer' for all variables should definitely call diop_solve(), but also the shorter solve_diophantine(expr) without assumptions should be available. Not sure what the output of [1] above means.

rwst commented 10 years ago
comment:7

Irrelevant comment deleted. Sorry.

rwst commented 10 years ago

Dependencies: #16624

rwst commented 10 years ago

Branch: u/rws/interface_sympy_diophantine_functions

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

827e50516590: add documentation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Commit: 827e505

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

e598b2c16590: fix doctests
d9989ed16590: roll back changes to quadratic_forms/; finish documentation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 827e505 to d9989ed

rwst commented 10 years ago
comment:13

This is completed IMO, modulo the review. The failing doctest depends on #16624, so I'll wait with setting 'needs review' for that.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

1568fe4Merge branch 'develop' into t/16590/interface_sympy_diophantine_function_s_
6365073shortened patch
04d8d62remove doc/src/modules/mpmath from patch; remove files via spkg-install
4c9f28816624: remove mpmath/tests/__init__.py too
056a4c1Merge branch 'public/sympy075' of trac.sagemath.org:sage into t/16590/interface_sympy_diophantine_function_s_
60f9af7Merge branch 'develop' into t/16624/public/sympy075
e6c24d316624: use standard patch script in spkg-install
8488e19Merge branch 'public/sympy075' of trac.sagemath.org:sage into t/16590/interface_sympy_diophantine_function_s_
bd23c2416590: fix merge mistake
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from d9989ed to bd23c24

rwst commented 10 years ago

Changed dependencies from #16624 to none

rwst commented 10 years ago

Upstream: Reported upstream. No feedback yet.

rwst commented 10 years ago
comment:16

Merged in #16624.

Edit: removed nonsense

rwst commented 10 years ago

Author: Ralf Stephan

rwst commented 10 years ago

Changed upstream from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.

rwst commented 10 years ago
comment:17

The x^2-9 doctest failure is only fixed in sympy master but not 0.7.5, so we would still have to wait for this fix. I would however support any reviewer that wants to have the code in Sage---just remove that doctest, the failure is not our fault.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from bd23c24 to e2ff58b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

5479f61Merge branch 'develop' into t/16590/interface_sympy_diophantine_function_s_
e2ff58b16590: cosmetics
rwst commented 9 years ago

Changed branch from u/rws/interface_sympy_diophantine_functions to u/rws/16590

rwst commented 9 years ago
comment:20

With the new sympy, also the last doctest passes. Squashed it all into one commit.

New commits:

584192416590: interface sympy Diophantine function(s)
rwst commented 9 years ago

Changed commit from e2ff58b to 5841924

rwst commented 9 years ago

Changed upstream from Fixed upstream, but not in a stable release. to none

a1031e5c-5e2c-4c90-8ba4-91be67e304df commented 9 years ago
comment:21

Some of the tests depend on ordering at the moment:

File "src/sage/symbolic/expression.pyx", line 10089, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    solve_diophantine(x^2+y^2==25)
Expected:
    [(-4, 3), (4, -3), (0, -5), (-4, -3), (0, 5), (4, 3)]
Got:
    [(4, -3), (0, -5), (-4, -3), (-4, 3), (0, 5), (4, 3)]
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 10105, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    solve_diophantine(x*y-y==10, (x,y))
Expected:
    [(6, 2), (2, 10), (3, 5), (0, -10), (-1, -5), (11, 1), (-4, -2), (-9, -1)]
Got:
    [(-1, -5), (0, -10), (-9, -1), (-4, -2), (2, 10), (11, 1), (6, 2), (3, 5)]
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 10107, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    solve_diophantine(x*y-y==10, solution_dict=True)
Expected:
    [{x: 6, y: 2},
     {x: 2, y: 10},
     {x: 3, y: 5},
     {x: 0, y: -10},
     {x: -1, y: -5},
     {x: 11, y: 1},
     {x: -4, y: -2},
     {x: -9, y: -1}]
Got:
    [{y: -5, x: -1},
     {y: -10, x: 0},
     {y: -1, x: -9},
     {y: -2, x: -4},
     {y: 10, x: 2},
     {y: 1, x: 11},
     {y: 2, x: 6},
     {y: 5, x: 3}]
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

0906224Merge branch 'develop' into t/16590/16590
395579016590: fix doctests; cosmetics
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 5841924 to 3955790

rwst commented 9 years ago
comment:23

Fixed. Why dictionaries have to be sorted to be comparable is beyond me.

rwst commented 9 years ago
comment:24

Passes all patchbot tests.

KPanComputes commented 9 years ago
comment:25

I would like to review this ticket and perhaps contribute more code around this theme. I am working on a review of this code and should be available before the end of this week. :-)

KPanComputes commented 9 years ago
comment:27

OK, so this ticket is really an interface to Sympy code and all the tests pass.

A suggestion that you might want to consider: Pell's equation is in no reasonable sense a correct attribution. I would prefer Brahmagupta-Pell equation. For historic comments, see A. Weil's book "Number Theory, An approach through history from Hammurapi to Legendre" or Whitford's book "Pell's equation" for some of the early history.

Modulo this, positive review.

rwst commented 9 years ago

Changed branch from u/rws/16590 to u/rws/16590-1

rwst commented 9 years ago

Changed commit from 3955790 to b8501cd

rwst commented 9 years ago
comment:29

I agree with the attribution change. Please add your name to the Reviewers field of the ticket. Thanks for the review.

New commits:

b8501cd16590: interface sympy Diophantine function(s)
tscrim commented 9 years ago
comment:30

Would anyone believe I actually recently have a use for this, for me coming and my combinatorial/representation theory background? :P Just a trivial push to get this into Sage.

tscrim commented 9 years ago

Reviewer: Kannappan Sampath

vbraun commented 9 years ago
comment:31

doctests depends on x/y order which is apparently random:

sage -t --long src/sage/symbolic/expression.pyx
**********************************************************************
File "src/sage/symbolic/expression.pyx", line 10122, in sage.symbolic.expression.Expression.solve_diophantine
Failed example:
    res.sort(); res
Expected:
    [{y: -1, x: -9},
     {y: -2, x: -4},
     {y: -5, x: -1},
     {y: -10, x: 0},
     {y: 10, x: 2},
     {y: 5, x: 3},
     {y: 2, x: 6},
     {y: 1, x: 11}]
Got:
    [{x: 0, y: -10},
     {x: -1, y: -5},
     {x: -4, y: -2},
     {x: -9, y: -1},
     {x: 11, y: 1},
     {x: 6, y: 2},
     {x: 3, y: 5},
     {x: 2, y: 10}]
**********************************************************************
1 item had failures:
   1 of  20 in sage.symbolic.expression.Expression.solve_diophantine
    [2394 tests, 1 failure, 31.23 s]
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from b8501cd to c2b1a59

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

c4fb08aMerge branch 'develop' into t/16590/16590-1
c2b1a5916590: fix doctest
tscrim commented 9 years ago
comment:34

This test

all(sol[i] == res[i] for i in range(len(sol)))

still depends on the order of the solutions (which is machine dependent as per Volker's note), not the (only) print order of the dicts. So I think a better test would be

all(solution in res for solution in sol)
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from c2b1a59 to 259bf76

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

259bf7616590: fix doctest
rwst commented 9 years ago
comment:36

Thanks!

tscrim commented 9 years ago
comment:37

Sorry, I just realized this isn't quite sufficient. We should also add an and len(res) == len(sol) as there could be more "solutions" in sol than there should be. Once you add that, you can set positive review. Thanks.

tscrim commented 9 years ago

Changed reviewer from Kannappan Sampath to Kannappan Sampath, Travis Scrimshaw

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 259bf76 to 9a8c2f3