Patent ID: 8655937

Claim:
A computer-implemented method for performing integer division between a numerator and a denominator on a processing unit that supports operations using variables of a first bit size, wherein the numerator and the denominator are integers having a second bit size that is greater than the first bit size, the method comprising: subdividing the numerator into a plurality of equal sized partitions, wherein each partition has a third bit size; converting the denominator into a variable of the first bit size; dividing the numerator by the variable of the first bit size to obtain a current approximation of a current portion of a quotient, wherein the current approximation of the current portion of the quotient has the third bit size; subtracting a product of the current approximation of the current portion of the quotient and the denominator from the numerator to generate a subsequent numerator, wherein a fourth bit size of most significant bits associated with the subsequent numerator represents a bit overflow error value utilized to correct the first approximation of the first portion of the quotient; and storing the current approximation of the current portion of the quotient in a memory.