p-adic arithmetic: a tool for error-free computations
In this paper we propose the use of the p-adic arithmetic as a basic computational tool for a symbolic computation system in the framework of the TASSO project. This arithmetic has been chosen for two main reasons.
- PDF / 1,435,998 Bytes
- 15 Pages / 439.37 x 666.14 pts Page_size
- 93 Downloads / 166 Views
1 Introduction In this paper we propose the use of the p-adic arithmetic as a basic computational tool for a symbolic computation system in the framework of the TASSO project. This arithmetic has been chosen for two main reasons. 1. p-adic arithmetic representation provides a unified form to treat numbers and functions by means of truncated power series and it constitutes the mathematical background for the definition of basic abstract data structures for a homogeneous computing environment. The problem of the approximation of numbers and functions necessitates an integrated environment allowing a unified representation. We have seen that a unified representation can be obtained when numbers and functions are represented by power series and p-adic analysis offers an appropriate mathematical settlement to handle with power series. Limongelli and Temperini (1997) show how it is possible to treat numbers by truncated power series, as well as the most general p-adic construction methods in an integrated computing environment. 2. p-adic arithmetic is an exact arithmetic and the algebraic bases on which it is founded overcome the problem of the floating point arithmetic, which is essentially due to a lack of algebraic setting. Moreover, the truncated version of this arithmetic that we treat in this paper is suitable to represent numbers in a finite field. This last characteristic belongs to modular arithmetic too (Knuth 1981, Gregory and Krishnamurthy 1984), but the difference is that while modular arithmetic works over the integers, p-adic arithmetic operates on rational numbers. Limongelli (1997) shows the advantages due to the possibility of working directly over the rationals. Moreover, Limongelli and Temperini (1997) and Limongelli (1993a) show that also algebraic numbers are representable in this arithmetic. Limongelli (1997, 1993b) proved the possibility of speeding up the computations via its parallelization from both a theoretical and practical point of view. Despite its characteristic of modularity and its powerful algebraic properties (completeness of the p-adic metric space; Koblitz 1977), this arithmetic has not A. Miola et al. (eds.), Advances in the Design of Symbolic Computation Systems © Springer-Verlag/Wien 1997
A. Colagrossi et al.
54
received much attentions because of some computational problems, due to the possible lack of the significant digit of the code. In this paper we show how it is possible to overcome this problem. Actually the only critical point is due to the division operation. We propose a suitable algorithm for the division operation and we show how it is possible to carry out computations with a very low probability of obtaining an actual lack of approximation. The next section describes the algebraic bases of the proposed arithmetic. Section 3 shows the algebra of the Hensel code set and Sect. 4 is devoted to the treatment of the pseudo-Hensel codes which occur when a significant digit of the code is missed. Section 5 concludes the paper with a description of the possible further
Data Loading...
