确定浮点平方根 [英] Determining Floating Point Square Root

问题描述

我如何确定一个浮点数的平方根？是对牛顿迭代法的好办法？我没有硬件平方根无论是。我也没有硬件除法器（但我已经实现浮点除法）。

How do I determine the square root of a floating point number? Is the Newton-Raphson method a good way? I have no hardware square root either. I also have no hardware divide (but I have implemented floating point divide).

如果可能的话，我会preFER减少除法的数量尽可能因为它们是如此昂贵。

If possible, I would prefer to reduce the number of divides as much as possible since they are so expensive.

此外，应该是什么初始猜测，以减少迭代的总数???

Also, what should be the initial guess to reduce the total number of iterations???

感谢你了！

推荐答案

在使用牛顿迭代计算平方根，你真的想使用迭代找到的倒数平方根（之后就可以简单地乘以由输入 - 与一些护理四舍五入 - 产生的平方根）

When you use Newton-Raphson to compute a square-root, you actually want to use the iteration to find the reciprocal square root (after which you can simply multiply by the input--with some care for rounding--to produce the square root).

更多precisely：我们使用功能 F（X）= X ^ -2 - N 。显然，如果 F（X）= 0 ，然后 X = 1 / SQRT（N）。这就产生了牛顿迭代：

More precisely: we use the function f(x) = x^-2 - n. Clearly, if f(x) = 0, then x = 1/sqrt(n). This gives rise to the newton iteration:

x_(i+1) = x_i - f(x_i)/f'(x_i)
        = x_i - (x_i^-2 - n)/(-2x_i^-3)
        = x_i + (x_i - nx_i^3)/2
        = x_i*(3/2 - 1/2 nx_i^2)

需要注意的是（迭代的平方根不同），这个迭代平方根倒数不涉及部门，因此它一般是更有效的。

Note that (unlike the iteration for the square root), this iteration for the reciprocal square root involves no divisions, so it is generally much more efficient.

我在你的问题中提到的鸿沟，你应该看一下现有的软浮点库，而不是重新发明轮子。这个建议在这里也适用。这个功能已经在现有的软浮点库中实现。

I mentioned in your question on divide that you should look at existing soft-float libraries, rather than re-inventing the wheel. That advice applies here as well. This function has already been implemented in existing soft-float libraries.

编辑：提问者似乎仍然被混淆，所以让我们举​​一个例子：的sqrt（612）。 612 是 1.1953125×2 ^ 9 （或 b1.0011001×2 ^ 9 ，如果preFER二进制）。拉出指数（9）的偶数部分写的输入为 F * 2 ^（2M），其中 M 是一个整数， F 的范围是[1,4）。然后，我们将有：

the questioner seems to still be confused, so let's work an example: sqrt(612). 612 is 1.1953125 x 2^9 (or b1.0011001 x 2^9, if you prefer binary). Pull out the even portion of the exponent (9) to write the input as f * 2^(2m), where m is an integer and f is in the range [1,4). Then we will have:

sqrt(n) = sqrt(f * 2^2m) = sqrt(f)*2^m

将本次减持我们的例子给出了 F = 1.1953125 * 2 = 2.390625 （ b10.011001 ）和 M = 4 。现在做一个牛顿迭代迭代找到 X = 1 /开方（F），使用0.5起始的猜测（正如我在评论指出，这个猜测收敛所有 F ，但可以使用线性近似作为一个初始猜测）做显著更好的：

applying this reduction to our example gives f = 1.1953125 * 2 = 2.390625 (b10.011001) and m = 4. Now do a newton-raphson iteration to find x = 1/sqrt(f), using a starting guess of 0.5 (as I noted in a comment, this guess converges for all f, but you can do significantly better using a linear approximation as an initial guess):

x_0 = 0.5
x_1 = x_0*(3/2 - 1/2 * 2.390625 * x_0^2)
    = 0.6005859...
x_2 = x_1*(3/2 - 1/2 * 2.390625 * x_1^2)
    = 0.6419342...
x_3 = 0.6467077...
x_4 = 0.6467616...

因此​​，即使一个（相对较差）初始猜测，我们得到快速收敛到真实值 1 /开方（F）= 0.6467616600226026 。

现在我们只是组装的最终结果：

Now we simply assemble the final result:

sqrt(f) = x_n * f = 1.5461646...
sqrt(n) = sqrt(f) * 2^m = 24.738633...

和检查：SQRT（612）= 24.738633 ...

And check: sqrt(612) = 24.738633...

显然，如果你要正确舍入，需要确保您随身携带足够的precision在计算的各个阶段仔细的分析。这需要仔细记账，但它不是火箭科学。您只需保持谨慎误差范围，并通过算法将它们传播。

Obviously, if you want correct rounding, careful analysis needed to ensure that you carry sufficient precision at each stage of the computation. This requires careful bookkeeping, but it isn't rocket science. You simply keep careful error bounds and propagate them through the algorithm.

如果你想纠正四舍五入没有明确检查的剩余，你需要计算的sqrt（F）的2P + 2位的precision（其中p是源和目标类型的precision）。不过，您也可以把计算的sqrt（六）多一点P位的策略，正方形的价值，并在必要时由一个调整尾随位（这往往是便宜）。

If you want to correct rounding without explicitly checking a residual, you need to compute sqrt(f) to a precision of 2p + 2 bits (where p is precision of the source and destination type). However, you can also take the strategy of computing sqrt(f) to a little more than p bits, square that value, and adjust the trailing bit by one if necessary (which is often cheaper).

开方是很好的，因为它是一个一元函数，这使得详尽的​​测试单precision在商用硬件上是可行的。

sqrt is nice in that it is a unary function, which makes exhaustive testing for single-precision feasible on commodity hardware.

您可以找到OS X软浮动 sqrtf 函数opensource.apple.com，它使用上述算法（我写的，因为它发生）。这是APSL，这可能是不适合你的需要进行授权。

You can find the OS X soft-float sqrtf function on opensource.apple.com, which uses the algorithm described above (I wrote it, as it happens). It is licensed under the APSL, which may or not be suitable for your needs.

这篇关于确定浮点平方根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！