Re: [GSoC 2013] Interested in project "Fast Reconstruction Of Rationals"

[Bill Hart]

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 <goodwi...@googlemail.com> 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 <ritisha...@gmail.com> 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 flint-devel...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Bill Hart]

Cross posting additional information provided by Martin Lee to mpir-devel.

Bill.

On 11 April 2013 17:14, marti...@web.de <marti...@web.de> wrote:

Hi Ritisha

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. 

For a general description of rational reconstruction you can take a look at Modern Computer Algebra (Chapter 5.10). In the same book there is a Chapter on Fast Euclidean Algorithm (Chapter 11.1) which will help you understand the basics of Fast GCD. Implementation wise you can take a look at a function in NTL called _ntl_gxxratrecon in g_lip_impl.h which implements the Collins & Encarnacion algorithm.
Cheers
Martin