0
$\begingroup$

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.

$\endgroup$
3

1 Answer 1

1
$\begingroup$

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;
}
$\endgroup$
5
  • $\begingroup$ By "Converting it into an iterative algorithm" I meant just deriving an equivalent algorithm that isn't recursive. $\endgroup$ Jul 1, 2021 at 0:29
  • $\begingroup$ 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? $\endgroup$ Jul 1, 2021 at 0:44
  • $\begingroup$ @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. $\endgroup$
    – Urtur
    Jul 1, 2021 at 0:55
  • $\begingroup$ 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? $\endgroup$ Jul 1, 2021 at 1:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – Urtur
    Jul 1, 2021 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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