JavaScript - Improving algorithm for finding square roots of perfect squares without Math.sqrt

Question

I'm trying to learn algorithms and coding stuff by scratch. I wrote a function that will find square roots of square numbers only, but I need to know how to improve its performance and possibly return square roots of non square numbers

function squareroot(number) {
    var number;
    for (var i = number; i >= 1; i--) {
        if (i * i === number) {
            number = i;
            break;
       }
   }
   return number;
}

 alert(squareroot(64))

Will return 8

Most importantly I need to know how to improve this performance. I don't really care about its limited functionality yet

Answer 1

Here is a small improvement I can suggest. First - start iterating from 0. Second - exit loop when the square of root candidate exceeds the number.

function squareroot(number) {
    for (var i = 0; i * i <= number; i++) {
        if (i * i === number)
            return i;
   }
   return number; // don't know if you should have this line in case nothing found
}

This algo will work in O(√number) time comparing to initial O(n) which is indeed performance improvement that you asked.

Edit #1

Just even more efficient solution would be to binary search the answer as @Spektre suggested. It is known that x² is increasing function.

function squareroot(number) {
    var lo = 0, hi = number;
    while(lo <= hi) {
         var mid = Math.floor((lo + hi) / 2);
         if(mid * mid > number) hi = mid - 1;
         else lo = mid + 1;
    }
    return hi;
}

This algo has O(log(number)) running time complexity.