#StackBounty: #complexity-theory #time-complexity #arithmetic #number-theory How does the bitlength of the divisor affect the running-t…

Bounty: 50

Wikipedia lists $$O(M(n))$$ as the best complexity (out of the algorithms listed) for division on two $$n$$-digit numbers, where $$M(n)$$ is the complexity of the multiplication algorithm of choice. This is the complexity of the Newton-Raphson division.

My question is this: what are some of the best known (wrt. running-time complexity as a function of $$n$$) algorithms for division of two numbers, of m, and $$n < m$$ digits respectively? That is, how much complexity can be gained when the two numbers are not assumed to be of the same length?

I wouldn’t want to treat $$n$$ as a constant as I’m in particularly interested in the case of $$n in O(log{m})$$. So I’m not looking for answers that treat $$n$$ as in $$O(1)$$.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.