|
|
1.Introduction
In this text two significant examples of on-line computations have been developed: fully on-line solving a linear system of algebraic equations and an on-line computation of a located real root of a polynomial with real coefficients. Our purpose is limited to a demonstration of the existence of the on-line algorithms. The problem of establishing the convergence criterions is not discussed here. Therefore many important details such as determining the range of convergence, estimating the numerical accuracy, the choice of the selection rules, pre-computing the on-line delays are not mentioned at all.
On-line algorithms receive their input data and give their results serially, most significant digit first. By definition in order to generate the j-th digit of the result (j+d) digits of the corresponding operands are required. The on-line delay d is usually a small integer.
We use radix-2 number system in our examples. Of course when hardware-oriented algorithms are implemented the time and area complexity plays a decisive role, so the use of a higher radix number system is highly desirable. But from a strictly theoretical point of view the binary number system is as powerful as any higher radix number system. And what is more important: it offers a simplicity of theoretical constructions not feasible if higher radix number systems are used. This observation can be illustrated by the long history of the CORDIC method, starting from J. Volder [1] and reaching in our judgment rather respectable achievements namely: the Householder CORDIC algorithms [2] and the BKM method for complex elementary functions [3](see also [4]). In both mentioned cases radix-2 number system was utilized.
We hope that our two examples deserve a serious consideration. Evidently the potential of developing new digit-by-digit (digit-recurrence or shift-and-add) methods is far from being exhausted. The same holds for the redundant and on-line methods which are in fact a partial case of the more general digit-by-digit approach.
