Hi, I am cross posting this to the MPIR list, since this code may end up in MPIR and is directly relevant there. If people commenting on this thread could remember to include mpir-devel as well, that would be greatly appreciated.
Bill. On 11 April 2013 14:52, Bill Hart <[email protected]> wrote: > Hi Ritisha, > > Welcome. > > The eventual desire of the rational reconstruction project is to implement > the algorithm of Monaghan [1]. > > This is a modification of an algorithm due to Wang. Note that the > description of what rational reconstruction actually is, starts on page 1 > of that paper, starting level with the section title "Introduction", but in > the second column of the page. > > What we'd ultimately like to do is to implement this algorithm using > GMP/MPIR's mpn level functions (see [2]). These functions are very high > speed assembly optimised functions for dealing with multiprecision unsigned > integers. > > Obviously it makes sense to start with something less complex though. And > to that end the project calls for implementation of the Collins and > Encarnacion method [3], which is based on Lehmer's GCD. This is a sensible > first step because Lehmer's GCD is relatively easy to understand and > implement (there is an efficient implementation of it in GMP/MPIR) and > because this version with quadratic complexity will still be faster over > some basecase range. > > Unless you are extremely efficient at writing C code using mpn arithmetic > and have experience of this sort of thing, I would limit the project to > Collins and Encarnacion and leave the Monaghan algorithm altogether. The > former is plenty hard enough. > > I doubt there is any point providing an efficient implementation of Wang's > algorithm. But you could possibly try this as a prelude to the project to > get warmed up. However, it is especially important to realise that we don't > think Wang's algorithm will be competitive compared to Collins and > Encarnacion in the final analysis and so one shouldn't put much time into > that. > > It's possible the code may end up in either flint or MPIR, but initially > it would be placed in flint and tested thoroughly before being moved into > MPIR. Perhaps if you are prepared to sign the right paperwork and some > modest porting (the mpn interface is very slightly different in GMP), you > could also eventually consider submitting it to the GMP project. But you > would need to discuss that directly with them, not us. > > [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.7419 > [2] http://mpir.org/ > [3] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1287 > > > On 11 April 2013 12:02, Ritisha Laungani <[email protected]>wrote: > >> Hello, >> >> I am Ritisha Laungani, a final year Information Systems student at BITS >> Pilani Goa Campus, India. >> >> Last year, I successfully completed the GSoC 2012 program working on a >> Java project with Cytoscape, NRNB ( >> http://apps.cytoscape.org/apps/pathexplorer ). I have been working in C >> for the past 4 years using various libraries like the POSIX, OpenGL and >> Socket Programming. I've always had a deep interest in Mathematics but >> unfortunately, over the past 2 years of my engineering studies, i have only >> been involved with the algorithmic and graph theory part of it and have >> lost touch with algebra a bit. However, i am sure i'll be able to catch up >> as i start working towards the project *Fast Reconstruction of Rationals. >> * >> >> Quite a few papers have been mentioned in the project description, i >> would want to know a start point as to where i can start looking at codes >> or reference material, which can help me draft a relevant proposal for the >> project. >> >> Do let me know. >> >> Regards, >> >> Ritisha. >> >> -- >> >> --- >> You received this message because you are subscribed to the Google Groups >> "flint-devel" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- You received this message because you are subscribed to the Google Groups "mpir-devel" 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/mpir-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
