I attached the code herewith as a .py file so you can easily run it.
On Tue, Jul 16, 2013 at 12:47 AM, Thilina Rathnayake <[email protected] > wrote: > Hi Ondrej, > > Thank you very much for the words of encouragement. I am implementing the > descent method. > I have used the solver you pointed out to validate answers for quadratic > Diophantine equations. > We need something which solve the the ternary quadratic equations. > > I will continue implementing the algorithm as you suggested. I think > that's the best way. > I am confident that we will find some way to validate the results. I > couldn't completely check PARI/GP <http://pari.math.u-bordeaux.fr/> > and sage. They might contain a solver for ternary quadratic forms. > > I implemented the descent algorithm but it doesn't return the correct > results. Here is the code. > > *def descent(A, B): > """ > Uses Lagrange's method to finda a solution to $w^2 = Ax^2 + By^2$. > Output a tuple $(x_0, y_0, z_0)$ which a solution to the above > equation. > This solution is used as a base to calculate all the solutions. > """ > if abs(A) > abs(B): > y, x, w = descent(B, A) > return (x, y, w) > > if A == 1: > return (1, 0, 1) > > if B == 1: > return (0, 1, 1) > > if quadratic_congruence(A, B, 0.5) != None: > r = quadratic_congruence(A, B, 0.5) > Q = (r**2 - A)//B > div = divisors(Q) > > B_0 = 0 > > for i in div: > if isinstance(sqrt(Q // i), Integer): > B_0, d = i, sqrt(Q // i) > break > > if B_0 > 0: > X, Y, W = descent(A, B_0) > return (r*X + W, B*d*Y, A*X + r*W) > > def quadratic_congruence(a, m, k=1.0): > """ > Solves the quadratic congruence $x^2 \equiv a \ (mod \ m)$. Returns the > first solution in the range $0 .. \lfloor k*m \rfloor$. > Return None if solutions do not exist. Currently uses bruteforce. > Good enough for ``m`` sufficiently small. > > TODO: An efficient algorithm should be implemented. > """ > upper_bound = floor(abs(k*m)) + 1 > > for i in range(upper_bound): > if (i**2 - a)% abs(m) == 0: > return i > > return None* > > Perhaps you could take a look at it and tell me where I have done wrong. I > tried to follow > almost the same symbols as in the algorithm. Here B_0 corresponds to B' in > the algorithm. > Please take a look at it when you have some free time. > > Thank you and best regards, > Thilina > > > On Mon, Jul 15, 2013 at 9:01 PM, Ondřej Čertík <[email protected]>wrote: > >> I see, it's the Chapter IV. >> Are you going to implement the "Sieving method" (IV.3.1)? Or the >> "descent method"? >> >> So, if I take the Pythagorean formula a^2 + b^2 = c^2, your new solver >> will be able to give me all integer solutions to this? That would be >> really cool. >> >> As far as a solver, I found this one ( >> http://www.alpertron.com.ar/QUAD.HTM). >> But it can only do equations for "x" an "y". You need equations for >> "x", "y" and "z". >> >> I would suggest that you implement the solver, and then we just check >> the solutions numerically, that should be quite easy. We will not know >> for sure that you got all the solutions, but just cite the algorithm >> reference in the docstring, so that users know what it does. That >> would be good start. If somebody later finds some other software that >> can do this, or some other reference with examples and results, we can >> make sure that it returns all the solutions. >> >> Ondrej >> >> On Sun, Jul 14, 2013 at 11:21 PM, Thilina Rathnayake >> <[email protected]> wrote: >> > This is what I use. >> > >> > “The Algorithmic resolution of Diophantine Equations”, Nigel P. Smart, >> > Chapter IV, Quadratic ternary forms. >> > >> > Here is the book: >> > >> > >> > >> > On Mon, Jul 15, 2013 at 2:20 AM, Aaron Meurer <[email protected]> >> wrote: >> >> >> >> On Sun, Jul 14, 2013 at 12:09 AM, Thilina Rathnayake >> >> <[email protected]> wrote: >> >> > Hi All, >> >> > >> >> > I am planning to implement ternary quadratic forms, i.e equations of >> the >> >> > form, >> >> > a*x**2 + by**2 + cz**2 + fxy + gyz + hzx = 0. It would be better If I >> >> > can >> >> > find >> >> > a system which currently implement this so I can validate my >> results. If >> >> > you >> >> > know >> >> > of any system which solves this or a source which have good >> literature >> >> > on >> >> > the problem, >> >> > please let me know. >> >> >> >> What is the literature that you plan to use to get the algorithm in >> >> the first place? >> >> >> >> Aaron Meurer >> >> >> >> > >> >> > Also I have to solve the quadratic congruence x**2 = D (mod m) as a >> sub >> >> > problem to implement the algorithm I found. I found a few algorithms >> on >> >> > this >> >> > but >> >> > none of them explain precisely how to solve the general equation, all >> >> > they >> >> > do is >> >> > solve the equation for m prime and gcd(D, m) = 1 and just ask to use >> >> > Chinese >> >> > remainder theorem to combine the results to solve for the general >> case >> >> > where >> >> > m >> >> > is not prime and gcd(D, m) not necessarily equal to 1. Any help on >> this >> >> > would >> >> > be highly appreciated. >> >> > >> >> > 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. >> > >> > >> >> -- >> 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.
descent.py
Description: Binary data
