Cheap and Secure Web Hosting Provider : See Now

[Answers] What is the fastest way to check if an integer is divisible by another?

, , No Comments
Problem Detail: 

What would the Big O be? Can something like this be done in O(log(n)) where n is the number of bits?

Asked By : Askeroni

Answered By : D.W.

Integer division

The best algorithm known for integer division has running time that is slightly more than linear, i.e., a bit more than $O(n)$. In particular, it is something like $O(n \lg n 2^{\Theta(\lg^* n}))$ (which is a bit faster than $O(n \lg n \lg \lg n)$. The time complexity of integer division is the same as the time complexity of integer multiplication. See https://en.wikipedia.org/wiki/Division_algorithm and https://en.wikipedia.org/wiki/Multiplication_algorithm.

Caution: these algorithms are purely theoretical. The constants hidden by the big-O notation make them impractical for most sizes you'll run into in real life. But there are plenty of other algorithms that are faster than the naive algorithm and are useful in practice.

No, you can't do it in $O(\lg n)$ time, where $n$ is the number of bits in the input: you obviously can't do it in less than $O(n)$ time, since it takes that much time just to read in the entire input.

Testing divisibility

The problem of testing divisibility could in theory be easier: it asks for just a yes-or-no answer (is $y$ divisible by $x$ or not?) instead of the result of the full division (compute $\lfloor y/x \rfloor$). Obviously, you can use any algorithm for integer division to test integer divisibility (with the same running time). I don't know if there is any faster way to test integer divisibility.

A conceptually simple way to test whether $y$ is divisible by $x$ is to check whether $y \bmod x$ is zero or not. However, I don't know of any way to compute the remainder $y \bmod x$ in linear time (in time linear in the number of bits of the input, i.e., in $O(n)$ time, where $n=\lg(x)+\lg(y)$). As before, you obviously can't do it in less than $O(n)$ time.

See also http://cstheory.stackexchange.com/q/16788/5038, which basically states the same thing: no faster algorithms are known, but no one has proven lower bounds ruling out the possibility of faster algorithms.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60374

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback