#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!!!

Leave a Reply

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