And I will try to find how I can implement solving systems of Diophantine equations. If we run out of time for that, I can do it after the deadline. It's a nice addition to the module.
Regards, Thilina On Fri, Sep 6, 2013 at 8:52 AM, Thilina Rathnayake <[email protected]>wrote: > 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 <[email protected]>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 >> <[email protected]> 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 <[email protected]> >> 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 <[email protected]> >> wrote: >> >> > On Thu, Aug 29, 2013 at 7:19 PM, Thilina Rathnayake >> >> > <[email protected]> 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 <[email protected]> >> >> >> 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 >> >> >>> <[email protected]> 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 [email protected]. >> > To post to this group, send email to [email protected]. >> > 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 [email protected]. >> To post to this group, send email to [email protected]. >> 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 [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
