A Tutorial on p-adic Arithmetic

C
. K. Koc
Electrical & Computer Engineering
Oregon State University
Corvallis, Oregon 97331
Technical Report, April 2002

Abstract
The p-adic arithmetic allows error-free representation of fractions and error-free arithmetic
using fractions. In this tutorial, we describe infinite-precision p-adic arithmetic which is more
suitable for software implementations and finite-precision p-adic arithmetic which is more suitable for hardware implementations. The finite-precision p-adic representation is also called
Hensel code which has certain interesting properties and some open problems for research.

Introduction

A p-adic number can be uniquely written in the form

=

aj pj

j=n

where each of aj [0, p 1] and the p-adic norm of the number is defined as k k= pn . Note
that the series
1 + p + p2 + p3 +
converges to

1
1p

in the p-adic norm. Now, as an example, consider the power series expansion
= 2 + 3p + p2 + 3p3 + p4 + 3p5 + p6 +
= 2 + 3p(1 + p2 + p4 + ) + p2 (1 + p2 + p4 + )
= 2 + (3p + p2 )(1 + p2 + p4 + )

Since 1 + p2 + p4 + converges to (1 p2 )1 , we have

=2+

3p + p2
.
1 p2

Taking p = 5, we obtain 5-adic expansion of = 13 , which can be written in the form

1
3

= .23131313131
= .231

(p = 5) .
1

(p = 5)

There is a one-to-one correspondence between the power series expansion

an pn + an+1 pn+1 + an+2 pn+2 +
and the short representation an an+1 an+2 , where only the coefficients of the powers of p are
shown. We can use the p-adic point as a device for displaying the sign of n.
an an+1 a2 a1 .a0 a1 a2
.a0 a1 a2
.00 0a0 a1 a2

for n < 0
for n = 0
for n > 0

For example,
13.41 = 1 52 + 3 51 + 4 50 + 1 51
= 241/25
.1341 = 1 50 + 3 51 + 4 52 + 1 53
= 241
.01341 = 0 50 + 1 51 + 3 52 + 4 53 + 1 54 = 1205

Representation of Negative Numbers

If
=

ai pi

i=n

then

bi pi

i=n

where bn = p an and bi = (p 1) ai for i > n. Thus, for example,

1
3
1

= .2313131
= .3131313

However, watch for leading zeros, they remain unchanged:

5
3
5

= .02313131
= .03131313

Representation of Integers

Since a positive integer h can be expressed in exactly one way as the sum of powers of a prime p,
i.e.,
h = d0 + d1 p + d2 p2 + + dk pk
with di [0, p 1], there is essentially no difference between p-adic and p-ary representation of h.
The only difference is that the digits in the p-adic representation are written in reverse order. For
example,
199 = 4 50 + 4 51 + 2 52 + 1 53 = .4421 (5-adic)
199 = 1 53 + 2 52 + 4 51 + 4 50 = 1244. (5-ary)
2

Representation of Rational Numbers

If is a rational number, then it has a repeating pattern of aj s in its p-adic expansion, i.e., it is of
the form
= an an+1 a1 .b0 b1 bk c1 c2 cl
For example, 1/3 = .231, 1/3 = .31, and 2/3 = .413, etc. Let have the p-adic expansion
= an pn + an+1 pn+1 + an+2 pn+2 +
= pn (an + an+1 p + an+2 p2 + )
c1
= pn
d1
where gcd(c1 , d1 ) = 1 and p divides neither c1 nor d1 . The p-adic expansion for c1 /d1 is
c1
= an + an+1 p + an+2 p2 +
d1
and thus
c1 d1
1

(mod p) = an + an+1 p + an+2 p2 +

(mod p)

= an .
In other words, we compute an by
an = c1 d1
1

(mod p) .

Next, we use
c1
an = p(an+1 + an+2 p + an+3 p2 + )
d1
c2
,
= p
d2
where gcd(c2 , d2 ) = 1 and p divides neither c2 nor d2 . The p-adic expansion for c2 /d2 is
c2
= an+1 + an+2 p + an+3 p2 +
d2
and so
an+1 = c2 d1
2

