确定浮点平方根

Question

如何确定浮点数的平方根？Newton-Raphson方法是一种好方法吗？我也没有硬件平方根.我也没有硬件鸿沟(但我实现了浮点除法).

如果可能的话,我宁愿尽可能减少分歧的数量,因为它们太贵了.

另外,应该是初始猜测减少迭代总数???

非常感谢!

Answer 1

当你使用Newton-Raphson计算平方根时,你实际上想要使用迭代来找到倒数平方根(在此之后你可以简单地乘以输入 - 稍微考虑舍入 - 来产生平方根).

更确切地说:我们使用该功能f(x) = x^-2 - n.显然,如果f(x) = 0,那么x = 1/sqrt(n).这产生了牛顿迭代:

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)

注意(与平方根的迭代不同),这个倒数平方根的迭代不涉及任何划分,因此它通常更有效.

我在你关于鸿沟的问题中提到过,你应该看看现有的软浮动库,而不是重新发明轮子.这个建议也适用于此.此功能已在现有的软浮动库中实现.

编辑:提问者似乎仍然感到困惑,所以让我们举个例子:sqrt(612). 612是1.1953125 x 2^9(或者b1.0011001 x 2^9,如果你喜欢二进制).拉出指数(9)的偶数部分以将输入写为f * 2^(2m),其中m是整数,f并且在[1,4]的范围内.然后我们将:

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

将此缩减应用于我们的示例给出f = 1.1953125 * 2 = 2.390625(b10.011001)和m = 4.现在做一个newton-raphson迭代来找到x = 1/sqrt(f),使用0.5的开始猜测(正如我在评论中所指出的,这个猜测会收敛所有f,但你可以使用线性近似作为初始猜测明显更好):

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/sqrt(f) = 0.6467616600226026.

现在我们简单地汇总最终结果:

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

并检查:sqrt(612)= 24.738633 ...

显然,如果要进行正确的舍入,需要仔细分析以确保在计算的每个阶段都具有足够的精度.这需要仔细记账,但这不是火箭科学.您只需保持谨慎的错误界限并通过算法传播它们.

如果要在不明确检查残差的情况下纠正舍入,则需要将sqrt(f)计算为2p + 2位的精度(其中p是源和目标类型的精度).但是,您也可以采用计算sqrt(f)的策略略大于p位,将该值平方,并在必要时将尾随位调整为1(通常更便宜).

sqrt很不错,因为它是一个一元函数,可以对商用硬件上的单精度进行详尽的测试.

你可以sqrtf在opensource.apple.com上找到OS X soft-float 函数,它使用上面描述的算法(我写的,它发生了).它是根据APSL许可的,可能适合或不适合您的需求.