12
$\begingroup$

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask for is not (necessarily) an algorithm for Remainder Calculation. I just want to know whether $a$ divides $b$ or not. Being more specific, my question is whether exists or not some recent algorithm for Divisibility with time complexity better than $O(m\log m\log\log m)$, where $m$ is the number of bits of $\max\{a,b\}$. Further, is $\Omega(m\log m\log\log m)$ the lower bound of this problem?

Thanks and regards, and sorry if this is such a naive question.

$\endgroup$
  • $\begingroup$ AFAIK there are no non-trivial lower bounds known. I believe multiplication and division are known to have essentially the same complexity (though it may possibly be up to a log log factor?) via Newton's method, and since there's no known nonlinear lower bound on multiplication then I think any lower bound of the form you're stating would be a major result. $\endgroup$ – Steven Stadnicki Jul 26 '13 at 0:27
  • $\begingroup$ (Actually, looking at it now I think the log log factor goes away because while you're doing a nonconstant number of multiplications, they're not all of the same length, so the superlinear factors can be absorbed in the same way that, e.g., $\sum_{k=1}^{\lfloor\lg n\rfloor} \frac{n}{2^k}$ is still linear in $n$ even though it has a nonconstant number of 'linear' factors.) $\endgroup$ – Steven Stadnicki Jul 26 '13 at 0:33
4
$\begingroup$

Fleshing out my comments into an answer: since divisibility is (trivially) reducible to division, and since division is (nontrivially) reducible to multiplication via approaches like Newton's method, then your problem should have the same time complexity as integer multiplication. AFAIK, there are no known lower bounds for multiplication better than the trivial linear one, so the same should hold true of your problem - and in particular, since multiplication is known to have (essentially) $O(n\log n\log^* n)$ algorithms, your hopes for a $n\log n\log\log n$ lower bound are almost certainly in vain.

The reason that division reduces precisely in complexity to multiplication — as I understand it — is that Newton's method will do a sequence of multiplications of different escalating sizes; this means that if there's an algorithm for multiplication with complexity $\Theta(f(n))$ then the complexity of a division algorithm using this multiplication algorithm as an intermediate step will be along the lines of $\Theta\left(\sum_{k=0}^{\lg n} f(\frac{n}{2^k})\right)$ — and for all of the complexity classes under discussion this is just $\Theta(f(n))$.

$\endgroup$
  • 2
    $\begingroup$ Nitpick: I don't see how you get a lower bound from this kind of reasoning, even if we assume there are no better algorithms for multiplication than the best ones currently known. Your reductions imply that divisibility is no harder than multiplication. But there's still the possibility that divisibility might be easier than division and easier than multiplication, as divisibility only requires a yes/no answer instead of a number. (At least, the reduction you mention doesn't seem to rule that out.) $\endgroup$ – D.W. Jul 6 '16 at 20:20
  • 2
    $\begingroup$ @D.W. Agreed, and that's an excellent point; but I wasn't trying to get a lower bound. Rather, the point is that any lower bound on divisibility implies the corresponding lower bound on multiplication, and since no such bounds are known beyond the trivial linear bound, then getting any better-than-linear lower bound on divisibility (which is part of what OP asked for) is unlikely. $\endgroup$ – Steven Stadnicki Jul 6 '16 at 21:20
  • $\begingroup$ @D.W. I wouldn't be wholly shocked to learn of a linear upper bound on divisibility, and as you say that wouldn't specifically imply anything about upper bounds on multiplication, but there are no specific results in that direction AFAIK. $\endgroup$ – Steven Stadnicki Jul 6 '16 at 21:21
-2
$\begingroup$

I think there are Vedic type of hacks for some numbers ending in 3,7 etc. Or base 2^n divisors...

But generally speaking, the fastest division algorithm seems to be the norm.

The best one I know of without looking is Algorithm D of Knuth's Seminumerical methods... Never checked its correctness though. It runs in more or less O(mn-n^2) where m and n are the dividend and divisor... without factoring multiplication complexity...

A lower bound however could be surpringly low as your question is only concerned with the decision problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.