Efficient Quotients Using Exact Arithmetic

One method to compute multiple precision integer quotients is to use a Newton iteration with multiple precision fixed point or floating point values. On one hand, this allows quotients to be calculated efficiently by employing an efficient multiplication method. On the other hand, this leads to a library structure where exact and approximate arithmetic are interdependent. This paper develops the concept of a shifted inverse and modified Newton iteration to compute quotients efficiently using whole numbers only. The method is equally applicable to computing polynomial quotients efficiently.