Square root manually in Javascript

Question

I’m trying to manually calculate square root in Javascript.

Theoretically it was to stop at 100 according to the value that is in the variable number, but it continues to multiply.

Code sample:

var numero = 100;
var contador = 0;
var i;
var num1 = 0;
var num2 = 0;
do {
for (i = 0; i < numero; i++) {
  contador++
  num1++
  num2++
  
  var multi = num1 * num2;
  var resultado = multi * multi / multi;
  console.log(multi);
} 
} while (resultado < 100) {

}


console.log(contador);

Answer 1

There is a fast square root approach through a linear equation:

L(x) = f(a) + f'(a)*(x-a)

For a given value a where the function has a known value and f'(_) being the derivative of the function. By coincidence, the derivative of the square root is half the inverse of the square root.

The square root value is fully known in perfect squares, so let’s treat a as a perfect square, and f(a) its entire root.

So the approximation formula can be transformed like this:

                                    (x-a)
sqrt_approx(x) = sqrt_int(a) +  -------------
                                2*sqrt_int(a)

For the approach to work, I need to choose a a close enough to x.

So our algorithm now boils down to:

1. find a perfect square (and its entire root sqrt_int(a)) closest to x
2. apply the formula

Roughly speaking, that would be:

function sqrt_approx(x) {
  let sqrt_a = raiz_do_quadrado_mais_proximo(x);
  let a = sqrt_a * sqrt_a;

  // se x for um quadrado perfeito, x-a resultará em zero e a resposta será sqrt_a
  return sqrt_a + (x-a)/(2*sqrt_a);
}

Great, now we just need to define who is the closest square to x. Since we’re dealing with real numbers, it doesn’t make sense to investigate negative number roots, so I’m going to reduce the search set to positive ones only. The idea is very simple: from 0 to infinity, checking the distance from the square of the iteration variable to the x. At the moment there is an inflection (ie, the distance ceases to be negative and becomes positive), return either the current element of the iteration or the previous element, according to the square closest to x:

function raiz_do_quadrado_mais_proximo(x) {
  let i = 0;
  while (true) {
    let ii = i * i;
    if (ii - x > 0) {
      let dist_ii = x - ii;
      let dist_ant = x - (i-1)*(i-1);
      if (dist_ii < 0) {
        dist_ii *= -1;
      }
      if (dist_ant < 0) {
        dist_ant *= -1;
      }

      return dist_ant < dist_ii? i-1: i;
    }
  }
}

The above code can be trivially optimized for:

function raiz_do_quadrado_mais_proximo(x) {
  let i = 0;
  while (i*i < x) { // itera até a inflexão
    i++;
  }
  let dist_ii = i*i - x; // i*i >= x garantido, depois da inflexão, daí dist_ii está sendo calculado já positivo
  let dist_ant = x - (i-1)*(i-1); // antes da inflexão, x será maior que o quadrado, daí dist_ant está sendo calculado já positivo

  return dist_ant < dist_ii? i-1: i;
}

Put it all together, we got:

function faz_leitura(form) {
  let x = Number(document.getElementById("quad").value);
  let raiz_apprx = sqrt_approx(x);
  let err = x - (raiz_apprx * raiz_apprx);
  if (err < 0) {
    err = -err;
  }
  
  document.write("<div>Raiz quadrada aproimada de " + x + " é " + raiz_apprx + ", com erro de " + err + "</div>");
}

function raiz_do_quadrado_mais_proximo(x) {
  let i = 0;
  while (i*i < x) {
    i++;
  }
  let dist_ii = i*i - x;
  let dist_ant = x - (i-1)*(i-1);

  return dist_ant < dist_ii? i-1: i;
}

function sqrt_approx(x) {
  let sqrt_a = raiz_do_quadrado_mais_proximo(x);
  let a = sqrt_a * sqrt_a;

  // se x for um quadrado perfeito, x-a resultará em zero e a resposta será sqrt_a
  return sqrt_a + (x-a)/(2*sqrt_a);
}

<form onsubmit="faz_leitura(this); return false;">
<div>
  <input required type="text" id="quad"/>
  <label>valor a ser calculada a raiz</label>
</div>

<button type="submit">SQRT</button>
</form>

Answer 2

This code is too complex and confusing and this gives room to create several errors. Your algorithm doesn’t compute the square root of any number, but I imagine you only want the ones that can be computed as integers, at least that’s what you’ve already done. It’s not the most optimized way to do this but it’s much simpler.

What do you have to do to find the entire square root? Go dividing the number by a divisor, and then it goes up this divisor until it reaches the desired value, but the new divisor needs the average of the divided value and the divisor itself, in this way in addition to being more performatic by avoids too many the Solar , but achieves better approximations. This algorithm may not be the most accurate in all scenarios, but it depends on the requirement, at least it works.

var numero = 101;
var divisor = 1, dividido = 0;
for (var  i = 0; i < numero; i++) {
    dividido = numero / divisor;
    divisor = (dividido + divisor) / 2;
}
console.log(divisor);

I put in the Github for future reference.

I used 101 to show that it works with broken numbers. Its algorithm did not work.

Answer 3

This way I did, you decrease the number of code variables and can see the multi and counter values in the console:

var numero = 100;   
var resultado = 0;

for (var i = 0; i < numero; i++) {
  var multi = i * i;
  resultado = multi * multi / multi;
  console.log(`${i}° de multi: ${multi}`);
} 

console.log("Valor do Contador: ", i); 

Answer 4

Here I ran and it stopped at 100 normally. Usually when I’m having doubt on the size of the loop, I put some counting print to see how it works:

var numero = 100;
var contador = 0;
var i;
var num1 = 0;
var num2 = 0;
do {
for (i = 0; i < numero; i++) {
  contador++
  num1++
  num2++
  
  var multi = num1 * num2;
  var resultado = (multi * multi) / multi;
  console.log("contador:" + contador + " - resultado: " + resultado);
} 
} while (resultado < 100) {

}


console.log(contador);

Answer 5

If you need me, I have a function for that:

function calculoRaiz(numero) {

   var divisorRaiz = 1, calcDiv = 0;
   for (var i = 0; i <= numero; i++) {
       calcDiv = numero / divisorRaiz;
       divisorRaiz = (calcDiv + divisorRaiz) / 2;
   }
   return divisorRaiz;
}

calculoRaiz(100);