Re: [flint-devel] Function Interface Updates

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

I give an outline of p-adic division. I've used some functions from long
extras.



--------------------------------------------------------------------------------------
Functions

(1) unsigned long z_powmod(unsigned long b, long exp, unsigned long n).

(2) unsigned long z_gcd(long a, long b)

(3) unsigned long z_pow(unsigned long a, unsigned long exp)

(4) unsigned long mulmod2_precomp(unsigned long a, unsigned long b,
unsigned long n, pre_inv2_t ninv)

(5) A function for converting Q -> Q_p. Something like num_to_padic_conv.
To compute the coefficients, repetedly use (1) to solve congruences modulo
p^k for a and (1/b) and then a*(1/b). Store the elements in an array as
they are computed and output something like 1 . 1 0 1 to represent the
p-adic P^-1 + 1 + p^2.

(6) A function to convert Q_p -> Q. Again something like
padic_to_num_conv. We want to take an array of coefficients like 1 0 2 . 0
1 1 representing p^-3 + 2*p^-1 + p + p^2 and convert it to (a,b). I think
in this case we should set a = 1 + 2*p^2 + p^4 + p^5 and b = p^3. More
generally, consider the non-negative coefficient with the largest negative
exponent of p, say -m and set b = pow(p,m) by using (3) and once we've
essentially taken p^-m out as a factor we can sum the terms to find a.

(7) unsigned long z_div2_precomp(unsigned long a, unsigned long n,
pre_inv2_t ninv)

(8) A function to find the number of times p divides b. Can we use
unsigned long
z_powmod(unsigned long b, long exp, unsigned long n) for this?

(9) Function for reducing precision. This will be needed if we have two
p-adics of different precision. Something like padic_prec_redu. Simply
taking the p-adic modp^k for some suitable k should do.

(10) A function to "shift" the p-adic, so for example adding or taking out
a factor of p from the p-adic.

--------------------------------------------------------------------------------------


* Use (6) if necessary to convert a p-adic into an element of Q. So I can
assume the p-adic is inputted in the form a/b together with a prime p and
a precision n, say something like padic_num_t (a,b). Since we are likely
going to need modulo arithmetic, we probably want to be working with the
long extras module as opposed to fmpz when we deal with the two intgers a
and b representing numerator and denominator. This also allows us to use 
unsigned long z_invert in a function for converting our result a/b back to
a p-adic. I do realise that this limits us to unsigned longs.


p-adic division.  We need a precision, prime and the input which will be
of the form (a,b) representing a/b.

* Assume we are given p-adics (a,b) and (c,d) with precision n and prime
p. a may be signed, but we can assume b isnt signed.

* The long extras module can deal with gcd, so given ints a and b, first
find gcd(a,b) = D. Use (2) for this.
        -> Set a = a/D, b = b/D (6).
        -> Use (8) to find the p-adic valuation of a and b. If v_p(b) = N
>1 where v_p denotes the p-adic valuation of b, then we know that
a/b lies in Q_p, so letting b' = b/pow(p,N)  by using (3) to find
pow(p, N) and (6) for the division. Similarly we want to take
powers of p out of a (if any exist after the previous step) to
avoid impossible divisions modulo p^k later. Let v_p(a) = M. By
the last step, only one of M or N can be greater than 0. Let the
resulting number be a'. We want to store a', b', M-N, p and n,
then a'/b' lies in Z_p and the arithmetic in Q_p can be reduced to
arithmetic in Z_p. Note that we are basically rewriting the p-adic
a/b as p^(M-N)a'/b' and we shall perform the arithmetic on a'/b'.
        -> Then we want something like padic_num_init (a', b', M-N, p, n).

* Repeat the same process for (c, d).

* The p-adic arithmetic is performed on the integers a', b', c', d' (where
d' = d/pow(p,v_p(d) and similarly for c'.)

        -> We want to find (a'/b')/(c'/d') = (a'*d')/(b'*c'). We don't
want to reduce a'*d' and b'*c' modp^n after each step in say a while loop,
it will be quicker to do one reduction mod p^n at the end rather than a
reduction at each step. The end reduction (or if no loop is being used)
can use (4) where we take the multiplications a'*d' and b'*c' modulo p^n.
This will make converting a'*d'/b'*c' to its p-adic expansion quicker. We
also cancel the powers of p we took out of a/b and c/d at this point. This
requires an addition.

The final step is converting (a'*d',b'*c') back into its p-adic expansion.
We want to put the powers of p we took out of a, b, c and d (after
cancellation has taken place; we have a/b = p^(M-N)a'/b' and something
similar for c/d and when we perform the division we want to cancel the
powers of p appropriately) back in at the last step, i.e. "shift" the
resulting p-adic depending on what powers of p are left, (10). Use (5)
(although we will want modp^(n+(N-M)) since we took factors of powers of p
from a and b and so shifted the p-adic) and then perform a final shift as
just described.



Daniel Ellam




>