Fast recursive division
Christoph Burnikel, Joachim Ziegler · Max Planck Digital Library · 1998
We present a new recursive method for division with remainder of integers. Its running time is 2K(n)+O(n log n) for division of a 2n-digit number by an n-digit number where K(n) is the Karatsuba multiplication time. It pays in practice for numbers with 860 bits or more. Then we show how we can lower this bound to 3=2K(n)+O(n log n) if we are not interested in the remainder. As an application of division with remainder we show how to speedup modular multiplication. We also give practical results of an implementation that allow us to say that we have the fastest integer division on a SPARC architecture compared to all other integer packages we know of. Keywords Multiprecision Arithmetic, Integer Arithmetic, Karatsuba Method, School Methods, Fast Division, Division Without Remainder, Modular Reduction 1 Introduction Multiprecision arithmetic is the art of computing with numbers that are larger than one machine word. It is an important subject in many domains of computer science, e.g....