Algorithm Sqrt for Double

By | 2012 年 12 月 16 日

The binary divide is straight forward solution, but some times slow.

The Newtown solution is better, but must careful for the mathematic detail. The equation is:
xk+1 = xk – (F(xk) / F'(xk) )

PS:slope(斜率), first derivative(一阶导数)



code

<

pre>
//
// main.cpp
// Sqrt
//
// Created by Qiu Xiangyu on 12-12-16.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include <math.h>

using namespace std;

//max error to guide the algorithms
const double _err = 0.000001;

//binary divide version
double mySqrtBinary(double num) {
if (num < 0) {
return NAN;
} else if (num == 0) {
return 0;
}
double sqmax = num > 1 ? num : 1.0;
double sqmin = num > 1 ? 1.0 : num;
double s = 0.5 * (sqmax + sqmin);
while (true) {
double ss = s * s;
if (fabs(ss – num) < _err) {
break;
}
if (ss > num) {
sqmax = s;
} else {
sqmin = s;
}
s = 0.5 * (sqmax + sqmin);
}
return s;
}

//newtown
double mySqrtNewtown(double num) {
if (num < 0) {
return NAN;
}
double s = num;
while (true) {
double ss = s * s;
double f0 = ss – num;
if (fabs(f0) < _err) {
break;
}
cout<<s<<endl;
s = s – f0 / (2.0 * s);
}
return s;
}

int main(int argc, const char * argv[])
{
// insert code here…
std::cout << mySqrtNewtown(0);
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注