Re: [flint-devel] Function Interface Updates

[<D.C...@wa...>]

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.


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

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.


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
>