Digital computation method involving euclidean division

Abstract

A computational method for implementation in an electronic digital processing system performs integer division upon very large (multi-word) operands. An approximated reciprocal of the divisor is obtained by extracting the two most significant words of the divisor, adding one to the extracted value and dividing from a power of two out to two significant words. Multiplying this reciprocal value by a remainder (initialized as the dividend) obtains a quotient value, which is then decremented by a random value. The randomized quotient is multiplied by the actual divisor, and decremented from the remainder. The quotient value is accumulated to obtain updated quotient values. This process is repeated over a fixed number of rounds related to the relative sizes in words of the dividend and divisor. Each round corrects approximation and randomization errors from a preceding round.