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<https://github.com/thilinarmtb/sympy/tree/Diophantine_Equation_Module_II>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<http://code.google.com/p/sympy/issues/detail?id=3968> . 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 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.
