您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

手算平方根的JavaScript实现

今天偶然了解到了一种手算平方根的方法。其流程如下:

  1. 用二分查找确定整数部分。若发现是完全平方数,则直接返回。
  2. 设之前已求出的整数部分和小数部分一起,不断乘10直到它是一个整数,为a,比如:之前已经求出11.45,那么a=1145。设要求的下一位是b,则:根据100 * v = (10a+b)^2 = 100*a*a+20*a*b+b*b(实际上这个公式就是手算法的原理,v为待求根号的数,v = a + 0.1*b)有:
  3. 设上一轮得到的差值为delta,则初始的delta = v - intPart * intPartintPart为整数部分。用本轮的a和b表示,则delta = 100*v-100*a*a = (10a+b)^2-100*a*a,所以我们只需要求出最大的b,使得delta >= 20*a*b+b*b。在此为了实现简单,直接遍历0~9了。

它相比于牛顿迭代等没有计算速度上的优势,牛顿迭代在此问题是平方收敛,它的速度就慢太多了。但如果只使用通常的double,牛顿迭代无法获得极其高的精度(比如小数点后114514位)。而这个手算的算法在使用BigInt的情况下可以达到任意精度。

代码
"use strict";
//node 开根号.js
//若v是完全平方数,则返回整数,否则返回want位小数
function mySqrt(v,want) {
  let l = 1, r = v
  while (l < r - 1) {
    let mid = (l + r) >> 1
    if (mid * mid > v) r = mid - 1
    else l = mid
  }
  const intPart = r * r <= v ? r : l
  let delta = v - intPart * intPart
  if (!delta) return intPart
  let tmp = intPart
  let ans = []
  for (let i = 1; i <= want; ++i) {
    let val = 9
    for (let j = 0; j < 10; ++j) {
      if (20 * tmp * j + j * j > 100 * delta) {
        val = j - 1
        break
      }
    }
    ans.push(val)
    delta = 100 * delta - (20 * tmp * val + val * val)
    tmp = 10 * tmp + val
    // console.log(delta, tmp)//因为tmp会越来越大,所以delta大体上也会越来越大
  }
  return `${intPart}.${ans.join('')}`
}

//1.4142135623730 41 1.7320508075688 5.0990195135927
//2.2360679774997 2.4494897427831 2.6457513110645 338.3991725758
console.log(mySqrt(2,13))
console.log(mySqrt(1681,13))
console.log(mySqrt(3,13))
console.log(mySqrt(26,13))
console.log(mySqrt(5,13))
console.log(mySqrt(6,13))
console.log(mySqrt(7,13))
console.log(mySqrt(114514,10))

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进