博客

最近同事参加面试，被问及如何实现x开y次方，第一个想法就是pow函数。细思考虑，面试官应该意图是如何实现pow函数。

先从最简单的开平方考虑：

被开方数如果是1 4 9 16 等这些数，int 上遍历还有意义 ，但是如果类似5 或者double类型，那又该如何做呢？

1 二分法 

#include <iostream>
#define PRECISION_THRESHOLD 0.0000001
double my_sqrt(double num){
    double result = num/2.0;
    double temp = result * result;
    double pre_low= 0;
    double pre_high = num>1?num:1 ;//避免纯小数  纯小数的开方大于其本身
    while((temp>= (num+PRECISION_THRESHOLD)) || (temp <= (num - PRECISION_THRESHOLD))){
        if(temp<num){
            pre_low = result;
            result = (result+pre_high)/2.0;
        }else if (temp > num){
            pre_high = result;
            result = (result+pre_low)/2.0;
        } else
            break;
        temp = result*result;
    }
    return result;
}
int main(){
    double data = my_sqrt(0.4);
    std::cout<<"data " << data<<std::endl;
    return 0;
}

其中因为是double类型，无法完全相等（5 开方后平方一直在5 附近 比如4.999998 5.000001 然而无法等于5 陷入死循环）所以要设置一个阈值。设置阈值的话又会影响到0.01的开方，在这种情况下结果为 data 0.0999997

2 高斯牛顿法

可得 在Y=X^2时 Y = Xo^2 +2*Xo（X-Xo）  可得 X =( Y+Xo^2)/Xo  并且可知X=Xo时 等式成立 故循环迭代直到 X=Xo

#include <iostream>
#include <cmath>
#define PRECISION_THRESHOLD 0.0000001
double my_sqrt_newton(double num){
    double X = num;
    double pre_X =  num/2.0;
    while(fabs(X-pre_X)> PRECISION_THRESHOLD){
        pre_X = X;
        X = (num + pre_X*pre_X)/(2*pre_X);
    }
    return X;
}
int main(){
    double result = my_sqrt_newton(0.01);
    std::cout<<"result " << result<<std::endl;

    return 0;
}

3 雷神之锤算法

看的也是一脸懵逼

float InvSqrt (float x){
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    y = *(float*)&i;
    y = y*(1.5f - xhalf*x*x);
    return x;
}

详情看 http://www.matrix67.com/data/InvSqrt.pdf，神器的数字

部分参考https://blog.csdn.net/xusiwei1236/article/details/25657611