(mod p) .

We continue this process until the period is exhibited. Let = 2/15 and p = 5. Thus,
2
2
= 51 ,
15
3
and n = 1. The 5-adic expansion of 2/15 is found as
a1 = 2 31 (mod 5) = 4
10
2
2
4 = =5
3
3
3
a0 = 2 31 (mod 5) = 1
3

2
1
3
a1
1
3
3
a2
2
1
3
a3

5
1
=5
3
3
1
1 3
(mod 5) = 3
10
2
=5
3
3
2 31 (mod 5) = 1
5
1
=5
3
3
1
1 3
(mod 5) = 3

=
=
=
=
=
=

which gives us 2/15 = 4.131313 = 4.13.

Addition

Addition of p-adic numbers is similar to the addition of p-ary numbers. However, we add the digits
and propagate the carries from left to right. As an example, we compute 2/3 + 5/6 = 3/2 for p = 5.
2
3
5
6

= .413131313
= .014040404

The addition operation proceeds as follows:

.413131313
.014040404
.422222222

=
=
=

.413
.0140
.42

As a check, we convert .42 to rational

.42 = 4 + 2(5 + 52 + 53 + )
= 4 + 10(1 + 5 + 52 + 53 + )
1
= 4 + 10
15
3
.
=
2

Subtraction

We complement the subtrahend and add it to the minuend, i.e., = + (). Let = 2/3
and = 5/6, then
5
6
5

= .014040404
= .040404040

Thus, we compute 2/3 5/6 = 1/6 as

4

.413131313
.040404040
.404040404

=
=
=

.413
.04
.40

Now, we convert .40 to rational using

.40 = 4(1 + 52 + 54 + 56 + )
1
= 4
1 25
1
= .
6

Multiplication

A p-adic number is called unit if it is not a multiple of a negative power of p and its first digit is
nonzero. For example, .413 and .42 are units while .0140 and 42.1231 are not. A non-unit p-adic
number can always be written in the form = pn where is a unit. For example,
.0140 = .140 51
and
42.1231 = .421231 52 .
Let = pn and = pm , then = pn+m . We can thus restrict multiplication of any two
p-adic numbers to multiplication of units. The multiplication can then be carried similar to the
case of p-ary numbers. To multiply 2/3 and 5/6, we get the Hensel codes
2
3
1
6

= .413131313
= .140404040

The multiplication operation is illustrated below:

.4131313131313
.1404040404040
4131313131313
123131313131
00000000000
1231313131
000000000
12313131
0000000
123131
00000
1231
000
12
0
.4201243201243
5

Thus, the result is 0.4201243 which is equal to

1
2 1
= .
3 6
9

Division

Again, we will only consider the division of p-adic units. Consider the following p-adic units:
= d0 + d1 p + d2 p2 +
= b0 + b1 p + b2 p 2 +
with d0 , b0 6= 0. The quotient = / can be written
d0 + d1 p + d2 p2 +
b0 + b1 p + b2 p 2 +
= a0 + a1 p + a2 p2 +

where a0 , a1 , a1 , . . . are the digits of . Since = , we have

= (b0 + b1 p + b2 p2 + )(a0 + a1 p + a2 p2 + )
= c0 + c1 p + c2 p2 +
Even though the p-adic digits ai and bi lie in the interval [0, p 1], we cannot assume that the
integers ci lie in this interval. Hence we write
c0 = b0 a0 = d0 + t1 p
where d0 [0, p 1]. Then d0 is the first digit in the p-adic expansion for and t1 is the carry
which must be added to c1 . Thus,
d0 = a0 b0 (mod p)
which implies
a0 = d0 b1
0

(mod p) .

