Math.sqrt()的更快替代方案

Question

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

例如:

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

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

Answer 1

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

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

1. 近似多项式

   通常使用泰勒级数、切比雪夫等展开式，并且热数的数量取决于目标精度。并非所有数学函数都可以这样计算。

2. 迭代近似

   很少有像牛顿法、巴比伦法等方法通常收敛得足够快，因此不需要使用太多的热值。我打赌你sqrt使用牛顿近似。

   还有基于二分搜索的计算

   • 负指数的幂

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

   • 如何仅在一个时钟周期内获得 32 位输入的平方根？

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

   • 近似搜索的工作原理

3. 代数地使用log2,exp2

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

   • Math.Pow（等等）实际上是如何工作的

4. 查找表

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

5. 混合方法

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

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

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

另外，有关更多信息，请查看相关的质量检查：

• 平方根函数是如何实现的？

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

例如，如果您想做：

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

您可以将其重写为：

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

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

Answer 2

您可以确定,如果不是更好,您将编写自己的最快算法已在Math.sqrt中实现.

有一种算法可以通过数字直到中间(有一些简单的计算):编写自己的平方根函数

但正如我所说,如果不是更好,它可能会实施.

您可以尝试查找某些特定的业务/域逻辑,以减少数字范围.