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.
