Re: Reg: Fast Reconstruction of Rationals.

[Bill Hart]

I can imagine there being a kind of p-adic algorithm for this. Could this be what Burcin is referring to? I am not aware of references for such an algorithm though. Perhaps individuals on either list have more information about this.

Bill.

On 16 April 2013 15:23, Fredrik Johansson <fredrik....@gmail.com> wrote:

On Tue, Apr 16, 2013 at 3:51 PM, Burcin Erocal <bur...@erocal.org> wrote:

Hi,

On Tue, 16 Apr 2013 14:09:09 +0100
Bill Hart <goodwi...@googlemail.com> wrote:

> I believe Martin Lee is mentor for this project. He will be able to
> answer any questions about what is required (if they aren't already
> answered in that thread). I will be helping with the integration of
> any resulting code into flint.

Martin didn't think he would have time to mentor a project this summer,
so the project page lists me and Fredrik as potential mentors. We
should look for other mentors who can commit more time to this project,
since it seems that I am volunteering to mentor too many this summer. :)

Would anybody, perhaps more with MPIR background, be interested to
mentor this?

Hi Burcin,

To clarify, I might be relatively busy this summer, so it'd be great if you and Bill could be the primary mentor candidates. But I will absolutely be available for mentoring FLINT related projects if either of you doesn't have time.

> On 16 April 2013 08:01, Saket Bharambe <saketbhar...@gmail.com>
> wrote:
> >

> > I am Saket Bharambe, a final year Computer Science student at
> > IIIT-Hyderabad, India. I love to code and take part in many
> > programming competitions. I have been using C/C++ since for the
> > last 5yrs and use it extensively in the programming competitions
> > too. I am also fond of Mathematics and in particular, Number
> > Theory. I have solved 100+ problems on projecteuler [1].

Can you provide more information on your programming background?
Examples of projects you have worked on for instance.

> > I am interested in the project "Fast Reconstruction of Rationals".
> > As first step, I read the paper [2] describing Collins and
> > Encarnacion's algorithm. Please guide me in this project and tell
> > me what my next steps should be.

It seems that flint already has rational reconstruction from fpmz, but
not from finite field elements. (Flint devs, please correct me if I'm
wrong.)

Yes, it does have rational reconstruction from fmpz. The problems with this code is just that it is 1) slow compared to an mpn implementation of a slightly more clever algorithm, 2) not asymptotically fast.

I'm not sure what you mean by rational reconstruction from finite field elements. You can reconstruct a rational number from a list of residues modulo word-size primes in two stages, first calling the fast CRT code to reconstruct an integer, and then calling rational reconstruction to construct a rational.

The other thing that would be very useful to have is of course rational function reconstruction.

Fredrik

--
 
---
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.
 
 

[Burcin Erocal]

On Tue, 16 Apr 2013 15:26:53 +0100
Bill Hart <goodwi...@googlemail.com> wrote:

> I can imagine there being a kind of p-adic algorithm for this. Could
> this be what Burcin is referring to? I am not aware of references for
> such an algorithm though. Perhaps individuals on either list have
> more information about this.

I meant simply changing the existing code so that it works with ulong
extras or the representation used by nmod_vec. (Is there a separate
nmod struct?) This just needs to be an exercise to demonstrate basic
coding and git skills. :)

Rational function reconstruction would definitely be more interesting,
but does flint have a data structure for F_p(x) or Q(x)? Passing around
two nmod_poly's or fmpz_poly's is also OK of course.


BTW, if there is time left in this project, vector rational
reconstruction would be great to have as well:

https://cs.uwaterloo.ca/~astorjoh/issac11ratrecon.pdf

Cheers,
Burcin

[Fredrik Johansson]

On Tue, Apr 16, 2013 at 4:51 PM, Burcin Erocal <bur...@erocal.org> wrote:

On Tue, 16 Apr 2013 15:26:53 +0100
Bill Hart <goodwi...@googlemail.com> wrote:

> I can imagine there being a kind of p-adic algorithm for this. Could
> this be what Burcin is referring to? I am not aware of references for
> such an algorithm though. Perhaps individuals on either list have
> more information about this.

I meant simply changing the existing code so that it works with ulong
extras or the representation used by nmod_vec. (Is there a separate
nmod struct?) This just needs to be an exercise to demonstrate basic
coding and git skills. :)

Rational function reconstruction would definitely be more interesting,
but does flint have a data structure for F_p(x) or Q(x)? Passing around
two nmod_poly's or fmpz_poly's is also OK of course.

It does have a data structure for Q(x) (fmpz_poly_q). But the right way to implement this function would arguably be as an fmpz_poly function, with the fmpz_poly_q version being a thin wrapper. That's a minor detail though...

BTW, if there is time left in this project, vector rational
reconstruction would be great to have as well:

https://cs.uwaterloo.ca/~astorjoh/issac11ratrecon.pdf

It is clear that there are a million things that would be useful :-)

Of course a GSoC project could only cover perhaps 1-3 of them.

Fredrik