This turns out to be the rule for obtaining each digit of the expansion for . At each stage of
the standard long division procedure, we multiply b1
(mod p) by the first digit of the partial
0
remainder and reduce the result modulo p.
As an example, we divide 2/3 by 1/12. We have
2
3
1
12

= .4131313
= .3424242

The first digit of the divisor is b0 = 3 and its multiplicative inverse modulo 5 is
b1
0

(mod p) = 31
= 2.

(mod 5)

The first digit of the partial remainder (which, in the first step, is the dividend) is d0 = 4, which
gives
a0 = b1
0 d0
= 24

(mod p)
(mod 5)

= 3.
Thus, we obtain the first digit of the quotient. We then update the partial remainder by subtracting
3 times the divisor from it.
.3
.4131313
.1111111
.0342424

.3424242
.4333333
To obtain the second digit, we multiply b1
0
and reduce the result modulo p.

(mod p) by the first digit of the partial remainder

a1 = 2 3

(mod 5)

= 1.
Thus, the second step of the division procedure gives us
.31
.0342424
.0202020
.0000000

.3424242
.0342424

This procedure produced the partial remainder which is zero, hence we terminate the expansion.
In general, this will not happen and we will have to continue until the period is exhibited. As a
check we observe that 2/3 1/12 = 8 and 8 = .31 for p = 5.
We note that the division of p-adic numbers is deterministic and not subject to trial and error
as is the case for division of p-ary numbers.

Finite-Segment p-adic Number System

In this finite number system each rational number in the set

SN = { =

a
: |a| [0, N ], and |b| [1, N ]}
b

is assigned a unique code representation called its Hensel code. Arithmetic operations on pairs of
rational numbers in SN can be replaced by corresponding arithmetic operations on their Hensel
codes.
A Hensel code for a rational number is simply a finite segment of its infinite-precision p-adic
expansion. We use the notation H(p, r, ) where p is a prime and r is the integer which specifies
the number of digits of the p-adic expansion which we retain for the Hensel code. For example,
since
2
= 0.4131313 ,
3
7

the Hensel code for = 2/3 when p = 5 and r = 4 is

H(5, 4, 2/3) = .4131 .
A Farey sequence of order N is the ascending sequence of all reduced fractions in [0, 1] whose
denominators are not greater than N . For example, if N = 5, we have the Farey sequence
F5 =

0 1 1 1 2 1 3 2 3 4 1
, , , , , , , , , , .
1 5 4 3 5 2 5 3 4 5 1

A simple rule for obtaining the Farey sequence of any order is illustrated below:
F1 :
F2 :
F3 :
F4 :
F5 :

0
1
0
1
0
1
0
1
0
1

1
5

1
4
1
4

1
3
1
3
1
3

1
2
1
2
1
2
1
2

2
5

2
3
2
3
2
3

3
5

3
4
3
4

4
5

1
1
1
1
1
1
1
1
1
1

where the nth row is constructed from the (n 1)st row by including the fraction a+b
c+d between any
a
b
two fractions c and d whenever c + d n. Note that the set SN is the set of all order N Farey
fractions.
Theorem 1 Let p be a prime and let r be a positive integer. Define N to be the largest positive
integer which satisfies the inequality
1
 r
p 1 2
N
2
then every order N Farey fraction can be represented uniquely by an r-digit ordered sequence (its
Hensel code), where each digit is an integer in the interval [0, p 1].
For example, for p = 5 and r = 4, the value of N is found by computing
N

54 1
2

!1
2

which gives N = 17. Thus, if a/b belongs to F17 , we have a unique Hensel code H(5, 4, a/b) for it.
We do not have compute infinite p-adic expansion of in order to obtain r-digit Hensel code
of . Suppose = ab where
a
c
= pn
b
d
with gcd(c, d) = gcd(c, p) = gcd(d, p) = 1. Let the Hensel code for c/d be
H(p, r, c/d) = .a0 a1 ar1
then ar1 ar2 a1 a0 is the radix p representation for the integer c d1
a0 + a1 p + a2 p2 + + ar1 pr1 = c d1
We consider the following three cases:

