Patent ID: 7016930

Claim:
A method of operating a data processing apparatus to perform a division operation to divide a dividend by a divisor, the division operation being implemented by iterative execution of a recurrence equation, in each iteration, execution of the recurrence equation causing a predetermined number of bits of a quotient, and a partial remainder, to be generated, the partial remainder generated in a previous iteration being used as an input for the current iteration, and in the first iteration the dividend forming the input partial remainder, the method comprising the steps of: (a) for a current iteration, (i) determining from the divisor and a most significant n bits of the input partial remainder a next quotient digit; (ii) generating, based on the input partial remainder, the divisor and the next quotient digit, a next partial remainder, the most significant n bits of the next partial remainder being generated in non-redundant form and the remaining bits of the next partial remainder being generated in redundant form; (iii) modifying the quotient, having regard to the next quotient digit, to produce an updated quotient; (b) iterating said steps (a)(i) to (a)(iii) until a predetermined condition is met, whereafter the result of the division operation is indicated by the updated quotient and any partial remainder existing after the final iteration.