JavaScript - 改进算法，用于在没有Math.sqrt的情况下查找完美正方形的平方根

Question

我正在尝试从头开始学习算法和编码。我写了一个函数，它只能找到平方数的平方根，但我需要知道如何提高它的性能并可能返回非平方数的平方根

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

 alert(squareroot(64))

将返回8

最重要的是，我需要知道如何改善这种性能。我真的不关心其有限的功能

Answer 1

这是我可以建议的一个小改进。首先 - 从0开始迭代。当根候选的平方超过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
}

与最初的O（n）相比，这个算法将在O（√number）时间内工作，这确实是你提出的性能改进。

编辑＃1

更有效的解决方案是按照@Spektre的建议二进制搜索答案。众所周知，x2正在增加功能。

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;
}

该算法具有O（log（number））运行时复杂度。

Answer 2

你尝试做的事情叫做numerical methods。方程求解的最基本/简单的数值方法（是的，你在这里求解方程x ^ 2 = a）是Newtons method。

你要做的就是迭代这个等式：

在你的情况下f(x) = x^2 - a，因此f'(x) = 2x。

这将允许您以任何精度查找任何数字的平方根。添加一个将解近似于整数的步骤并验证是否sol^2 == a并不难

Answer 3

将牛顿方法从函数分离为近似。可以用来寻找其他根源。

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))

Answer 4

二进制搜索最有效。

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;
}

Answer 5

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;
}

这将通过重复找到平均值来返回平方根。

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

的jsfiddle：https://jsfiddle.net/L5bytmoz/12/