On-line Multiplication and Division in Real and Complex Bases

摘要

A positional numeration system is given by a base and by a set of digits. The base is a real or complex number β such that |β| > 1, and the digit set A is a finite set of real or complex digits (including 0). In this paper, we first formulate a generalized version of the on-line algorithms for multiplication and division of Trivedi and Ercegovac for the cases that β is any real or complex number, and digits are real or complex. We show that if (β, A) satisfies the so-called (OL) Property, then on-line multiplication and division are feasible by the Trivedi-Ercegovac algorithms. For a real base β and alphabet A of contiguous integers, the system (β, A) has the (OL) Property if #A > |β| . Provided that addition and subtraction are realizable in parallel in the system (β, A), our on-line algorithms for multiplication and division have linear time complexity. Three examples are presented in detail: base β = 3+√5/2 with alphabet A = {-1, 0, 1}; base β = 2i with alphabet A = {-2, -1, 0, 1, 2} (redundant Knuth numeration system); and base β = -3/2 + z√3/2 = -1 + ω, where ω = exp 2iπ/3 , with alphabet A = {0, ±1, ±ω, ±ω2} (redundant Eisenstein numeration system).