Efficient Quotients Using Exact Arithmetic

The usual formulation of efficient division uses Newton iteration to compute an inverse in a domain where multiplicative inverses exist. On one hand, this allows quotients to be calculated using an efficient multiplication method. On the other hand, working in another domain is not always desirable and can lead to a library structure where arithmetic domains are interdependent. This paper uses the concept of a shifted inverse and modified Newton iteration to compute quotients efficiently without leaving the original domain. The iteration is generic to Euclidean domains having a suitable shift operation, such as base-$B$ integers or polynomials in a monomial basis.