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.
