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.
