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.
