Patent ID: 7672990

Claim:
A method implemented in an electronic digital processing system for performing an integer division computation upon large multi-word operands, the method comprising: (a) loading dividend and divisor operands into storage locations accessible to the processing system; (b) initializing a quotient and a remainder; (c) extracting a specified number of most significant words of said divisor, incrementing the extracted value, and computing a reciprocal thereof with said specified number of significant words; (d) executing by said processing system of a number of rounds, each round including: (i) multiplying said remainder and reciprocal to obtain a quotient value for that round with said specified number of significant words; (ii) decrementing the quotient value by a random value of a size not more than one bit less than one word; (iii) multiplying the quotient for that round by the divisor and subtracting a resulting product from the remainder to update the remainder; and (iv) left shifting the partial quotient by a number of words for that round and adding to the quotient to accumulate the quotient; and (e) if the remainder after the last round is still larger than the divisor, then subtracting the divisor from the remainder and incrementing the quotient until the remainder is less than the divisor, thereby obtaining the quotient and remainder for the loaded dividend and divisor.