Hi Ondrej, I was a little busy with my university work within last two days, so I couldn't reply to this email. Sorry for that.
I noticed that you have created two issues, both of the equation types are not implemented. I was more focusing on the deliverables iin the proposal, so I didn't try to solve those types. But I still have 10 days so, I can solve them. Also without just trying to represent a number as a sum of squares I am trying to implement this<http://reference.wolfram.com/mathematica/ref/PowersRepresentations.html>general functionality. As soon as I finish that I will start on the issues. And I will update the wiki as Aaron suggested. Regards, Thilina. On Wed, Sep 4, 2013 at 12:58 AM, Ondřej Čertík <ondrej.cer...@gmail.com>wrote: > 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. > -- 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.
