P-Adic numbers, basic: Difference between revisions

Content added Content deleted
(Added Wren)
(changed the intro and a few examples.)
Line 17: Line 17:
If we convert a natural number, the familiar p-ary expansion is obtained:
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
10 decimal is 1010 both binary and 2-adic. To convert a rational number a/b
we perform long division modulo powers of p. If p is actually prime,
we perform p-adic long division. If p is actually prime, this is always possible
this is always possible if first the 'p-part' is removed from b
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.
(and the p-adic point moved to the left 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
'''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.
(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
Shift out the zero digit (divide by p) and repeat until the remainder is zero
or the precision limit is reached. Note that the 'proper multiplier' is always
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).
d = partial remainder * 1/b (mod p).
The d's are the successive p-adic digits to find.
The d's are the successive p-adic digits to find.


p-Adic addition proceeds as usual, with carry from the right to the leftmost term,
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
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:
and obtain exact results. The routine for rational reconstruction demonstrates this:
Line 315: Line 315:
cls
cls


'rational reconstruction limits
'rational reconstruction
'are relative to the precision:
'depends on the precision -
'until the dsum-loop overflows.
data 2,1, 2,4
data 2,1, 2,4
data 1,1
data 1,1
Line 329: Line 330:
data 4,9, 5,4
data 4,9, 5,4
data 8,9
data 8,9

data -7,5, 7,4
data 99,70


data 26,25, 5,4
data 26,25, 5,4
Line 345: Line 343:
data -101,384
data -101,384


'three 'decadic' pairs
'two 'decadic' pairs
data 6,7, 10,7
data -5,7

data 2,7, 10,7
data 2,7, 10,7
data -3,7
data -1,7


data 34,21, 10,9
data 34,21, 10,9
Line 359: Line 354:
data 679001,207
data 679001,207


data 11,4, 3,27
data -8,9, 23,9
data 679001,207
data 302113,92

data 11,4, 11,13
data 679001,207

data -22,7, 2,37
data 46071,379


data -22,7, 3,23
data -22,7, 3,23
data 46071,379
data 46071,379


data -22,7, 7,13
data -22,7, 32749,3
data 46071,379
data 46071,379


data -101,109, 2,40
data 35,61, 5,20
data 583376,6649
data 9400,109


data -101,109, 61,7
data -101,109, 61,7
data 583376,6649
data 583376,6649


data -101,109, 32749,3
data -25,26, 7,13
data 583376,6649
data 5571,137

data 1,4, 7,11
data 9263,2837

data 122,407, 7,11
data -517,1477

'more subtle
data 5,8, 7,11
data 353,30809


data 0,0, 0,0
data 0,0, 0,0
Line 447: Line 446:
3 1 3 3
3 1 3 3
4/3
4/3


-7/5 + O(7^4)
2 5 4 0
99/70 + O(7^4)
0 5 0. 5
+ =
6 2 0. 5
1/70




Line 494: Line 484:




6/7 + O(10^7)
2/7 + O(10^7)
7 1 4 2 8 5 8
5 7 1 4 2 8 6
-5/7 + O(10^7)
-1/7 + O(10^7)
5 7 1 4 2 8 5
7 1 4 2 8 5 7
+ =
+ =
2 8 5 7 1 4 3
2 8 5 7 1 4 3
1/7
1/7


2/7 + O(10^7)
5 7 1 4 2 8 6
-3/7 + O(10^7)
1 4 2 8 5 7 1
+ =
7 1 4 2 8 5 7
-1/7




Line 530: Line 511:




11/4 + O(3^27)
-8/9 + O(23^9)
2 12 17 20 10 5 2 12 17
2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 1 2
679001/207 + O(3^27)
302113/92 + O(23^9)
5 17 5 17 6 0 10 12. 2
1 1 0 2 2 0 1 2 2 1 2 1 1 0 2 2 1 0 1 1 0 0 2 2 2. 0 1
+ =
+ =
18 12 3 4 11 3 0 6. 2
0 2 0 0 1 1 1 0 1 2 1 2 0 1 2 0 0 1 0 1 2 1 2 1 1. 0 1
2718281/828
2718281/828


11/4 + O(11^13)
8 2 8 2 8 2 8 2 8 2 8 3 0
679001/207 + O(11^13)
8 7 9 5 6 10 6 3 6 4 2 10 9
+ =
5 10 6 8 4 2 3 6 3 7 0 2 9
2718281/828


-22/7 + O(2^37)
1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0
46071/379 + O(2^37)
1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1
+ =
1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 1 1
314159/2653




Line 566: Line 529:




-22/7 + O(7^13)
-22/7 + O(32749^3)
28070 18713 23389
6 6 6 6 6 6 6 6 6 6 6 3. 6
46071/379 + O(7^13)
46071/379 + O(32749^3)
4493 8727 10145
6 4 1 6 6 5 1 2 2 1 3 2 4
+ =
+ =
32563 27441 785
4 1 6 6 5 1 2 2 1 3 2 0. 6
314159/2653
314159/2653




-101/109 + O(2^40)
35/61 + O(5^20)
0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1
2 3 2 3 0 2 4 1 3 3 0 0 4 0 2 2 1 2 2 0
583376/6649 + O(2^40)
9400/109 + O(5^20)
1 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0
3 1 4 4 1 2 3 4 4 3 4 1 1 3 1 1 2 4 0 0
+ =
+ =
0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 1 1 1
1 0 2 2 2 0 3 1 3 1 4 2 0 3 3 3 4 1 2 0
577215/6649
577215/6649


Line 593: Line 556:




-101/109 + O(32749^3)
-25/26 + O(7^13)
2 6 5 0 5 4 4 0 1 6 1 2 2
5107 21031 15322
583376/6649 + O(32749^3)
5571/137 + O(7^13)
3 2 4 1 4 5 4 2 2 5 5 3 5
5452 13766 16445
+ =
+ =
6 2 2 2 3 3 1 2 4 4 6 6 0
10560 2048 31767
141421/3562
577215/6649


1/4 + O(7^11)
1 5 1 5 1 5 1 5 1 5 2
9263/2837 + O(7^11)
6 5 6 6 0 3 2 0 4 4 1
+ =
1 4 1 4 2 1 3 5 6 2 3
39889/11348


122/407 + O(7^11)
6 2 0 3 0 6 2 4 4 4 3
-517/1477 + O(7^11)
1 2 3 4 3 5 4 6 4 1. 1
+ =
3 2 6 5 3 1 2 4 1 4. 1
-27584/90671


5/8 + O(7^11)
4 2 4 2 4 2 4 2 4 2 5
353/30809 + O(7^11)
2 3 6 6 3 6 4 3 4 5 5
+ =
6 6 4 2 1 2 1 6 2 1 3
47099/10977


</pre>
</pre>
Retrieved from "https://rosettacode.org/wiki/P-Adic_numbers,_basic"