patternMinor
Compute square root using (bit) additions and shifts as primitives
Viewed 0 times
additionsbitcomputeshiftsprimitivesusingrootsquareand
Problem
Question: Given an $n$-bit natural number $N$, how to compute $\lceil \sqrt{N} \rceil$ using only $O(n)$ (bit) additions and shifts?
The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$).
What does it mean by
This is an exercise in an algorithm book.
In my opinion, it means that adding two, say $n$-bit, natural numbers costs $O(1)$ and shifting a, say $n$-bit, natural number also costs $O(1)$. Then we are only allowed to use such $O(1)$ operations $O(n)$ times.
It does not mention the cost of comparison. I guess we can ignore it or assume that comparing two, say $n$-bit, natural numbers costs $O(1)$ as well.
My $O(n^2)$ algorithm:
$$2^{\frac{n-1}{2}} \le \sqrt{N} \le 2^{\frac{n}{2}} \Rightarrow 2^{\lfloor \frac{n-1}{2} \rfloor} \le \lceil \sqrt{N} \rceil \le 2^{\lceil \frac{n}{2} \rceil}$$
Therefore,
$$t_1 \triangleq \lfloor \frac{n-1}{2} \rfloor + 1 \le t \le \lceil \frac{n}{2} \rceil + 1 \triangleq t_2.$$
Find $\lceil \sqrt{N} \rceil$ between $2^{t_1}$ and $2^{t_2}$ using binary search. For each number $x$, to compute $x^2$ using additions and shifts as primitives and compare it with $N$.
The complexity is thus $O(n \times n) = O(n^2)$ for $O(n)$ times of binary search and computing $x^2$, each of which in turn takes $O(n)$ additions and shifts.
The tip is to use binary search. However, I could not achieve the required complexity (I got $O(n^2)$).
What does it mean by
using only $O(n)$ (bit) additions and shifts:This is an exercise in an algorithm book.
In my opinion, it means that adding two, say $n$-bit, natural numbers costs $O(1)$ and shifting a, say $n$-bit, natural number also costs $O(1)$. Then we are only allowed to use such $O(1)$ operations $O(n)$ times.
It does not mention the cost of comparison. I guess we can ignore it or assume that comparing two, say $n$-bit, natural numbers costs $O(1)$ as well.
My $O(n^2)$ algorithm:
- Determine the range of the number of bits $t$ of $\lceil \sqrt{N} \rceil$:
$$2^{\frac{n-1}{2}} \le \sqrt{N} \le 2^{\frac{n}{2}} \Rightarrow 2^{\lfloor \frac{n-1}{2} \rfloor} \le \lceil \sqrt{N} \rceil \le 2^{\lceil \frac{n}{2} \rceil}$$
Therefore,
$$t_1 \triangleq \lfloor \frac{n-1}{2} \rfloor + 1 \le t \le \lceil \frac{n}{2} \rceil + 1 \triangleq t_2.$$
- Binary search:
Find $\lceil \sqrt{N} \rceil$ between $2^{t_1}$ and $2^{t_2}$ using binary search. For each number $x$, to compute $x^2$ using additions and shifts as primitives and compare it with $N$.
The complexity is thus $O(n \times n) = O(n^2)$ for $O(n)$ times of binary search and computing $x^2$, each of which in turn takes $O(n)$ additions and shifts.
Solution
An iterative algorithm seems like it should work.
Let $M=\lfloor N/4 \rfloor$. Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously).
Now we want to find $y=\lceil \sqrt{N} \rceil$. What are the possible values of $y$? I'm pretty sure the only possible values are $y=2x$ or $y=2x+1$. And, it's easy to try both of them and see which is correct. In particular, for $y=2x$, we have $y^2=4x^2$, which can be obtained from $x^2$ by two left-shifts ($O(1)$ time); for $y=2x+1$, we have $y^2=4x^2+4x+1$, which can be obtained from $x^2$ and $x$ with four left-shifts and two additions ($O(1)$ time). Now just compare those two values to $N$ to see which one is correct.
In this way, we get an iterative algorithm where we do $n/2$ iterations, and where each iteration takes $O(1)$ time. The total running time is $O(n)$, as required.
I realize this didn't use binary search. Oh well.
Let $M=\lfloor N/4 \rfloor$. Suppose we know that $x$ is the integer approximation to $\sqrt{M}$, i.e., $x=\lceil \sqrt{M} \rceil$, and suppose we know the value of $x^2$ (obtained previously).
Now we want to find $y=\lceil \sqrt{N} \rceil$. What are the possible values of $y$? I'm pretty sure the only possible values are $y=2x$ or $y=2x+1$. And, it's easy to try both of them and see which is correct. In particular, for $y=2x$, we have $y^2=4x^2$, which can be obtained from $x^2$ by two left-shifts ($O(1)$ time); for $y=2x+1$, we have $y^2=4x^2+4x+1$, which can be obtained from $x^2$ and $x$ with four left-shifts and two additions ($O(1)$ time). Now just compare those two values to $N$ to see which one is correct.
In this way, we get an iterative algorithm where we do $n/2$ iterations, and where each iteration takes $O(1)$ time. The total running time is $O(n)$, as required.
I realize this didn't use binary search. Oh well.
Context
StackExchange Computer Science Q#30334, answer score: 7
Revisions (0)
No revisions yet.