2

我设法让我的 sqrt 函数完美运行，但我第二次猜测我是否根据给定的伪代码正确编写了这段代码。

这是伪代码：

x = 1
repeat 10 times:  x = (x + n / x) / 2
return x.

我写的代码，

#include <iostream> 
#include <math.h> 
using namespace std; 

double my_sqrt_1(double n) 
{
double x= 1; x<10; ++x;
return (x+n/x)/2; 
}
4

3 回答 3

7

不，您的代码没有遵循您的伪代码。例如，您不会在代码中重复任何内容。您需要添加一个循环来执行此操作：

#include <iostream> 
#include <math.h> 
using namespace std; 

double my_sqrt_1(double n) 
{
  double x = 1;
  for(int i = 0; i < 10; ++i) // repeat 10 times
    x = (x+n/x)/2;
  return x; 
}

让我们分析一下您的代码：

double x = 1;
// Ok, x set to 1


x < 10; 
// This is true, as 1 is less than 10, but it is not used anywhere

++x;
// Increment x - now x == 2

return (x + n / x) / 2 
// return value is always (2 + n / 2) / 2

由于您没有任何循环，因此函数将始终在第一次“迭代”中退出并返回 value (2 + n / 2) / 2。

于 2013-09-17T22:48:27.193 回答
3

正如您可以使用二进制搜索的另一种方法或另一种非常优雅的解决方案一样，使用牛顿法。

牛顿法是一种利用函数导数求函数根的方法。在每一步，一个值被计算为：x(step) = x(step-1) - f(x(step-1))/f'(x(step-1)) Newton's_method

这可能比二进制搜索更快。我在 C++ 中的实现：

double NewtonMethod(double x) {
        double eps = 0.0001; //the precision 
        double x0 = 10;
        while( fabs(x-x0) > eps) {
            double a = x0*x0-n;
            double r = a/(2*x0);
            x = x0 - r;
            x0 = x;
        }
        return x;
    }
于 2013-09-17T23:01:27.643 回答
1

由于人们展示了计算平方根的不同方法，我无法抗拒;)...

下面是逆平方根实现的精确副本（带有原始注释，但没有预处理器指令）Quake III Arena：

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );               // what the...?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}
于 2013-09-17T23:16:19.030 回答