Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible by $a$, and FALSE otherwise. I understand that there is no proof that divisibility is not in $L$ since that would imply $P \ne L$ which is open. Also I understand that if there is a nondeterministic algorithm in $O(\log(n)^k)$ then there is a deterministic algorithm in $O(\log(n)^{2k})$, by Savitch's theorem. I believe I've figured out an $L$ algorithm to verify $a*b=c$, and also an $FL$ algorithm to compute $c$ (essentially the method I was taught in grade school, reusing ink when possible), but I haven't been able to adapt it to divisibility. Is such an algorithm for divisibility known?

share|improve this question
    
Isn't the euclidean algorithm log space and with the identity $a | b$ iff $\gcd(a,b)=a$, wouldn't this give you a logspace algorithm? –  JSchlather Oct 25 '11 at 6:08
1  
If so, yes, but I don't know how to make the Euclidean algorithm log-space either. The way I would ordinarily implement it is O(n) space. Note that n ~ log(b) here, so log-space means O(log(log(b))) space. –  Dan Brumleve Oct 25 '11 at 6:13
1  
The euclidean algorithm is most certainly an overkill; if b divides a, it will be discovered in the first step of the algorithm (where we divide a by b and take the remainder)... –  Gadi A Oct 25 '11 at 7:53
1  
@user7530, all the digits can be examined, they just can't be copied into working space at the same time. See en.wikipedia.org/wiki/L_(complexity%29. My intuition is that divisibility is in P and P=L might be true, and also it seems like an easy P problem compared to others. –  Dan Brumleve Oct 25 '11 at 8:40
1  
Integer division is known to be in L. Page 22 of the slides “My Favorite Ten Complexity Theorems of the Past Decade II” by Lance Fortnow refers to Chiu 1995, although I cannot locate this reference right now. If you can access Chiu, Davida, and Litow 2001, I am sure that it contains the reference to it. –  Tsuyoshi Ito Oct 25 '11 at 13:46

2 Answers 2

up vote 6 down vote accepted

(This is an updated version of my comment on the question.)

Beame, Cook, and Hoover [BCH86] showed that integer divisibility is in L. More recently, Chiu, Davida, and Litow [CDL01] showed that integer division is also in L.

References

[BCH86] Paul W. Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM Journal on Computing, 15(4):994–1003, Nov. 1986. DOI: 10.1137/0215070

[CDL01] Andrew Chiu, George Davida, and Bruce Litow. Division in logspace-uniform NC1. Theoretical Informatics and Applications, 35(3):259–275, May 2001. DOI: 10.1051/ita:2001119.

share|improve this answer
1  
By the way, according to the introduction of [BCH86], there seems to be a folklore O((log n)^2)-space algorithm. –  Tsuyoshi Ito Oct 26 '11 at 23:13
2  
I realized that the master thesis of Chiu in 1995 seems to contain a proof that integer division is in L (and more strongly in log-space-uniform NC1), and I am not sure its relation to [CDL01] because I cannot access [CDL01]. –  Tsuyoshi Ito Oct 26 '11 at 23:41
1  
Even more is true, we know that it is in uniform $TC^0$. –  Kaveh Nov 2 '11 at 16:59
1  
@Kaveh: That is true. I did not mention that result in the answer because I wanted to keep the answer simple by focusing on space complexity by a Turing machine. –  Tsuyoshi Ito Nov 10 '11 at 21:40

Edited to add: As Gadi points out in a comment, this answer is wrong.

If you have a logspace algorithm to verify $x \times y = z$, then since you're not concerned with running time, you can simply check, for all $c$ with $1 < c \le b$, whether $a \times c = b$.

share|improve this answer
2  
I believe he meant that the algorithm is logspace in the sum of lengths of x,y,z. What you suggest is not logspace since writing c takes up space on the work tape. –  Gadi A Oct 25 '11 at 12:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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