Hàm căn bậc hai không dùng Math.sqrt() trong JavaScript

Mô tả bài toán

Tính căn bậc hai của số dương không dùng Math.sqrt(), sử dụng thuật toán tìm kiếm nhị phân (binary search).

Ví dụ minh họa

const square = (n, i, j) => {
  let mid = (i + j) / 2;
  let mul = mid * mid;
  if ((mul === n) || (Math.abs(mul - n) < 0.00001)) {
    return mid;
  } else if (mul < n) {
    return square(n, mid, j);
  } else {
    return square(n, i, mid);
  }
};

const findSqrt = num => {
  let i = 1;
  while (true) {
    if (i * i === num) return i;
    else if (i * i > num) {
      return square(num, i - 1, i);
    }
    i++;
  }
};

console.log(findSqrt(33));

Kết quả

5.744562149047852

Giải thích thuật toán

1. Tìm số nguyên i nhỏ nhất sao cho i² > n
2. Căn bậc hai nằm trong khoảng (i-1, i)
3. Áp dụng binary search trong khoảng đó với độ chính xác 0.00001

Cách khác: Newton-Raphson

const sqrt = n => {
  let x = n;
  while (true) {
    const root = 0.5 * (x + n / x);
    if (Math.abs(root - x) < 1e-10) return root;
    x = root;
  }
};