P-adic division algorithm
From Wikipedia, the free encyclopedia
- The correct title of this article is p-adic division algorithm. The initial letter is shown capitalized due to technical restrictions.
The p-adic division algorithm is a simple algorithm for dividing p-adic numbers in mathematics. Most algorithms proceed one p-adic digit at a time, but this algorithm improves the number of correct digits in the quotient by a factor of c during each calculation. Furthermore, it is very easy to define.
[edit] Description of the algorithm
To compute the inverse of a, first choose a number c > 1, and an initial guess x0, which must be chosen to have at least 1 correct p-adic digit, that is x0 a ≡ 1 (mod p). Then, apply the iteration
The result is a polynomial in xk and a after c has been chosen.
One can also convert nth root algorithms from real numbers to p-adic numbers.
[edit] Example
To calculate 1/11 in Q7 with c = 3, we start with x0 = 2. The first three iterates are
This tells us that 727 divides (45554184106538309239332600382503722×11 − 1).
