Next: Exact Division, Previous: Divide and Conquer Division, Up: Division Algorithms [Index]

For the largest divisions, a block-wise Barrett division algorithm is used. Here, the divisor is inverted to a precision determined by the relative size of the dividend and divisor. Blocks of quotient limbs are then generated by multiplying blocks from the dividend by the inverse.

Our block-wise algorithm computes a smaller inverse than in the plain Barrett
algorithm. For a *2n/n* division, the inverse will be just *ceil(n/2)* limbs.