Node:Divide and Conquer Division, Next:Exact Division, Previous:Basecase Division, Up:Division Algorithms
For divisors larger than DIV_DC_THRESHOLD, division is done by dividing.
Or to be precise by a recursive divide and conquer algorithm based on work by
Moenck and Borodin, Jebelean, and Burnikel and Ziegler (see References).
The algorithm consists essentially of recognising that a 2NxN division can be done with the basecase division algorithm (see Basecase Division), but using N/2 limbs as a base, not just a single limb. This way the multiplications that arise are (N/2)x(N/2) and can take advantage of Karatsuba and higher multiplication algorithms (see Multiplication Algorithms). The "digits" of the quotient are formed by recursive Nx(N/2) divisions.
If the (N/2)x(N/2) multiplies are done with a basecase multiplication
then the work is about the same as a basecase division, but with more function
call overheads and with some subtractions separated from the multiplies.
These overheads mean that it's only when N/2 is above
MUL_KARATSUBA_THRESHOLD that divide and conquer is of use.
DIV_DC_THRESHOLD is based on the divisor size N, so it will be somewhere
above twice MUL_KARATSUBA_THRESHOLD, but how much above depends on the
CPU. An optimized mpn_mul_basecase can lower DIV_DC_THRESHOLD a
little by offering a ready-made advantage over repeated mpn_submul_1
calls.
Divide and conquer is asymptotically O(M(N)*log(N)) where M(N) is the time for an NxN multiplication done with FFTs. The actual time is a sum over multiplications of the recursed sizes, as can be seen near the end of section 2.2 of Burnikel and Ziegler. For example, within the Toom-3 range, divide and conquer is 2.63*M(N). With higher algorithms the M(N) term improves and the multiplier tends to log(N). In practice, at moderate to large sizes, a 2NxN division is about 2 to 4 times slower than an NxN multiplication.
Newton's method used for division is asymptotically O(M(N)) and should therefore be superior to divide and conquer, but it's believed this would only be for large to very large N.