Patent GB-1214987-A (GB)
Title: A computing device
Inventor: AKUSHSKY IZRAIL YAKOVLEVICH
IPC: G06F7/72
Filed: 1967-12-13
Abstract: 1,214,987. Calculating apparatus. I. Y. AKUSHSKY and D. I.-G. JUDITSKY. 13 Dec. 1967] No. 43348/67. Heading G4A. The specification shows how a representation of a number by an ordered set of residues can be augmented by a redundant digit-referred to as the "weight" of the number-and how when calculations are performed using this particular form of representation it is possible to decide from an analysis of the weights of the numbers involved in the calculaion whether any number formed during the calculation lies outside the range of numbers that can be represented uniquely. The specification also describes a method of computing the value of the number that a given set of ordered residues and their associated weight digit represents. In the system of ordered sets of residues a base B having mutually prime positive integral components {b i } is chosen, and a given number N is represented by its set of least positive residues {n i } with respect to the base components. For example with a base of B = (3, 5, 7), the number 48 is represented by (0, 3, 6), since 48 = 0 (mod 3), 48 = 3 (mod 5), and 48 = 6 (mod 7). With this system of representation, the sum, difference and product of two numbers is represented respectively by the residues with respect to the appropriate base components of the sum difference and product of their corresponding components. The system can also be extended to division. For example with the same base as above if F = 48 = (0, 3, 6) and G = 17 = (2, 2, 3), then addition is as follows:- F = (0, 3, 6) = 48 G = (2, 2, 3) = 17 F + G = (2, 0, 2) = 65 Since 0 + 2 = 2 (mod 3), 3 + 2 = 0 (mod 5), and 6 + 3 = 2 (mod 7). However, with this system of representation any number that should result with a value larger than the product of the base components #b i  will result with an incorrect representation. Thus, with the above values F.G = 816 which is greater than the product of the base components, 105, and therefore if the components of F and G are multiplied in accordance with the above rules an erroneous value namely (0, 1, 4) which represents 81, will result. It is difficult to decide when an error of this type-referred to as an 'overflow' error-has occurred. The present invention eases this difficulty by associating a weight component with each set of residues. When two numbers are combined their weights are combined in a related manner to give the weight of the resulting number, and if this resulting weight is larger than a constant related to the base, an overflow has occurred. The specification only exhibits the technique in detail as applied to addition, to determine whether overflow has occurred, and to subtraction, to determine the sign of the difference, but it envisages the technique also being applied to multiplication and division. The specification first describes a system for representing polynomials by ordered sets of remainders, and shows how addition, subtraction and multiplication of polynomials can be performed by performing similar (but non- modulo) artithmetic operations upon their remainders. This system is then related to the residue system for numbers and to its modulo arithmetic. Then the concept of weight is introduced, and finally methods of extending the base and of restoring numbers from their residues are discussed. Let a base # (x) have components {P i (x)}, 1 # i # n+ 1 where P i (x) = x-# i , the #'s being integral and non-equal. Let be a polynomial of degree m # n with integral coefficients. Let so that Also let Then by using Lagrange's interpolating formula it follows that where the dash denoting differentiation in the usual way. For a given base #(x) and a given polynomial N(x) the remainders γ i  are uniquely determined. The ordered set of remainders {γ i } is said to constitute a representation of the polynominal N(x) on the base #(x). It can be shown that if N 1 (r) and N 2 (x) are two /polynomials of degrees m 1  and m 2  respectively with representations {γ<SP>1</SP> i } and {γ<SP>2</SP> i } on #(x), then N 1 (x) Œ N 2 (x) has a representation {γ<SP>1</SP> i  Œ γ<SP>2</SP> i } and N 1 (x).N 2 (x) has a representation {γ<SP>1</SP> i γ<SP>2</SP> i } providing in the first case that m 1 , m 2  # n and in the second case that m 1  + m 2  # n. Moreover, having obtained the representation of a new polynomial, its actual form can be restored by using equation (2), since the coefficients A i (x) are determined completely by the base #(x).  By giving x a specific value in the above, say x 0  and for brevity when x has the value x 0  the argument will be omitted, a representation {γ i } on a base # is obtained for the number N. The system then resembles the system of ordered sets of residues except that the arithmetic is non-modulo. Thus, in order to manipulate two numbers in this system, it is merely necessary to find two polynomials having the given numbers as their values when their arguments are x 0 . Representation of the two numbers can then be found. For example, if so that equation (2) becomes then to find a representation for the number 48 it is necessary to find a polynomial, of degree 2 or less, whose value is 48 when x = 10. Choose F(x) = 4x+8, then F(10) = F = 48, and using the above rules, the representation for F(x) is F(x) = (36, 28, 20) Similarly, if G(x) is chosen as x + 7, so that G = 17 then G(x) = (14, 12, 10). Then for addition and if F + G is restored by equation (3) Although this polynomial remainder system has a very convenient and precise restorating formula (3) it lacks the main advantage of the residue system in that its arithmetic is non-modulo in character. However, a relationship can be established between the two systems. Let the number N have, as above, a polynomial remainder representation of {γ i } on the base # = {P i }. Also let the number N have a residue representation of (α i ) on a base B = {P i }. In other words B = #(x 0 ). Then N = q i P i  + γ i , from equation (1), and also N = α i (mod P i ) Hence, γ i  = α i  + K i P i  (4) where Ki is an integer. Using this result in equation (2) it follow that which can be arranged as where D is the smallest positive integer to make all the other terms in the sum integers also. The weight W(N) of the number N is defined by Reverting to the previous example in which and then from equation (4) and hence, using equation (3) Thus for this particular base and choice of  x0 , For the number 48, a polynomial remainder representation (the one used above) is 48 = (36, 28, 20) and hence, bearing in mind equation (4), Thus, and from equation (6) the weight of the number 48 is 4. According to the specification it can be shown that the weight of a number is independent of the particular polynomial chosen to represent it. The expression for the weight of a number given above can be rearranged. From the theory of residue representations it is known that if a number N has a representation {α i } on a base B = {P i } then where if and if then From equations (5) and (8) it follows that where Reverting again to the above example, from equations (5), (6) and it can be shown that then and hence W(N = 5α 1  + 2α 2  + α 3  (mod 8) (10) so that for the number 48, which has a residue representation of (0, 3, 6), In other words, if a base B of a residue system is a special case of a base #(x) of a polynomial system, it is possible to establish a formula, namely equation (9), for the weight of a number in terms of its residues. According to the specification, the weight of the sum of two numbers N 1  = {α<SP>1</SP> i } and N 2  = {α<SP>2</SP> i } is given by where # i  = 1 if α<SP>1</SP> i  + α<SP>2</SP> i  # P i  = O otherwise. and # i  is as defined in equation (5). Furthermore, if W(N 1  + N 2 ) > D, D being as defined in equation (5) also, then N 1  + N 2  > P and an overflow error will occur. Subtraction can be effected by complementary addition, N 1  - N 2  becoming N 1  + #N 2 , where #N 2  = P - N2. The weight of the difference then determines the sign of the difference. Thus, if W(N 1  - N 2 ) # D, then N 1  > N 2 . The weight digit can also be used, according to the specification, in association with division, but only one example, namely division by 2 is described. If division of N by 2 is effected by formal multiplication by its reciprocal 2* = (2, 3, 4) 2À2* = 1 mod (3, 5, 7) then the result will only represent the correct result ¢N if N is even. If N is odd the result is completely spurious, but a rounded up or down result can be obtained by multiplying NŒ 1 formally by 2*. If N 1  is obtained formally by multiplying N by 2, then N 1  only represents ¢N if W(N 1  + N 1 ) < D. As an example in computing weight digits, consider the numbers F = 48 = (0, 3, 6) and G = 17 = (2, 0, 2). By using equation (10), namely. and Also, from equation (5) and (7). and hence addition is as follows;- and from equation (11) hence W(F + G) = 4 + 4 + 0À1 + 1À(-2) + 1À1 = 7 Thus, W(F + G) < 8. and therefore the sum F + G = (2, 0, 1) is correct and no overflow error arises. The restoration of polynomials from their representations {γ i } can be effected by using equation (2). The restoration of numbers from their residues {α i } can be effected similarly by deriving the corresponding polynomial representation {γ i } from {α i }. This can be done by using equation (4), the values of K; being assigned arbitrarily (e.g. all zero except one) such that The fact that the values of K i  can be assigned arbitrarily is assumed by the specification as a consequence of the invariance of the weight with the form of N(x). The representation of a polynomial N(x) on a base #(x) = {x - # i }, 1 # i # n+ 1, can be extended to a base #<SP>1</SP>(x) = {x-# i }, 1 # i # n + 2, by obtaining the value of γ n+2  = N(# n+2 ) from equation (2), the values