5

有没有其他方法可以Math.sqrt()用来获得未知值的平方根？

例如：

var random  = (Math.random() * (999 - 1)) + 1;
var sqrt = Math.sqrt(random);

我听说使用Math.sqrt()得到一个数字的平方根是一个非常慢的操作，我只是想知道是否有更快的方法可以得到一个随机数的平方根。对此的任何帮助将不胜感激。

4

7 回答 7

11

你可以确定你自己编写的最快算法已经在 Math.sqrt 中实现了，如果不是更好的话。

有一种算法可以遍历数字直到中间（通过一些简单的计算）：编写自己的平方根函数

但正如我所说，如果不是更好的话，它可能已经实现了。

您可以尝试寻找一些特定的业务/领域逻辑以减少数字范围。

于 2017-01-01T09:35:12.627 回答
8

不知道您sqrt是如何实现的（不是 javascript 编码器），所以我只能推测更快的方法，但是对于IEEE 754float/double格式以及integers例如在Quake3中使用“幻数”的快速方法很少。这在定义的时间间隔上只需要很少的操作就或多或少地精确，并且很可能比你的 sqrt 更快，但只能在特定的时间间隔内使用。

通常sqrt的实现是通过以下方式完成的：

  1. 近似多项式

    通常使用 Taylor 级数、Chebyshev 等展开式，而 therms 的数量取决于目标精度。并非所有数学函数都可以这样计算。

  2. 迭代逼近

    很少有像 Newton、Babylonian等方法通常收敛得足够快，所以不需要使用太多的 therms。我敢打赌你sqrt使用牛顿近似。

    还有基于二进制搜索的计算

    二进制搜索需要相同的迭代次数，然后使用数字结果的位数，这通常比上述近似方法中使用的热量多。但是对 sqrt 的二分搜索有一个巨大的优势，那就是它可以在没有乘法的情况下完成（这对于 bignums 很重要......）

    还有其他搜索近似值，例如：

  3. 代数使用log2,exp2

    你可以直接计算，pow所以看看log2,exp2sqrt(x)=pow(x,0.5)

  4. 查找表

    您可以将分段插值与预先计算的查找表一起使用。

  5. 混合方法

    您可以将更多方法组合在一起，例如将估计结果与低精度近似多项式结合起来，然后使用二进制搜索在它周围搜索（仅几位）......但这仅对“大”数（以位的方式）有意义......

  6. 一些数学运算和常数可以用 PCA 计算

    但我认为在你的情况下使用它没有意义......

此外，有关更多信息，请查看相关的QA：

不知道你在计算什么，但最快sqrt的是你根本不计算它。许多计算和算法可以重写，因此它们根本不需要使用sqrt或至少不需要经常使用（例如比较距离^2 等......）。

例如，如果你想做：

x = Random();
y = sqrt(x);

您可以将其重写为：

y= Random();
x = y*y;

但要注意随机性属性不一样！！！

于 2017-01-01T11:08:51.297 回答
1

正如您在计数中看到的那样，您的分配sqrt不相等。为了获得相同的分布，您需要一个改变分布的因素。该因子取决于随机数。没有捷径可走。

function getRandom() {
    return Math.sqrt((Math.random() * (999 - 1)) + 1);
}

var i, r,
    o = {};

for (i = 0; i < 32; i++) {
    o[i] = 0;
}

for (i = 0; i < 100000; i++) {
    o[Math.floor(getRandom())]++;
}

console.log(o);
.as-console-wrapper { max-height: 100% !important; top: 0; }

于 2017-01-01T10:10:51.917 回答
1

在 JS 中有另一种方法可以计算平方根。

const m = 0x5F375A86,
  // Creating the buffer and view outside the function
  // for performance, but this is not thread safe like so:
  buffer = new ArrayBuffer(4),
  view = new DataView(buffer)
  function fastInvSqrt (n) {
    var f, n2 = n * 0.5, th = 1.5
    view.setFloat32(0, n)
    view.setUint32(0, m - (view.getUint32(0) >> 1))
    f = view.getFloat32(0)
    f *= (th - (n2 * f * f))
    f *= (th - (n2 * f * f))
  return f
}

// Test execution time
let start = Date.now()
for (let i = 0; i < 1000000; i++) {
  fastInvSqrt(i**2)
}
console.log('fastInvSqrt', Date.now() - start, 'millieconds')

// compare with Math.sqrt
start = Date.now()
for (let i = 0; i < 1000000; i++) {
  Math.sqrt(i**2)
}
console.log('Math.sqrt', Date.now() - start, 'millieconds')

这是在 Quake III 游戏中发现并最初使用的！

于 2021-08-30T22:37:12.997 回答
1

如果您拥有的代码与您正在使用的代码相同，则根本不需要平方根

var random  = (Math.random() * (999 - 1)) + 1;
var sqrt = Math.sqrt(random);

可能

var sqrt  = (Math.random() * ( 31.6069612586)) + 1;
var random  = sqrt * sqrt ;

乘法比 sqrt 快得多，所以代码应该类似

请注意，可以像上面一样预先计算 998 的平方根，使其成为一次性操作，而不是每次运行

于 2017-01-01T11:19:41.773 回答
1

我认为您无法获得比内置预编译代码更快的速度，但对于您在下面的信息，您可以找到有关如何使用纯 JS 获得数字平方根的算法。

它非常快，但由于它是递归的，它很可能会比它的迭代版本慢一些。迭代实现取决于您。

var sqrt = (n, u = n, d = n-1 ? n/u : 1) => n ? (u === (u+d)/2) && (d === n/u) ? d : sqrt(n,(u+d)/2, n/u) : 0,
       s = 0;
console.time("sqrt");
var s = sqrt(9876543210*9876543210);
console.timeEnd("sqrt");
console.log(s);

console.time("sqrt");
var s = sqrt(98765.4321*98765.4321);
console.timeEnd("sqrt");
console.log(s);

它采用巴比伦的方法。

于 2017-01-01T22:44:27.360 回答
0

数学规定：

var sqrt = Math.sqrt(random);

相当于：

var sqrt = random**.5;

可能不会更快，但肯定更短。

于 2019-11-07T04:41:11.337 回答