Patent ID: 7516172

Claim:
In a system for digital information processing, said system having a memory, a method for generating data representative of a quotient Q=a 0 a 1 a 2 . . . a b from data representative of a divisor Y=y 1 y 2 . . . y n and data representative of a dividend X=x 1 x 2 . . . x a , comprising the steps of: (a) aligning the first non-zero bit of X with the first non-zero digit of Y; (b) defining a signed-digit partial remainder series R i where R 0 =Y, a first sign series of the partial remainder S i where S 0 =0, a second sign series of the partial remainder S ri , a quotient bit series a i , and a counter i beginning from zero; (c) subtracting X from R i which yields next signed-digit partial remainder R i+1 ; (d) setting the sign of R i+1 to S ri+1 ; (e) setting the result of exclusive-OR of S i and S ri+1 to the true sign of the next remainder S i+1 ; (f) setting a i to 1 if S i+1 =0 or R i+1 =0; (g) setting a i to 0 if S i+1 =1; (h) inverting the signs of all digits of R i+1 if S i+1 =1; (i) shift R i+1 left by one bit; (j) adding 1 to i; (k) repeating steps (c) to (j) until i reaches a predetermined value or R i+1 =0; and (l) storing in said memory as said data representative of a quotient, a quotient resulting from step (k).