`
yarin
  • 浏览: 174650 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

用牛顿迭代法求浮点数的平方根

阅读更多

版权申明:http://yarin.iteye.com/blog/453262

先说个例子:

比如我们要求a的平方根,首先随便猜一个近似值x,然后不断令x等于x和a/x的平均数,迭代几次后x的值就已经相当精确了。

看下面(假设a=2,我们求2的平方根):

1.先随便猜个数,比如我猜2的平方根为7

( 7  + 2/7 ) / 2 = 3.64287514
( 3.64287514  + 2/3.64287514 ) / 2 = 2.095946017

......

......

( n+ 2/n) / 2 = 1.414....

 

下面是代码:

#define ABS(VAL) (((VAL)>0)?(VAL):(-(VAL))) //用牛顿迭代法求浮点数的平方根 float mysqrt(float x) { float g0,g1; if(x==0) return 0; g0=x/2; g1=(g0+x/g0)/2; while(ABS(g1-g0)>0.01) { g0=g1; g1=(g0+(x/g0))/2; } return g1; }


 

好的,就写到这里了!谢谢支持! 

 

 

 

 

 

 

 

 

分享到:
评论
10 楼 krzycube 2009-07-21  
Trustno1 写道
恩,其实如果做tuning做久了会遇到许多奇怪的magic number比如说,6755399441055744.0,
0x55555555,0x33333333之类的.



哈哈
inline void RoundToInt64 (int &val, double dval)
{
  static double magic = 6755399441055744.0;
  dval += magic;
  val = *(int*)&dval;
}

9 楼 Trustno1 2009-07-21  
恩,其实如果做tuning做久了会遇到许多奇怪的magic number比如说,6755399441055744.0,
0x55555555,0x33333333之类的.

8 楼 night_stalker 2009-07-15  
说白了就是一个收敛比较快的展开式 ……
7 楼 icefishc 2009-07-15  
mikeandmore 写道
icefishc 写道
补充
http://en.wikipedia.org/wiki/Fast_inverse_square_root

John Carmack 不是一般的强悍...

啊,传说中的那个神奇的常数?


嗯 就是那个.
6 楼 mikeandmore 2009-07-14  
icefishc 写道
补充
http://en.wikipedia.org/wiki/Fast_inverse_square_root

John Carmack 不是一般的强悍...

啊,传说中的那个神奇的常数?
5 楼 icefishc 2009-07-14  
补充
http://en.wikipedia.org/wiki/Fast_inverse_square_root

John Carmack 不是一般的强悍...
4 楼 ray_linn 2009-07-14  
quake iii
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;
  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;        // 浮点数按BIT强行赋给长整形
  i  = 0x5f3759df - ( i >> 1 ); // 没天理!!!!!
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 第1次叠代
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 第2次叠代,可以删除
  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}
3 楼 kimmking 2009-06-29  
一般函数的求根,无外乎
1,弦线法,
2,切线法,
3,1+2综合

其实都是迭代,起始值最好估计下,否则可能不收敛(迭代的混沌现象)

随便找个《数值分析》或是《计算方法》的书看看,都可以找到估值和加速迭代因子的算法
2 楼 mikeandmore 2009-06-27  
fivestarwy 写道
有个游戏引擎中的开方算法比库函数快好多倍,好像也是用牛顿迭代,不过忘了是哪个游戏了。

quake 3吧。。。比libm里面快了4倍吧。。。
1 楼 fivestarwy 2009-06-27  
有个游戏引擎中的开方算法比库函数快好多倍,好像也是用牛顿迭代,不过忘了是哪个游戏了。

相关推荐

    javascript基于牛顿迭代法实现求浮点数的平方根【递归原理】

    牛顿迭代法在求解浮点数的平方根问题上,表现出优异的性能和较高的精确度。 在JavaScript中实现牛顿迭代法求平方根的原理相对简单,基本步骤包括: 1. 选择一个初始的近似值x(在求平方根时,可以选a/2作为初始值)...

    北邮数值与符号计算实验 方程求根的牛顿迭代法

    1.double my_sqrt(double c);求平方根 。 假设浮点数在计算机中按IEEE标准表示。而c是一个整的规格化浮点数。令 为c的尾数。使用如下的牛顿迭代格式: 请详细论证p,q的选取,实得仅使用三次迭代...使用牛顿迭代法求

    浮点数开方.rar

    浮点数开方的过程可以分为多种算法,其中一种常见的是牛顿迭代法。牛顿法是一种寻找函数零点的迭代方法,可以用于求解平方根。具体步骤如下: 1. 选择一个初始近似值x0,通常是被开方数的一半。 2. 在每一步迭代中,...

    牛顿插值法解根号 vs2008 c#

    在进行根号计算时,通常会用到牛顿迭代法,它是一种寻找方程零点的迭代方法。对于方程f(x) = 0,牛顿迭代法的迭代公式是: x_{k+1} = x_k - f(x_k) / f'(x_k) 在这个场景中,f(x) = sqrt(x) - a,a是你希望求解的...

    Fast inverse square root平方根倒数速算法.zip_平方根倒数速算法_逆平方根速算法

    它的原理基于牛顿迭代法,用于寻找一个数的平方根的倒数。牛顿迭代法是一种优化算法,通过不断逼近目标函数的根来求解问题。对于求解1/x√(x),可以将迭代公式表示为: x_n+1 = x_n - (x_n * (x_n * x) - 1) / (2 *...

    易语言求高精度平方根

    总的来说,易语言求高精度平方根涉及的主要知识点包括高精度算法、牛顿迭代法、易语言的语法和数据类型,以及自定义数据结构的使用。通过学习和理解这些内容,你可以编写出自己的高精度平方根计算程序。

    汇编语言求平方根的问题

    因此,在80386汇编语言中实现求平方根通常需要采用数值计算方法,如牛顿迭代法或二分查找法。 牛顿迭代法是一种快速收敛的数值近似方法,其基本思想是通过不断迭代接近目标值。在汇编语言中,可以设置一个初始猜测...

    快速求平方根(英文)

    3. **牛顿迭代法**: 使用牛顿迭代法来进一步提高结果的准确性。该方法利用了一阶泰勒展开式来逼近`1/sqrt(x)`,并根据初始猜测进行迭代,以提高结果的精确度。 #### 三、算法改进 - **初始猜测优化**: 可以尝试...

    平方根的倒数速算

    平方根倒数速算法的实现需要使用到浮点数的位级操作和牛顿迭代法,以获取平方根倒数的近似值。该算法的代码实现如下所示: float Q_rsqrt( float number ){ long i; float x2, y; const float threehalfs = 1.5F; ...

    梦幻平方根详解

    `:使用牛顿迭代法进一步修正结果,使其更加精确。这里应用了牛顿迭代公式\( y_{n+1} = y_n - \frac{f(y_n)}{f'(y_n)} \)来求解\( f(x) = x^2 - a = 0 \)的根,其中\( a = \frac{1}{x} \)。 #### 数学原理 1. **...

    c语言编程题之数学问题x的平方根.zip

    然而,如果你想要自定义一个计算平方根的函数,或者在没有math.h库的情况下工作,你可以使用迭代法或牛顿法。迭代法是一种通过不断逼近目标值的方法,而牛顿法则是迭代法的一种特殊形式,用于求解方程的根。 以下是...

    快速平方根算法

    为了解决这一问题,John Carmack 在 Quake III 中引入了一种快速计算平方根倒数的方法,这种方法基于牛顿迭代法(Newton-Raphson Method),并通过一些巧妙的设计实现了极高的效率。 #### 二、牛顿迭代法与泰勒级数...

    F4求平方根程序.rar

    平方根函数的实现通常有多种方法,比如牛顿迭代法、二分查找法或者查表法。在这个特定程序中,开发者可能采用了其中一种或几种。牛顿迭代法是一种快速收敛的迭代算法,通过不断逼近目标值来计算平方根。二分查找法则...

    快速平方根倒数,双语版

    总结来说,快速平方根倒数算法是一种在软件开发中广泛应用的数学近似技巧,它通过位操作和牛顿迭代法来实现高速的平方根倒数计算。这个算法不仅在技术上具有突破性,而且在实用性上也非常强大,尤其适用于那些对计算...

    数值分析大作业

    本次大作业的主题是"开平方的两种算法",即牛顿迭代法和二分法。这两种方法都是解决非线性方程求根问题的有效手段,特别适用于求解平方根。 首先,我们来探讨牛顿迭代法。牛顿迭代法是一种迭代优化算法,通过不断...

    基于牛顿-拉夫森迭代算法的开方程序设计.docx

    总结来说,这个基于牛顿-拉夫森迭代算法的开方程序设计实例展示了如何利用迭代法在C语言环境中高效地计算平方根,同时考虑了数值计算中的精度控制和硬件限制。通过这样的程序,我们可以学习到数值计算的基本方法,...

    cpp代码-求一个正整数的平方根

    以下是一个使用牛顿迭代法求平方根的C++代码示例: ```cpp #include // 自定义求平方根函数 double customSqrt(int num) { double x = num; // 初始猜测值,这里设为输入数本身 double epsilon = 1e-9; // 定义...

    易语言求高精度平方根源码

    2. **平方根算法**:使用牛顿迭代法(Newton-Raphson method)来求解高精度平方根。初始值可以设置为被开方数的一半,然后不断迭代,每次迭代的公式为 `x_{n+1} = (x_n + y/x_n) / 2`,其中 `x_n` 是当前迭代值,`y`...

Global site tag (gtag.js) - Google Analytics