Fast Recursive Division

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/2 K(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.