3. Some remarks about division procedures

We state some well-known facts here. However they are arranged suitably for our topic. The division of two numbers is in fact a solution of the linear equation,,where is the dividend ,is the divisor and the quotient is represented as a continued sum. If we view the division procedure the way it is taught in secondary school, then we can observe that it is a typical algorithm with indirect convergence checking. The residuals are called partial remainders here,and ,for j = 0, 1, 2, ... For the scaled partial remainderswe have:

; ,j = 0, 1, 2, ...

There are three possibilities for the choice of the quotient digits. In the classical casebelongs to the non-redundant digit set { 0, 1}. Consequently the division becomes a trial-and-error procedure. At each iteration step the devisoris subtracted from the shifted partial remainder . If the new remainder is positive, then the quotient digit is set to 1. Otherwise the quotient digit is set to 0 and the previous value of the partial remainder is restored.

The second possibility is to use another non-redundant digit set {-1, 1},from which quotient digitsare chosen. In this case the division becomes a non-restoring procedure in the sense that negative values of partial remainders are permitted. If the subtraction of the devisor from the shifted partial remaindergives a negative result, then the quotient digit is set to -1.

Notice that in both cases we never care about the exact value of the partial remainder when choosing the quotient digits. Only the sign of the remainder is taken into consideration when the choice is made.

And finally the third possibility is to use the redundant digit set {-1, 0, 1} to represent the quotient digits. This method is known as SRT-division. Again the full precision represented partial remainders are not required for the choice of the quotient digitsat each iteration step. The selection ofis made by comparing a severely truncated version of the partial remainder, containing only a few digits with two simple comparison constants. These constants are simple in a "binary" sense, they are equal toetc. That makes the comparison itself and the selection procedure rather simple and fast operations.

So the conclusion is that even if a redundant number system is used, the division procedure is based strictly on indirect convergence checking. This is a fundamental property of all digit-recurrence (i.e. shift-and-add) methods.

To solve a linear system of algebraic equations means to solve the matrix equation. Therefore we can consider this operation to be a n-dimensions generalization of the simple division of two numbers.

The E-method and the new fully on-line method we proposed for solving linear systems of algebraic equations are based on indirect convergence checking too. However there is only one option for the representation of the result digits("the quotient digits"): the redundant digit set {-1, 0, 1}. Trial-and-error procedures and non-restoring schemes are not possible!

The analogy between the division of numbers and solving the linear systems of algebraic equations goes further. As mentioned above one of the first on-line algorithms was the on-line division [8]. In the previous section we demonstrated that an on-line algorithm for solving linear systems also exists. The recurrence equations for the on-line division (in our terms) are as follows:

The reader may compare the last equation with (13) and draw his (her) own conclusions.

Now suppose we decide to utilize continued-product representation of the quotient instead of the widespread and convenient for every day use continued-sum representation. This will lead us to the following formulae (we list the formulae without any commentary ) [9]:

;

;

;

;

.

Our first observation is that this time the dividend is subtracted from the partial remainders, not the devisor. The devisorforms the initial value . We might conclude that in some sense the dividend and the devisor have changed their roles in the division procedure. And of course there is an additional memberin the right-hand side of the equation so the recurrences are more complex and more difficult to implement compared to the classical continued-sum based case. Next we remark that the trial-and-error procedure using the non-redundant digit set { 0, 1} converges. However the non-restoring scheme utilizing the non-redundant digit set {-1, 1} is not convergent. If the redundant digit set {-1, 0, 1} is used to represent the quotient digits the division procedure can be convergent again. An exact and elaborate analysis of the convergence of this type of division with continued-product represented quotient,using the redundant digit set {-1, 0, 1} for the partial case when can be found in [4].

And at the end let us get back to the scalar equationagain. We can view the division procedure defined by this equation as computing the root of a first-degree polynomial. Having accepted such an approach we propose an n-degree generalization of the division in the next section. It will not be a surprise if this new method for computing a real root of an n-degree polynomial turns out to be a procedure with indirect convergence checking again. The real news here is the fact that we have found a digit-recurrence procedure for computation of an implicit function.