(mod pr ), i.e.,

(mod pr ) .

Case I n = 0
First we compute the integer c d1 (mod pr ) and then express this integer in radix p. The
Hensel code is then simply obtained by reversing the digits. For example, when = 2/3,
p = 5, and r = 4, we have pr = 54 = 625, and
2
2
= 50 ,
3
3
thus
2 31 = 2 417 = 209

(mod 625) .

Expressing the decimal 209 in radix 5, we obtain

209 = 1 53 + 3 52 + 1 51 + 4 50 = (1314)5 .
The Hensel code of 2/3 is found
H(5, 4, 2/3) = .4131
which agrees with the one found by truncating the infinite series expansion.
Case II n < 0
In this case = pm dc where m is a positive integer. To find H(p, r, ) we first find
H(p, r, c/d) using the procedure given in Case I and then shift the p-adic point m places to
the right. For example, let = 2/15 with p = 5 and r = 4. We write = 51 23 and compute
the Hensel code for 2/3 as .4131. The Hensel code for 2/15 is found by shifting the p-adic
point one place to the right to obtain
H(5, 4, 2/15) = 4.131
Case III n > 0
In this case = pk dc where k is a positive integer. To find H(p, r, ) we compute H(p, r, c/d)
and then shift the p-adic point k places to the left. For example, the Hensel code = 10/3 =
51 32 is found as
H(5, 4, 10/3) = .0413
Note that the rules for obtaining Hensel code for a negative number are the same. For example,
to obtain H(5, 4, 2/3) we compute 5-ary expansion of the integer 2 31 (mod 625) as
= 2 31

(mod 625)

= 2 417

(mod 625)

= 416
= (3131)5
which gives the Hensel code H(5, 4, 2/3) = .1313.

10

Arithmetic using Hensel Codes

The rules of the arithmetic are similar to the infinite-precision case. However, notice that whenever
the result is outside the set FN , uniqueness and correctness are no longer assured. The table given
below enumerates all Hensel codes of the form H(5, 4, a/b) where a/b F17 .
Table 1: Ordinary Hensel Codes H(5, 4, a/b)
a b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1
.1000
.2000
.3000
.4000
.0100
.1100
.2100
.3100
.4100
.0200
.1200
.2200
.3200
.4200
.0300
.1300
.2300

2
.3222
.1000
.4222
.2000
.0322
.3000
.1322
.4000
.2322
.0100
.3322
.1100
.4322
.2100
.0422
.3100
.1422

3
.2313
.4131
.1000
.3313
.0231
.2000
.4313
.1231
.3000
.0413
.2231
.4000
.1413
.3231
.0100
.2413
.4231

4
.4333
.3222
.2111
.1000
.0433
.4222
.3111
.2000
.1433
.0322
.4111
.3000
.2433
.1322
.0211
.4000
.3433

5
1.000
2.000
3.000
4.000
.1000
1.100
2.100
3.100
4.100
.2000
1.200
2.200
3.200
4.200
.3000
1.300
2.300

6
.1404
.2313
.3222
.4131
.0140
.1000
.2404
.3313
.4222
.0231
.1140
.2000
.3404
.4313
.0322
.1231
.2140

7
.3302
.1214
.4021
.2423
.0330
.3142
.1000
.4302
.2214
.0121
.3423
.1330
.4142
.2000
.0402
.3214
.1121

8
.2414
.4333
.1303
.3222
.0241
.2111
.4030
.1000
.3414
.0433
.2303
.4222
.1241
.3111
.0130
.2000
.4414

9
.4201
.3012
.2313
.1124
.0420
.4131
.3432
.2243
.1000
.0301
.4012
.3313
.2124
.1420
.0231
.4432
.3243

10
3.222
1.000
4.222
2.000
.3222
3.000
1.322
4.000
2.322
.1000
3.322
1.100
4.322
2.100
.4222
3.100
1.422

