从整数和余数中找到浮点数的平方根？

Question

4

我正在查看一种特定的算法来计算平方根，该算法返回平方根的整数部分和余数。

例如：mysqrt(140) = 11 * 11 + 19 = 整数11，余数19

问题是我能否计算浮点数的平方根，例如140的平方根约为11.8321...？

编辑来自评论

我正在查看一个固定点平方根的VHDL实现，该实现仅使用左/右移位、加法和减法等二进制操作。

...这个算法就足够了。

编辑2 我实际上正在阅读此处的算法：http://pioneer.netserv.chula.ac.th/~achatcha/Publications/0012.pdf 似乎通过将被开方数左移2n可以获得更好的精度。我不太确定为什么会起作用？能有人解释一下吗？

- mark mcgehee

我已经修复了一个看起来像是笔误的问题（将remainder 9改为19）。 - NPE

这基本上相当于编写自己的平方根实现。 - outis

编程语言还是算法？ - ChrisBD

@ChrisBD，算法就可以了。 - mark mcgehee

当然可以，但是你限制自己使用哪些操作呢？可能你不想使用完整的sqrt运算符。有一些算法使用估计和余数来计算平方根。http://www.homeschoolmath.net/teaching/square-root-algorithm.php 就是其中之一。 - Chris

谢谢@Chris，我会看一下的。目前我正在寻找的算法（用于找到整数和余数）只使用二进制操作，如左/右移、加减等。 - mark mcgehee

3个回答

1

回复：

似乎通过将被开方数左移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) 只返回一个整数。

- Chris

感谢 @Chris 的精彩解释！我希望我能够接受你的答案和 Ishtar 的答案。 - mark mcgehee

0

我不确定我理解你的问题。你想知道如何在浮点数中使用sqrt函数，还是想自己编写一个函数？

如果是前者，那么你的语言会提供一些东西（可能叫做sqrt()）。如果是后者，那么你需要查阅某种数值资源。我建议使用GSL： http://www.gnu.org/software/gsl/

- invisiblerhino

不用了，我知道怎么用 :) 我没有使用已经实现的系统 sqrt，而是另一个算法，它返回数字的整数部分和余数（参见示例） - mark mcgehee

那么如果int part = 11，余数为19，它的浮点数等价物是多少？ - invisiblerhino

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ishtar · Accepted Answer

(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

要解决这个问题，您需要再做一个平方根运算：

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

你可以重复应用这个方法来得到更好的近似值，但是使用牛顿迭代法可能更快速。