Problem Detail: Are there any known subquadratic algorithms for calculating the floor of the square root of an n bit integer? The naive algorithm would be something like
def sqrt(x): r = 0 i = x.bit_length() // 2 while i >= 0: inc = (r << (i+1)) + (1 << (i*2)) if inc <= x: x -= inc r += 1 << i i -= 1 return r
This takes O(n) iterations, each one involving additions that are O(n) time, so it’s O(n^2) time overall. Is there anything faster? I know that for the case of multiplication there are special algorithms that do better than quadratic time, but I can’t find anything for square roots.
Asked By : Antimony
Answered By : D.W.
You can use Newton’s method or any of a number of other methods for finding approximations to roots of the polynomial $p(x) = x^2 -c$. The rate of convergence for Newton’s method will be quadratic, which means that the number of bits that are correct doubles in each iteration. This means $O(lg n)$ iterations of Newton’s method suffice. Each iteration of Newton’s method computes $$x_{j+1} = x_j – (x_j^2 -c)/(2x_j) = 0.5 x_j + frac{c}{2x_j}.$$ The bit complexity of multiplication is $stackrel{~}{O}(b lg b)$, to multiply two $b$-bit integers (ignoring $lg lg b$ factors). The bit complexity for division (to $b$ bits of precision) is the same. Therefore, each iteration can be computed in $stackrel{~}{O}(n lg n)$ operations. Multiplying by $O(lg n)$ iterations, we find that the overall running time to compute the square root to $n$ bits of precision is $stackrel{~}{O}(n (lg n)^2)$. This is sub-quadratic. I think a more careful analysis shows that this can be improved to $stackrel{~}{O}(n lg n)$ running time (by taking into account that we only need to know each $x_j$ to within about $j$ bits of precision, rather than $n$ bits of precision). However, even the more basic analysis already shows a running time that is clearly subquadratic.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37596