11
.1332
.2120
.3403
.4240
.0133
.1411
.2204
.3041
.4324
.0212
.1000
.2332
.3120
.4403
.0340
.1133
.2411

12
.3424
.1404
.4333
.2313
.0342
.3222
.1202
.4131
.2111
.0140
.3020
.1000
.4424
.2404
.0433
.3313
.1342

13
.2034
.4014
.1143
.3123
.0203
.2232
.4212
.1341
.3321
.0401
.2430
.4410
.1000
.3034
.0114
.2143
.4123

14
.4101
.3302
.2013
.1214
.0410
.4021
.3222
.2423
.1134
.0330
.4431
.3142
.2343
.1000
.0201
.4302
.3013

15
2.313
4.131
1.000
3.313
.2313
2.000
4.313
1.231
3.000
.4131
2.231
4.000
1.413
3.231
.1000
2.413
4.231

16
.1234
.2414
.3104
.4333
.0123
.1303
.2042
.3222
.4402
.0241
.1421
.2111
.3340
.4030
.0310
.1000
.2234

17
.3043
.1132
.4121
.2210
.0304
.3342
.1431
.4420
.2024
.0113
.3102
.1240
.4234
.2323
.0412
.3401
.1000

Using this table, we now illustrate some of the properties of the finite segment p-adic number
systems:
Let = 2/3 and = 3/4. The result is 2/3 + 3/4 = 17/12.
2
3
3
4

= .4131
= .2111
= .1342

which is found in the table, giving the correct result.

Let = 3/13 and = 1/12. The result is 3/13 + 1/12 = 49/156.
3
13
1
12

= .1143
= .3424
= .4023

which is not in the table.

Let = 5/2 and = 5/7. The result is 5/2 + 5/7 = 45/14.
5
2
5
7

= .0322
= .0330
= .0113

which is in the table, giving an incorrect result 10/17. Note that 10/17 = 0.588235 is far from
the correct result 45/14 = 3.21429 in the absolute norm. However, it is 5-adically close, i.e.,
their difference 10/17 45/14 = 625/238 is divisible by 54 .
10

Theorem 2 Let = a/b and = c/d, with gcd(b, p) = gcd(d, p) = 1. Then H(p, r, ) = H(p, r, )
if and only if
a b1 = c d1 (mod pr ) ,
or, in other words,
ad=cb

(mod pr ) .

Using the previous example = 10/17 and = 45/14, we see that

10 171 = 45 141

(mod 625) ,

i.e.,
10 14 = 45 17

11

(mod 625) .

Floating-Point Hensel Codes

