Prescaled integer division

We describe a high radix integer division algorithm where the divisor is prescaled and the quotient is postscaled without modifying the dividend to obtain an identity N=Q^*×D+R^* with the quotient Q^* differing from the desired integer quotient Q only in its lowest order high radix digit. Here the "oversized" partial remainder R^* is bounded by the scaled divisor with at most one additional high radix digit selection needed to reduce the partial remainder and augment the quotient to obtain the desired integer division result N=Q×D+R with 0≤R≤D-1. We present a high radix multiplicative version of this algorithm where a k×p digit base β rectangular aspect ratio multiplier allows quotient digit selection in radix β^k-1 with a cost of only one k×p digit multiply per high radix digit, plus the fixed pre- and post-scaling operation costs. We also present a Booth radix 4 additive version of this algorithm where appropriately compressed representation of the partial remainder with Booth digits {-2, -1, 0, 1, 2} allows successive quotient digit selection from the leading partial remainder digit without the iterative table lookups required in SRT division.