50 lines
2.1 KiB
Plaintext
50 lines
2.1 KiB
Plaintext
;Conversion and addition of [[wp:P-adic_number|p-adic Numbers]].
|
|
|
|
|
|
;Task.
|
|
|
|
Convert two rationals to p-adic numbers and add them up.
|
|
Rational reconstruction is needed to interpret the result.
|
|
|
|
p-Adic numbers were introduced around 1900 by Hensel. p-Adic expansions
|
|
(a series of digits 0 ≤ d < p times p-power weights)
|
|
are finite-tailed and tend to zero in the direction of higher positive
|
|
powers of p (to the left in the notation used here).
|
|
For example, the number 4 (100.0) has ''smaller'' 2-adic norm than 1/4 (0.01).
|
|
|
|
If we convert a natural number, the familiar p-ary expansion is obtained:
|
|
10 decimal is 1010 both binary and 2-adic. To convert a rational number a/b
|
|
we perform p-adic long division. If p is actually prime, this is always possible
|
|
if first the 'p-part' is removed from b (and the p-adic point shifted accordingly).
|
|
The inverse of b modulo p is then used in the conversion.
|
|
|
|
'''Recipe:''' at each step the most significant digit of the partial remainder
|
|
(initially a) is zeroed by subtracting a proper multiple of the divisor b.
|
|
Shift out the zero digit (divide by p) and repeat until the remainder is zero
|
|
or the precision limit is reached. Because p-adic division starts from the right,
|
|
the 'proper multiplier' is simply
|
|
d = partial remainder * 1/b (mod p).
|
|
The d's are the successive p-adic digits to find.
|
|
|
|
Addition proceeds as usual, with carry from the right to the leftmost term,
|
|
where it has least magnitude and just drops off. We can work with approximate rationals
|
|
and obtain exact results. The routine for rational reconstruction demonstrates this:
|
|
repeatedly add a p-adic to itself (keeping count to determine the denominator),
|
|
until an integer is reached (the numerator then equals the weighted digit sum).
|
|
But even p-adic arithmetic fails if the precision is too low. The examples mostly
|
|
set the shortest prime-exponent combinations that allow valid reconstruction.
|
|
|
|
|
|
;Related task.
|
|
|
|
[[p-Adic square roots]]
|
|
|
|
|
|
;Reference.
|
|
|
|
[https://www.cut-the-knot.org/blue/p-adicExpansion.shtml] p-Adic expansions
|
|
|
|
|
|
__TOC__
|
|
|