Hi, How difficult would be to implement a solver for systems of Diophantine equations? It looks like one would use the Groebner basis to reduce the problem to a sequence of simpler problems.
I created issues for equation that can't be solved yet: http://code.google.com/p/sympy/issues/list?q=label:Diophantine otherwise I didn't find any bugs so far. Ondrej On Fri, Aug 30, 2013 at 11:29 AM, Thilina Rathnayake <thilina.r...@gmail.com> wrote: > Hi Aaron, > > Thanks for the reply, I'll return all the four solutions then. > > Hope we can come up with a neat fix to the bug. > > Regards, > Thilina > > > > > On Fri, Aug 30, 2013 at 7:59 AM, Aaron Meurer <asmeu...@gmail.com> wrote: >> >> I looked into the bug, and I can see what the issue is and how it >> should be fixed, but I'm not sure what the best way to actually do it >> is. Mateusz would be the best person to say, as he wrote all that >> code. See the issue page for more details, but basically any solution >> I can think of requires implementing a bunch of functionality (except >> for maybe some really hackish ones). >> >> Aaron Meurer >> >> On Thu, Aug 29, 2013 at 7:57 PM, Aaron Meurer <asmeu...@gmail.com> wrote: >> > On Thu, Aug 29, 2013 at 7:19 PM, Thilina Rathnayake >> > <thilina.r...@gmail.com> wrote: >> >> Hi Everyone, >> >> >> >> I have completed most of my work related to Diophantine equation >> >> Module. It >> >> will be really >> >> helpful if you can test my current work in Github. Some of them are >> >> already >> >> merged in master. >> >> But I recommend using the code from this branch since it contains fixes >> >> for >> >> some bugs and >> >> considerably faster due to the usage of `sqrt_mod()` function for >> >> solving >> >> quadratic congruences. >> >> >> >> Also, Please use Python2. Otherwise you will come across this bug. >> >> >> >> FUNCTIONS >> >> ========= >> >> >> >> Main routine of the Diophantine Module is `diophantine()`. You can use >> >> `diop_solve()` also. >> >> Both of the function has to be imported from >> >> `sympy.solvers.diophantine` >> >> >> >>> In [1]: from sympy.solvers.diophantine import diop_solve, diophantine >> >> >> >> >> >> Difference between diophantine() and diop_solve() is that diophantine() >> >> solves the input equation >> >> by factorizing and diop_solve()) try to solve the equation as is. For >> >> example, if the input equation >> >> is `y**2 - 7*x*y`, diop_solve() try to solve this by assuming this as a >> >> quadratic binary form and >> >> diophantine() works with the factorization y*(y - 7*x). >> >> >> >>> In [2]: from sympy.abc import x, y, z >> >>> >> >>> In [3]: diophantine(y**2 - 7*x*y) >> >>> Out[3]: set([(n₁, 0), (-t, -7⋅t)]) >> >>> >> >>> In [4]: diop_solve(y**2 - 7*x*y) >> >>> Out[4]: set([(-t, 0), (-t, -7⋅t)]) >> >> >> >> >> >> In general, these methods give different results and diophantine() adds >> >> more >> >> coverage. It's always >> >> better to use diophantine() rather than diop_solve(). >> >> >> >> Summary of some of the internal functions used by the module >> >> >> >> ------------------------------------------------------------------------------------------ >> >> >> >> There is no need to use these functions directly for testing. `eq` is >> >> an >> >> expression which is assumed to >> >> be zero. D, N are integers. >> >> >> >> diop_linear(eq) -- Solves linear diophantine equations >> >> diop_quadratic(eq) -- Solves binary quadratic forms >> >> diop_ternary_quadratic(eq) -- Solves the ternary quadratic forms >> >> diop_ternary_quadratic_norma(eq) -- Solves the specail ternary >> >> quadratic >> >> form, ax**2 + by**2 + cz**2 = 0 >> >> >> >> Following functions are associated with the Pell equation. These are >> >> called >> >> directly / indirectly by >> >> diop_quadratic(). >> >> >> >> find_DN(eq) -- Return D, N such that input equation can be written as >> >> x**2 - >> >> D*y**2 = N >> >> diop_DN(D, N) -- Solves the equation x**2 - D*y**2 = N >> >> >> >> >> >> EQUATION TYPES >> >> ============== >> >> >> >> Currently following types of equations are implemented. All the >> >> coefficients(a, b, c, .., D) involved >> >> are integers. >> >> >> >> [1] Linear Diophantine Equations: Equations of the form ax + by + cz + >> >> .... >> >> = m >> >> [2] Binary Quadratic Equations: Equations of the form ax**2 + bx*y + >> >> cy**2 + >> >> dx + ey + f = 0 >> >> Especially give attention to the equations of the form x**2 - >> >> D*y**2 - >> >> N = 0, which is the general >> >> Pell equation. >> >> >> >> [3] Ternary Quadratic Equations: Equations of the form ax**2 + by**2 + >> >> cz**2 >> >> + dxy + eyz + fxz = 0 >> >> >> >> Currently, Implementation of ternary quadratic forms return a partial >> >> solution. I didn't find any reference >> >> which describes how to implement the complete solution. I am not even >> >> sure >> >> whether that's possible. >> >> Complete solution is a finite number of parametrized tuples, (x, y, z) >> >> using >> >> two parameters. >> >> Currently, diophantine() returns only one parametrized tuple. >> >> >> >> SPECIAL NOTES >> >> ============= >> >> >> >> * Both diophantine() and diop_solve() return a set of tuples. Values in >> >> the >> >> output tuples are arranged in >> >> the sorted order of variables used. For example, >> >> >> >>> In [5]: diop_solve(x**2 + 2*y**2 - 3) >> >>> Out[5]: set([(-1, -1), (-1, 1), (1, -1), (1, 1)]) >> >> >> >> >> >> Output tuples in the set are in the order (x, y), i.e. (-1, 1) >> >> represent >> >> the solution x = -1 and y = 1. >> >> >> >> * diop_ternary_quadratic_normal() and diop_ternary_quadratic() assume >> >> that >> >> inputs are in the exact >> >> form as they are supposed to be, i.e they will contain exactly three >> >> variables. If by any chance, internal >> >> routines call these two functions with less than three variables, it >> >> will >> >> cause an error. This can be avoided >> >> by using diophantine() instead of diop_solve(). >> >> >> >> >> >> THINGS TO BE FINALIZED >> >> ==================== >> >> >> >> * When we know that (x, y), (-x, y), (-x, -y), (x, -y) are all >> >> solutions for >> >> a given equation should we return >> >> all the four solutions or just one? ( For example, x**2 - 2*y**2 - 3 = >> >> 0) >> > >> > I would return all four. It is easy to filter out the ones you don't >> > want, but not returning all the solutions looks like a bug. >> > >> > Aaron Meurer >> > >> >> >> >> * I have limited the number of solutions found for the general Pell >> >> equation >> >> and for the equations which >> >> can be converted to Pell equation. Finding all the solutions take a lot >> >> of >> >> time. >> >> >> >> * Correct way to represent parametrized solutions, as Aaron has >> >> mentioned in >> >> above mail. >> >> >> >> >> >> I am currently working on simplifying the results returned by >> >> diophantine() >> >> when the input equation can be >> >> reduced to a Pell equation. Since the results are parametrized >> >> solutions and >> >> involves square root and powers >> >> of the parameter used, these become complex very quickly. >> >> >> >> Regards, >> >> Thilina >> >> >> >> >> >> >> >> On Fri, Aug 30, 2013 at 5:48 AM, Aaron Meurer <asmeu...@gmail.com> >> >> wrote: >> >>> >> >>> That's great. One idea of something you can do next is to start >> >>> looking at how to integrate this with solve(), so that something like >> >>> >> >>> n, m = symbols('n m', integer=True) >> >>> >> >>> solve(3*n - 4*m - 1, [n, m]) >> >>> >> >>> works. This is more of a design issue than an implementation one. We >> >>> need to figure out the right way to return parameterized solutions >> >>> from solve(). >> >>> >> >>> Aaron Meurer >> >>> >> >>> >> >>> On Wed, Aug 28, 2013 at 1:44 AM, Thilina Rathnayake >> >>> <thilina.r...@gmail.com> wrote: >> >>> > Hi Ondrej, >> >>> > >> >>> > I finished the last two deliverables(generalized pythagorean >> >>> > equation >> >>> > and >> >>> > general sum of squares) >> >>> > of my project over the weekend and I think now the project is almost >> >>> > complete. But before pulling >> >>> > those new code we have to merge the current PR first. Below is it's >> >>> > link >> >>> > >> >>> > https://github.com/sympy/sympy/pull/2303 >> >>> > >> >>> > To merge this PR we have to merge pernici's PR. Below is the link of >> >>> > his >> >>> > PR. >> >>> > >> >>> > https://github.com/sympy/sympy/pull/2307 >> >>> > >> >>> > I reviewed it during the last week and since he has made some >> >>> > improvements, >> >>> > I am going through it >> >>> > once again. I don't think it will take a long time. We can merge it >> >>> > afterwards. >> >>> > >> >>> > Meanwhile I am looking for new types of equations to add to the >> >>> > Diophantine >> >>> > module and possible >> >>> > improvements in the algorithms used. I found a good book which >> >>> > contains >> >>> > various types of equations. >> >>> > >> >>> > >> >>> > >> >>> > http://books.google.lk/books/about/Diophantine_equations.html?id=QugvF7xfE-oC&redir_esc=y >> >>> > >> >>> > But it contains only a general introduction for each type of >> >>> > equation. I >> >>> > have to find another resource to >> >>> > look for the algorithms. >> >>> > >> >>> > Regards, >> >>> > Thilina >> >> >> >> > > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sympy+unsubscr...@googlegroups.com. > To post to this group, send email to sympy@googlegroups.com. > Visit this group at http://groups.google.com/group/sympy. > For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscr...@googlegroups.com. To post to this group, send email to sympy@googlegroups.com. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
