Re: [flint-devel] Function Interface Updates

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

--- D.C...@wa... wrote:

> The method for approximating real square roots works
> for p-adics as well;
> that is, if x is an approximation to sqrt(S), then
> 1/2(x + S/x) is a
> better approximation. We would get a list of
> rationals and the final step
> would be to convert the rational a/b into its p-adic
> expansion.
> 

I'm not completely convinced it is right to work in Q
then convert at the end. Won't the numerator and
denominator get really huge doing this?

Why can't one implement this as an algorithm with
power series (where our power series are still
represented as large integers)?

This is actually an important detail, and perhaps you
can convince me one way or another.

By the way, how many additional terms of the p-adic
series do you get each time with this algorithm?

> 
> You may also like to take a look at this division
> algorithm I found a
> little while ago;
> 
>
http://en.wikipedia.org/wiki/P-adic_division_algorithm
> 

That seems interesting. How is division normally
performed?

> I haven't found this algorithm used any where else,
> but it does seem to
> work and may speed up the process of finding the
> p-adic expansion of a/b
> after performing a division as it offers an
> alternative method to compute
> 1/b. I can include this in my write up, but I don't
> think it would benefit
> us in terms of speed. I also don't know how easy it
> would be to implement
> into FLINT.
> 
> (Its probably worth noting that I don't think either
> of these options
> would be available to us had we opted for a power
> series implementation.)
> 
> 
> The version of Hensels Lemma I've been reading
> actually places the
> restriction on the polynomial that the coefficients
> must be p-adic
> integers. From this restriction, the nth root must
> lie in Z_p according to
> the proof. So its probably not worth using this
> method for finding nth
> roots.
>

I see. So how does one find roots of polynomials in Qp
then? That's an important question we have to figure
out.

> 
> With regards to the Bristol conference,
> unfortunately I'll be home by
> then. Depending on the time you'll be leaving
> Coventry train station, I
> could look at getting an early train from home and
> meeting you at Bristol,
> but my hometown is ~200 miles north of Coventry so
> this probably won't be
> possible unfortunately.
> 
> 
> 
> Daniel Ellam
> 
> 
> 
> > I don't know if this looks efficient or not. Isn't
> there a method
> > which gives you more than one coefficient at a
> time.
> >
> > Also, this looks completely generic in that if I
> had an algorithm for
> > finding a root of an arbitrary polynomial, I could
> just feed it x^n-a
> > and it would essentially do exactly as you
> described, and not be any
> > slower.
> >
> > So perhaps there is no need to have it implemented
> separately for this
> > reason.
> >
> > I'm also unsure that you can expect the solution
> to always exist in
> > Zp. Isn't it sometimes in Qp?
> >
> > Bill.
> >
> > 2008/8/8  <D.C...@wa...>:
> >> Hi,
> >>
> >> My plan for finding nth roots was to consider
> p-adic nth roots as roots
> >> of
> >> a polynomial of the form f(x) = x^n - a and then
> basically applying
> >> Hensel's Lemma. So if S is a root of x^n - a and
> S = s0 + s1p + s2p^2 +
> >> ... then if we have already calculated s0,
> s1,...,s(n-1) and want to
> >> calculate sn, we write sn = s(n-1) + (bn)*p^n
> where
> >>
> >> (bn)*p^n = - f(b(n-1))/f'(b(n-1)) mod p^(n+1).
> >>
> >> Of course we will have to find the formal
> derivative of f, but in this
> >> specific case this is always easy. This method is
> quite easy to do by
> >> hand
> >> and should be easy to implement; I didn't find
> anything better during my
> >> research, do you think this method is worth
> pursuing?
> >>
> >>
> >>
> >>
> >> Daniel Ellam
> >>
> >>
> >>
> >>>Perhaps n-th roots can be thought of as roots of
> a polynomial, i.e.
> >>> roots
> >> of >x^n-1. So maybe we don't even need that
> separately. It would be
> >> worth
> >> it if >there is an algorithm out there which is
> definitely faster than
> >> something generic.
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >>
>
-------------------------------------------------------------------------
> >> This SF.Net email is sponsored by the Moblin Your
> Move Developer's
> >> challenge
> >> Build the coolest Linux based applications with
> Moblin SDK & win great
> >> prizes
> >> Grand prize is a trip for two to an Open Source
> event anywhere in the
> >> world
> >>
>
http://moblin-contest.org/redirect.php?banner_id=100&url=/
> >> _______________________________________________
> >> flint-devel mailing list
> >> fli...@li...
> >>
>
https://lists.sourceforge.net/lists/listinfo/flint-devel
> >>
> >
> >
>
-------------------------------------------------------------------------
> > This SF.Net email is sponsored by the Moblin Your
> Move Developer's
> > challenge
> > Build the coolest Linux based applications with
> Moblin SDK & win great
> > prizes
> > Grand prize is a trip for two to an Open Source
> event anywhere in the
> > world
> >
>
http://moblin-contest.org/redirect.php?banner_id=100&url=/
> > _______________________________________________
> > flint-devel mailing list
> > fli...@li...
> >
>
https://lists.sourceforge.net/lists/listinfo/flint-devel
> >
> 
> 
>
-------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your
> Move Developer's challenge
> Build the coolest Linux based applications with
> Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source
> event anywhere in the world
>
http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
>
https://lists.sourceforge.net/lists/listinfo/flint-devel
> 