4

我现在正在研究计算平方根的特定算法,它返回平方根的整数部分和余数。

例如:mysqrt(140) = 11*11 + 19 = integer 11, remainder 19

问题是我可以将平方根计算为浮点数,例如 140 的平方根是 ~ 11.8321 ....?

从评论编辑

我正在研究一个定点平方根的 VHDL 实现,它只使用像左/右移位、加法和减法这样的二进制操作。

...算法就足够了。

编辑 2我实际上在这里阅读这个算法:http: //pioneer.netserv.chula.ac.th/~achatcha/Publications/0012.pdf

似乎可以通过将radicand左移2n来获得更好的精度。我不太确定为什么这有效?谁能解释一下

4

3 回答 3

4
(11+x)^2 = 140
11^2 + 2*11*x + x^2 = 140
2*11*x + x^2 = 19
x^2 + 2*11*x - 19 = 0

为了解决这个问题,你需要做另一个 sqrt:

x = -11 + sqrt((2*11)^2 + 4 * 19) / 2

或者对于最终答案:

11+x = sqrt((2*11)^2 + 4 * 19) / 2

这并不比做更快

sqrt(140)

如果您正在寻找快速近似值:

x^2 + 2*11*x - 19 = 0
x = (19 - x^2)/(2*11)

猜测 x = 0.5,给出

x = 19/(2*11) - 0.5*0.5/(2*11) = 0.852272727

您可以反复应用它以获得更好的近似值,但牛顿的方法可能更快。

于 2012-01-17T12:26:33.027 回答
1

回应:

似乎可以通过将radicand左移2n来获得更好的精度。我不太确定为什么这有效?谁能解释一下

您链接的论文谈到了左移 2n。它起作用的原因是因为您有效地移动了 4 的倍数,这很容易计入平方根。

sqrt(K*2^2n) = sqrt(K)*sqrt(2^2n) = sqrt(K)*2^n

所以你只需向后移动 n 位,你就会得到正确的答案。如果您将这些移位的位保留为小数部分,那么您将得到分数答案。

以十进制形式考虑,在平方根之前乘以 100,之后除以 10。

所以

sqrt(2) = sqrt(200)/10 = 14/10 = 1.4

其中 sqrt(200) 只给出一个整数。

于 2012-01-17T13:53:10.860 回答
0

我不确定我是否理解你的问题。您想知道如何在浮点数上使用 sqrt 函数,或者如何编写自己的函数吗?

如果是前者,那么您的语言将提供一些东西(可能称为 sqrt())。如果是后者,那么您需要查找某种数字资源。我会推荐 GSL: http ://www.gnu.org/software/gsl/

于 2012-01-17T12:18:28.287 回答