智能车制作

标题: 迭代法求平方根 [打印本页]

---

作者: rubick    时间: 2014-3-5 03:30
标题: 迭代法求平方根


用迭代，按下面这个公式进行迭代即可求出a的平方根：
Xn=(Xn-1+a/Xn-1)/2 (n>0)
其中X0可以随便取一个数。当Xn-Xn-1满足精度要求时，即可输出Xn作为答案。原文：一种有趣地理解：
http://www.physixfan.com/archives/76
回复中有任意次方根的方法公式。

标准的牛顿迭代法：
http://www.matrix67.com/blog/archives/361
目前已知的最快的方法：quake III 源代码
http://www.matrix67.com/blog/archives/362
干脆附带源代码吧：

1. float InvSqrt(float x)
   
2. {
   
3.         float xhalf = 0.5f*x;
   
4.         int i = *(int*)&x; // get bits for floating value
   
5.         i = 0x5f3759df - (i>>1); // gives initial guess y0
   
6.         x = *(float*)&i; // convert bits back to float
   
7.         x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
   
8.         return x;
   
9. }

复制代码

迭代初始值（魔幻数）0x5f3759df 可以看论文：
http://www.matrix67.com/data/InvSqrt.pdf

---

作者: rubick    时间: 2014-3-5 03:48
用 quake III 的话，要小心咯！涉及到浮点数据的存储方式。
还是推荐用简单的形式吧。
简单形式迭代了5次就已经非常精确了，
quake III 更牛逼，每迭代一次提高两位有效数字。

---

作者: 简单丹    时间: 2014-3-5 08:33
              1

---

作者: zhou1994    时间: 2014-3-5 12:27
看看，学习一下

---

作者: 银影のK.I.D    时间: 2014-3-5 12:50
get

---

作者: Quixote    时间: 2014-8-16 21:16
MARK

---

欢迎光临 智能车制作 (http://dns.znczz.com/)

Powered by Discuz! X3.2