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

user_5680735 0
Viewed 11856

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

square-root algorithm javascript
8 Answers
function squareRoot(n){
    var avg=(a,b)=>(a+b)/2,c=5,b;
    for(let i=0;i<20;i++){
        b=n/c;
        c=avg(b,c);
    }
    return c;
}

This will return the square root by repeatedly finding the average.

var result1 = squareRoot(25) //5
var result2 = squareRoot(100) //10
var result3 = squareRoot(15) //3.872983346207417

JSFiddle: https://jsfiddle.net/L5bytmoz/12/

user_102958530

Here is the solution using newton's iterative method - 

/**
 * @param {number} x
 * @return {number}
 */
// newstons method
var mySqrt = function(x) {
    if(x==0 || x == 1) return x;

    let ans, absX = Math.abs(x);
    let tolerance = 0.00001;
    while(true){
        ans = (x+absX/x)/2;
        if(Math.abs(x-ans) < tolerance) break;
        x = ans;
    }
    return ans;
};
user_3638670

Separates Newton's method from the function to approximate. Can be used to find other roots.

function newton(f, fPrime, tolerance) {
  var x, first;

  return function iterate(n) {
    if (!first) { x = n; first = 1; }

    var fn = f(x);

    var deltaX = fn(n) / fPrime(n);
    if (deltaX > tolerance) {
      return iterate(n - deltaX)
    }

    first = 0;
    return n;
  }
}


function f(n) { 
  return  function(x) { 
    if(n < 0) throw n + ' is outside the domain of sqrt()';
    return x*x - n;
  };
}

function fPrime(x) {
  return 2*x;
}


var sqrt = newton(f, fPrime, .00000001)
console.log(sqrt(2))
console.log(sqrt(9))
console.log(sqrt(64))
user_14245050

Binary search will work best.

let number = 29;
let res = 0;

console.log((square_root_binary(number)));
function square_root_binary(number){

    if (number == 0 || number == 1)  
       return number;

    let start = 0;
    let end = number;


    while(start <= end){

        let mid = ( start + end ) / 2;

        mid = Math.floor(mid);

        if(mid * mid == number){
            return mid;
        }

        if(mid * mid < number){
            start = mid + 1;
            res = mid;
        }
        else{
            end = mid - 1;
        }
    }

    return res;
}
user_57636270

I see this solution on Github which is the much better and easiest approach to take a square root of a number without using any external library

function TakingPerfectSquare(Num) {
   for (var i = 0; i <= Num; i++) {
      var element = i;
      if ((element == element) && (element*element == Num)) {
         return true;
      }
   }
   return false;
}
console.log(TakingPerfectSquare(25));
user_132280080

If you analyze all natural numbers with their squares you might spot a pattern...

Numbers   Squares   Additives
   1         1          3
   2         4          5
   3         9          7
   4        16          9
   5        25         11
   6        36         13
   7        49         15

Look at the first row in the squares column (i.e 1) and add it with the first row in the additives column (ie. 3). You will get four which is in the second row of the squares column.

If you keep repeating this you'll see that this applies to all squares of natural numbers. Now if you look at the additives column, all the numbers below are actually odd.

To find the square root of a perfect square you should keep on subtracting it with consecutive odd numbers (starting from one) until it is zero. The number of times it could be subtracted is the square root of that number.

This is my solution in typescript...

function findSquareRoot(number: number): number {
  for (let i = 1, count = 0; true; number -= i, i += 2, count++) {
    if (number <= 0) {
      return number === 0 ? count : -1; // -1 if number is not a perfect square
    }
  }
}

Hopefully this has better time complexity :)

Admin1
Related