# Can this recursive algorithm be converted to an iterative algorithm in O(1) space?

I am trying to convert this recursive algorithm

isqrt(n){

if(n==0){
return 0;
}
a = 2*isqrt(n/4)+1;
if(n<(a*a)){
return a-1;
} else {
return a;
}

}


into an iterative algorithm. So far I was able to do this:

isqrt(n){

vector c;
for(d = n; d>0; d = d/4){
c.push_back(d);
}
res = 0;
for(con = c.size(); con>0; con = con-1){
a = 2*res+1;
if(c[con-1]<(a*a)){
res = a-1;
} else {
res = a;
}
}
return res;

}


This could be a solution to my problem, but my approach was simply "simulating the function stack" inside the function itself with the vector, which works but still runs in O(floor(log4(n))) space, which in my use case is greatly undesirable. Is there any way to modify this algorithm in an iterative algorithm that runs in O(1) space? If possible the time complexity should remain the same.

• What is the algorithm trying to compute? Jun 29, 2021 at 15:57
• @nirshahar oeis.org/A000196 Jun 29, 2021 at 16:46
• – D.W.
Jun 30, 2021 at 21:27

Converting it into an iterative algorithm is somewhat vague and there could be many different ways to do it. One way could be the following:

isqrt(n){
if (n==0){
return 0;
}
a = 1;
b = a*a;
while (true){
if (n < b){
return a-1;
} else {
b += 2*a+1;
a += 1;
}
}
}


Other options can be applying Newton's algorithm.

There was the question in the comments about which number to use for the initial point in Newton's algorithm. One can use $$x_0=n//2$$. Any positive number will work.

There was also the question of ensuring logarithmic time complexity. Observe that in the set $$[n]=\{0,1,2,\ldots,n\}$$ the elements satisfying $$x^2\leq n$$ are all less than or equal to those satisfying $$x^2\geq n$$. The integer square root is the largest element of $$[n]$$ satisfying $$x^2\leq n$$. Therefore, we can find it using binary search.

isqrt(n){
if (n==1){
return n;
}
L = 0;
R = n//2;
while (L < R){
m = L + (R-L)//2;
s = m*m;
if (L == m){
if (s <= n){
return L;
} else {
return R;
}
}
if (s < n){
L = m;
} else if (s > m) {
R = m;
} else {
return m;
}
}
return L;
}

• By "Converting it into an iterative algorithm" I meant just deriving an equivalent algorithm that isn't recursive. Jul 1, 2021 at 0:29
• In practice my question boils down to: does an algorithm that does the same thing as my algorithm but isn't recursive, has costant space complexity and still runs in logaritmic time exists? If yes, what it is? Jul 1, 2021 at 0:44
• @ThePirate42 The reason why I say it is vague is because "equivalent algorithm" and "does the same" are still not precise. For example, the recursive algorithm needs to remember all the recursive calls. The answer to your question would be trivially no, if by "does the same" you mean an algorithm that carries the machine through the same sequence of states. Now, I guess you probably mean by "does the same" that the mathematical function defined by the algorithm is the same as the recursive one. In that case, the answer is yes and above and in the link there are examples of how to do it. Jul 1, 2021 at 0:55
• I guess you probably mean by "does the same" that the mathematical function defined by the algorithm is the same as the recursive one. Yes that was what I meant. I'm not sure the algorithm you posted here works in logarithmic time, but I had never heard of the Newton's algorithm so thank you. I'm a little confused about the "initial guess" requirement though. How am I supposed to get it? Does a "best way" to generate initial guesses exists? Jul 1, 2021 at 1:13
• @ThePirate42 The algorithm in my answer is only the naive search of the integer square root through the numbers $0,1,2,...,\lfloor \sqrt{n}\rfloor$. So, it always takes $\Omega(\sqrt{n})$ time. If you want to improve the time, note that in the set of numbers $0,1,...,n$ the ones satisfying $x^2\leq n$ are at all smaller than those satisfying $x^2\geq n$. Therefore, you can find the integer square root by doing binary search. Jul 1, 2021 at 13:05