Hi Ondrej, I am planning to improve the algorithms used in solving binary quadratic equation. (Pernici pointed out some efficient algorithms). Should I commit these changes in a new branch or can I use the current one I used to implement ternary quadratics?
Regards, Thilina On Sat, Jul 27, 2013 at 5:26 PM, Thilina Rathnayake <[email protected]>wrote: > Hi Ondrej, > > Sorry for taking a lot of time to send you updates on the project. I had a > little busy > time since our university is having a drama festival and I had to > practice a drama for > it. It ends on upcoming Monday, so I will be as free as before after > Monday. > > I had to find a source for an algorithm on 2-dimensional lattice reduction. > It took a lot of time to find one and I implemented it. So now, the > descent method > is improved by using gaussian reduction. I renamed the previous `descent()` > method as `ldescent()` (Lagrange's descent). I couldn't compare the > performance > improvement, but I'll do it very soon.And also this algorithm has been > implemented > previously, not like the one in Smart's book. > > Also, Pernici did a wonderful job and implemented a fast method to solve > the > quadratic congruence. Here is the pull request. > > https://github.com/sympy/sympy/pull/2307 > > I can use this in my module when this get merged into the main repo. > So the time taken for finding solutions will be hugely reduced. > > I also implemented the Holzer's reduction to simplify the solutions. But > it contains bugs. > I will fix it as soon as possible. When I managed to get that done, the > work with ternary > quadratic forms will be finished. > > Major TODO's in the Diophantine module > ============================== > > [1] Pernici has pointed out a fast method for solving a sub-case of binary > quadratic > forms. I hope to do it in the future. > > [2] Fix the Holzer reduction algorithm which is to be used in ternary > quadratic forms. > > [3] Complete the other two deliverables. > > I made a commit with the changes I made this week. Please take a look at > this when you > have some free time. I couldn't do a lot of work this week due to my busy > schedule. I am > extremely sorry for that. > > Regards, > Thilina. > > > > On Wed, Jul 24, 2013 at 1:10 AM, Thilina Rathnayake < > [email protected]> wrote: > >> Thanks mario for the great job. >> Let me try your code. >> >> Regards, >> Thilina >> >> >> On Wed, Jul 24, 2013 at 12:47 AM, Ondřej Čertík >> <[email protected]>wrote: >> >>> Thanks. Should we integrate it into sympy? >>> >>> Ondrej >>> >>> On Tue, Jul 23, 2013 at 1:34 AM, mario <[email protected]> wrote: >>> > In the attached file there is a new version of ``descent``; I followed >>> your >>> > suggestion about >>> > reducing the input to the square free part; in this way the lowest >>> modular >>> > square root is >>> > always used; there is no need to use others; so the code in Smart >>> seems to >>> > be correct, >>> > provided the input is reduced to the square free part. >>> > It is used the fast ``sqrt_mod`` in >>> https://github.com/sympy/sympy/pull/2307 >>> > >>> > >>> > On Saturday, July 20, 2013 7:40:05 PM UTC+2, Thilina Rathnayake wrote: >>> >> >>> >> Thanks Ondrej for putting the link of the PR. I am sorry I forgot to >>> put >>> >> it. >>> >> >>> >> I am really grateful If other's can play with this and give feedback >>> on >>> >> how this can be improved, >>> >> especially reports any bugs in the programme. >>> >> >>> >> Thanks in advance. >>> >> >>> >> >>> >> >>> >> On Sat, Jul 20, 2013 at 11:00 PM, Ondřej Čertík <[email protected]> >>> >> wrote: >>> >>> >>> >>> On Sat, Jul 20, 2013 at 11:25 AM, Thilina Rathnayake >>> >>> <[email protected]> wrote: >>> >>> > Hi Ondrej, >>> >>> > >>> >>> > I am pleased to say that I managed to implement the solutions for >>> >>> > quadratic >>> >>> > ternary forms. >>> >>> > Only thing we have to verify is that whether they are complete. I >>> found >>> >>> > one >>> >>> > incident in the >>> >>> > current implementation where it returned a partial solution. I >>> added it >>> >>> > as a >>> >>> > different test. I plan >>> >>> > to implement the algorithm Implemented in MAGMA in the upcoming >>> days, >>> >>> > and >>> >>> > also it seems like >>> >>> > MAGMA's algorithm is faster. So we can make it the main algorithm >>> used >>> >>> > by >>> >>> > `diop_solve()`. >>> >>> > >>> >>> > There is one major factor affecting the speed of the algorithm, the >>> >>> > overhead >>> >>> > of the function >>> >>> > `quadratic_congruence()` which solves a quadratic congruence. This >>> >>> > function >>> >>> > was also used in solving >>> >>> > binary quadratic forms also. I found a link to a reference >>> material on >>> >>> > the >>> >>> > problem. >>> >>> > >>> >>> > Also the parametric solution returned by the solver would be more >>> >>> > elegant if >>> >>> > we could reduce the >>> >>> > basic solution we found using the `descent()` by the Hozler's >>> reduction >>> >>> > algorithm. >>> >>> > >>> >>> > These are the area's I am going to focus in the future. >>> >>> >>> >>> Very cool, I agree. Thanks for the work, you have done excellent >>> >>> progress. >>> >>> I'll try to play with your branch in the next few days. >>> >>> >>> >>> > >>> >>> > (PS - You have already commented in the pull request. Thank you for >>> >>> > that. >>> >>> > I'll get to it as soon as >>> >>> > I finish writing this week's blog post) >>> >>> >>> >>> Here is the PR if others would like to comment: >>> >>> >>> >>> https://github.com/sympy/sympy/pull/2303 >>> >>> >>> >>> Ondrej >>> >>> >>> >>> -- >>> >>> 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.
