Nega-base computer arithemetic-theory and applications

Abstract

This dissertation presents a detailed study of negative base number representation—the theory as well as the development of suitable algorithms for building the arithmetic unit of a digital computer. The idea of negative base representation is relatively new. Quite a few people have had this idea in connection with computer design. The present study is motivated towards the development of rigorous algorithms for all the basic arithmetic operations, square rooting and evaluation of important elementary functions. In addition, a few number-theoretical problems associated with the negative base representation are also studied. The important contributions of this dissertation fall under three major classes: i) Studies on Negative Base Representation: a) A proof for the uniqueness of the negative base representation of integers. b) Classification or parametrization of the family of fractions which do not possess a unique negative base representation. c) Studies on periodic decimals in a negative base. Two new interesting theorems have been proved in this connection: The first theorem brings out the relationship between the periods of prime reciprocals in a positive base p and that in a negative base -p; the second theorem proves what we call the "annihilation property", which holds for even-period prime reciprocals in a negative base. [If the decimal expansion of a prime reciprocal of period 2w in a negative base -p is split into two halves and added in base p, the sum is zero if the prime p is greater than or equal to p + 2 and (-p)^w if the prime p is less than p; this property is defined as "annihilation property".] A number of other earlier known interesting theorems (Mandelbaum (196?) [6]) for positive base periodic decimals have also been extended for the case of negative base. ii) Design of Negative Base Arithmetic Algorithms: a) A new unary operation called "Polarization" which changes the sign of a number has been introduced. This operation has no analogue in the positive base arithmetic, as it is required only for subtraction. Thus it has a different function from the complement code used for representing the negative numbers in the positive base. Fast and economical hardware algorithm for realizing the polarization has been developed by Sankar et al. (1973) [7]; this algorithm is no more complicated (hardware- wise) than the conventional complementation. This is an important aspect which de Regt has failed to highlight, while discussing the merits of the negative base representation. b) Hardware algorithms for the basic arithmetic operations, viz. addition, subtraction, multiplication, non-restoring division—all these are analogous to positive base algorithms; in fact multiplication turns out to be much simpler due to the fact that complement corrections are not involved. c) Development of a deterministic division algorithm in which the divisor is mapped into a suitable range by premultiplication, so that the selection of the quotient digit does not involve a trial-error procedure and is deterministic. d) Design of algorithms for multiple precision operations—in particular, divide and correct procedure for division of variable word length negative-base operands. e) The extension of the classical, positive base algorithm for square-rooting a number in a negative base. f) Economic digit-by-digit algorithms for the evaluation of elementary functions like logarithm, arctan and square-rooting, in a negative base. iii) Construction of Negative Base Log Tables: A study of the construction and use of logarithmic tables in a negative base to facilitate manual or machine computations of complicated arithmetic functions involving multiplication, division and exponentiation