P-adic number systems for error-free computation

The structure and properties of the infinite field of p-adic numbers are examined. A simpler algorithm for finding the canonical p-adic expansion of a rational number is developed, and many expansions for various primes p are given. Several classical number theoretic results are combined to devise an algorithm for calculating the period for the infinite expansion of a rational number. Theorems concerning sign determination and the relationships between the p-adic and radix-p representations of a rational number are proved. These variable-length representations of rational numbers for digital computer use allow sign determination, magnitude comparison, error-free computation, and simple conversion from p-adic to rational form. The major disadvantages of this system are the unpredictability of storage requirements, decreased speed of computations, and the detection of periodicity in the computations.

These problems can be alleviated by considering a finite subset of the rationals F_N, the order N Farey Fractions, with fixed length representations called Hensel codes (in honor of Kurt Hensel who first introduced p-adic numbers into algebraic number theory). These finite segment p-adic numbers can be obtained by truncating the infinite p-adic expansions to r digits for all rational numbers in F_N, where p, r, and N are related by a specific formula which guarantees uniqueness of representation. Arithmetic operations on Hensel codes are particularly simple and error-free. It is the simplicity of division when compared to the same operation in multiple-modulus residue arithmetic which has created most of the current interest in p-adic number systems for digital computer use.

It is shown that no system of weights will enable all Hensel codes to be converted directly into order N Farey fractions. However, linear Diophantine equations can be derived which characterize all rational numbers corresponding to a given Hensel code. Furthermore, divisibility conditions and constraining inequalities can be devised for selecting the unique solution of the linear Diophantine equation in the range of allowable Farey fractions. The disadvantages of these fixed-length representations involve overflow prevention, sign determination, magnitude comparison, and the conversion from Hensel code to rational form.