Let = a/b = pn dc with gcd(c, d) = gcd(c, p) = gcd(d, p) = 1, then the normalized floating-point
r, ) = (m, e) such that m = H(p, r, c/d) and e = n.
Hensel code of is defined as the pair H(p,
Here m is the mantissa and e is the exponent. For example,
4, 2/3) = (.4131, 0)
H(5,
4, 2/3) = (.1313, 0)
H(5,
4, 2/15) = (.4131, 1)
H(5,
4, 2/15) = (.1313, 1)
H(5,
4, 10/3) = (.4131, 1)
H(5,
4, 10/3) = (.1313, 1) .
H(5,

12

Arithmetic using Floating-Point Hensel Codes

Consider the following example:

2
3

1
5

13
15 .

The Hensel codes are given as

4, 2/3) = (.4131, 0)
H(5,
4, 1/5) = (.1000, 1)
H(5,
First, we line up the p-adic points: (.1000, 1) = (1.000, 0) and then perform the addition
.4131
1.000
1.413
Hence, the sum is equal to (1.413, 0) = (.1413, 1) which is equal to 13/15.
Subtraction is performed by using complemented addition in the sense that the subtrahend
7
using Hensel
is complemented and added to the minuend. For example, to compute 23 15 = 15
4, 1/5) = (.4444, 1). We perform the operation
codes, we need H(5,
.4131
4.444
4.313
11

which gives (4.313, 0) = (.4313, 1), i.e., the Hensel code of 7/15.
For multiplication, consider the example: 31 65 = 25 .
4, 1/3) = (.2313, 0)
H(5,
4, 6/5) = (.1100, 1)
H(5,
The algorithm multiplies the mantissas
.2313
.1100
.2313
231
.2000
4, ) = (.2000, 1) which is equal to 2/5 since
and adds the exponents: 0 + (1) = 1. Thus, H(5,
ordinary Hensel code of 2/5 is equal to 2.000.

13

Normalization of Floating-Point Hensel Codes

4, 1/2) =
Consider the following operation 1/2 + 1/8 = 5/8 using floating-point Hensel codes, H(5,

(.3222, 0) and H(5, 4, 1/8) = (.2414, 0).

.3222
.2414
.0241
The table indicates that this is indeed the ordinary Hensel code of 5/8. However, we need to
compute its floating-point Hensel code of the form (.xyyy, e) where x is nonzero. How can this be
achieved? The following method is proposed:
Gregory & Krishnamurty: Convert the unnormalized Hensel code to its order N Farey fraction
and then map this number to its normalized floating-point Hensel code. For example, the
table indicates that .0241 is equal to 5/8. We then compute (using the table) the Hensel code
of 1/8 as .2414 which means the floating-point Hensel code of 5 81 is equal to (.2414, 1).
Colagrossi & Miola: Soon to be investigated.

14

Research Directions
Area and time complexity of the binary versus p-adic floating-point number systems.
Efficient algorithms for conversion, magnitude detection, and normalization of Hensel codes.
Detection of overflow and underflow.
Applications of p-adic arithmetic in computational algebra and scientific computing.

More about p-adic arithmetic and Hensel codes can be found in the following books [1, 4, 6] and
the papers [8, 5, 3, 10, 11, 7, 12, 13, 9, 2].
12

References
[1] G. Bachman. Introduction to p-Adic Numbers and Valuation Theory. Academic Press, New
York, NY, 1964.
[2] R. N. Gorgui-Naguib and R. A. King. Comments on Matrix processors using p-adic arithmetic
for exact linear computations. IEEE Transactions on Computers, 35(10):928930, October
1986.
[3] R. T. Gregory. The use of finite-segment p-adic arithmetic for exact computation. BIT,
18(3):282300, 1978.
[4] R. T. Gregory. Error-Free Computation. Huntington, NY: Robert E. Krieger Publishing
Company, 1980.
[5] R. T. Gregory. Error-free computation with rational numbers. BIT, 21(2):194202, 1981.
[6] R. T. Gregory and E. V. Krishnamurthy. Methods and Applications of Error-Free Computation.
Springer, Berlin, Germany, 1984.
[7] E. C. R. Hehner and R. N. S. Horspool. A new representation of the rational numbers for fast
easy arithmetic. SIAM Journal on Computing, 8(2):124134, May 1979.
[8] P. Kornerup and R. T. Gregory. Mapping integers and Hensel codes onto Farey fractions. BIT,
23(1):920, 1983.
[9] E. V. Krishnamurthy. Matrix processors using p-adic arithmetic for exact linear computations.
IEEE Transactions on Computers, 26(7):633639, July 1977.
[10] E. V. Krishnamurthy, T. M. Rao, and K. Subramanian. Finite segment p-adic number systems
with applications to exact computation. Proc. Indian Acad. Sci., 81A(2):5879, 1975.
[11] E. V. Krishnamurthy, T. M. Rao, and K. Subramanian. p-Adic arithmetic procedures for exact
matrix computations. Proc. Indian Acad. Sci., 82A(5):165175, 1975.
[12] A. Miola. Algebraic approach to p-adic conversion of rational numbers. Information Processing
Letters, 18(3):167171, 30 March 1984.
[13] C. J. Zarowski and H. C. Card. On addition and multiplication with Hensel codes. IEEE
Transactions on Computers, 39(12):14171423, December 1990.

13