J'essaie d'apprendre des algorithmes et de coder des trucs par zéro. J'ai écrit une fonction qui ne trouvera que les racines carrées des nombres carrés, mais j'ai besoin de savoir comment améliorer ses performances et éventuellement retourner les racines carrées des nombres non carrés

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

 alert(squareroot(64))

Reviendra 8

Plus important encore, j'ai besoin de savoir comment améliorer ces performances. Je ne me soucie pas encore vraiment de ses fonctionnalités limitées

1
user5680735 8 mars 2016 à 01:54

5 réponses

Meilleure réponse

Voici une petite amélioration que je peux suggérer. Premièrement - commencez l'itération à partir de 0. Seconde - quittez la boucle lorsque le carré du candidat racine dépasse le 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
}

Cet algo fonctionnera en O (√nombre) en comparaison avec le O (n) initial qui est en effet une amélioration des performances que vous avez demandée.

Modifier # 1

2

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

Cet algo présente une O (log (nombre)) complexité de la durée d'exécution.

3
Ivan Gritsenko 8 mars 2016 à 09:41
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;
}

Cela retournera la racine carrée en trouvant à plusieurs reprises la moyenne.

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

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

0
Matthias Southwick 29 avril 2019 à 19:20

La recherche binaire fonctionnera mieux.

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;
}
0
Divyanshu Rawat 8 sept. 2018 à 20:31

Les choses que vous essayez de faire s'appellent des méthodes numériques. La méthode numérique la plus rudimentaire / facile pour la résolution d'équations (oui, vous résolvez une équation x ^ 2 = a ici) est une Méthode Newtons.

Il vous suffit d'itérer cette équation:

enter image description here

Dans votre cas f(x) = x^2 - a et donc f'(x) = 2x.

Cela vous permettra de trouver une racine carrée de n'importe quel nombre avec n'importe quelle précision. Il n'est pas difficile d'ajouter une étape qui rapproche la solution d'un entier et vérifie si sol^2 == a

3
Salvador Dali 7 mars 2016 à 23:27

Sépare la méthode de Newton de la fonction à approximer. Peut être utilisé pour trouver d'autres racines.

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))
0
Jeremy Azzari 14 oct. 2017 à 04:14