sqrt()函数，是绝大部分语言支持的常用函数，它实现的是开方运算；开方运算最早是在我国魏晋时数学家刘徽所著的《九章算术》被提及。今天写了几个函数加上国外大神的几个神级程序带大家领略sqrt的神奇之处。
1.古人算法（暴力法）
原理：从0开始0.00001,000002...一个一个试，直到找到x的平方根，代码如下：
public class APIsqrt {
static double baoliSqrt(double x) {
final double _JINGDU = 1e-6;
double i;
for (i = 0; Math.abs(x - i * i) > _JINGDU; i += _JINGDU)
;
return i;
}
public static void main(String[] args) {
double x = 3;
double root = baoliSqrt(x);
System.out.println(root);
}
}
测试结果：
1.7320509999476947
2.牛顿迭代法
计算机科班出身的童鞋可能首先会想到的是《数值分析》中的牛顿迭代法求平方根。原理是：随意选一个数比如说8，要求根号3，我们可以这么算：
(8 + 3/8) =4.1875
(4.1875 + 3/4.1875)
=2.4519
(2.4519
+ 3/2.4519) =1.837
(1.837+
3/1.837) =1.735
做了4步基本算出了近似值了，这种迭代的方式就是传说中的牛顿迭代法了，代码如下：
public class APIsqrt {
static double newtonSqrt(double x) {
if (x < 0) {
System.out.println("负数没事开什么方");
return -1;
}
if (x == 0)
return 0;
double _avg = x;
double last_avg = Double.MAX_VALUE;
final double _JINGDU = 1e-6;
while (Math.abs(_avg - last_avg) > _JINGDU) {
last_avg = _avg;
_avg = (_avg + x / _avg) / 2;
}
return _avg;
}
public static void main(String[] args) {
double x = 3;
double root = newtonSqrt(x);
System.out.println(root);
}
}
测试结果：
1.7320508075688772
3.暴力-牛顿综合法
原理：还是以根号3为例，先用暴力法讲根号3逼近到1.7，然后再利用上述的牛顿迭代法。虽然没有用牛顿迭代好，但是也为我们提供一种思路。代码如下：
public class APIsqrt {
static double baoliAndNewTonSqrt(double x) {
if (x < 0) {
System.out.println("负数没事开什么方");
return -1;
}
if (x == 0)
return 0;
double i = 0;
double _avg;
double last_avg = Double.MAX_VALUE;
for (i = 0; i*i < x; i += 0.1);
_avg = i;
final double _JINGDU = 1e-6;
while (Math.abs(_avg - last_avg) > _JINGDU) {
last_avg = _avg;
_avg = (_avg + x / _avg) / 2;
}
return _avg;
}
public static void main(String[] args) {
double x = 3;
double root = baoliAndNewTonSqrt(x);
System.out.println(root);
}
}
测试结果：
1.7320508075689423
4.二分开方法
原理：还是以3举例：
(0+3)/2 = 1.5, 1.5^2 = 2.25, 2.25 < 3;
(1.5+3)/2 = 2.25, 2.25^2 =5.0625, 5.0625 > 3;
(1.5+2.25)/2 = 1.875, 1.875^2 =3.515625;3.515625>3;
.
.
.
直到前后两次平均值只差小于自定义精度为止，代码如下：
public class APIsqrt {
static double erfenSqrt(double x) {
if (x < 0) {
System.out.println("负数没事开什么方");
return -1;
}
if (x == 0)
return 0;
final double _JINGDU = 1e-6;
double _low = 0;
double _high = x;
double _mid = Double.MAX_VALUE;
double last_mid = Double.MIN_VALUE;
while (Math.abs(_mid - last_mid) > _JINGDU) {
last_mid = _mid;
_mid = (_low + _high) / 2;
if (_mid * _mid > x)
_high = _mid;
if (_mid * _mid < x)
_low = _mid;
}
return _mid;
}
public static void main(String[] args) {
double x = 3;
double root = erfenSqrt(x);
System.out.println(root);
}
}
测试结果：
1.732051134109497
5.计算(int)(sqrt(x))算法
PS:此算法非博主所写
原理：空间换时间，细节请大家自行探究，代码如下：
public class APIsqrt2 {
final static int[] table = { 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53,
55, 57, 59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84,
86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104,
106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118, 119,
120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132,
133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144,
145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155,
156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166,
167, 167, 168, 169, 170, 170, 171, 172, 173, 173, 174, 175, 176,
176, 177, 178, 178, 179, 180, 181, 181, 182, 183, 183, 184, 185,
185, 186, 187, 187, 188, 189, 189, 190, 191, 192, 192, 193, 193,
194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201, 202,
203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210,
211, 211, 212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218,
218, 219, 219, 220, 221, 221, 222, 222, 223, 224, 224, 225, 225,
226, 226, 227, 227, 228, 229, 229, 230, 230, 231, 231, 232, 232,
233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238, 239, 240,
240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246,
247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253,
253, 254, 254, 255 };
/**
* A faster replacement for (int)(java.lang.Math.sqrt(x)). Completely
* accurate for x < 2147483648 (i.e. 2^31)...
*/
static int sqrt(int x) {
int xn;
if (x >= 0x10000) {
if (x >= 0x1000000) {
if (x >= 0x10000000) {
if (x >= 0x40000000) {
xn = table[x >> 24] << 8;
} else {
xn = table[x >> 22] << 7;
}
} else {
if (x >= 0x4000000) {
xn = table[x >> 20] << 6;
} else {
xn = table[x >> 18] << 5;
}
}
xn = (xn + 1 + (x / xn)) >> 1;
xn = (xn + 1 + (x / xn)) >> 1;
return ((xn * xn) > x) ? --xn : xn;
} else {
if (x >= 0x100000) {
if (x >= 0x400000) {
xn = table[x >> 16] << 4;
} else {
xn = table[x >> 14] << 3;
}
} else {
if (x >= 0x40000) {
xn = table[x >> 12] << 2;
} else {
xn = table[x >> 10] << 1;
}
}
xn = (xn + 1 + (x / xn)) >> 1;
return ((xn * xn) > x) ? --xn : xn;
}
} else {
if (x >= 0x100) {
if (x >= 0x1000) {
if (x >= 0x4000) {
xn = (table[x >> 8]) + 1;
} else {
xn = (table[x >> 6] >> 1) + 1;
}
} else {
if (x >= 0x400) {
xn = (table[x >> 4] >> 2) + 1;
} else {
xn = (table[x >> 2] >> 3) + 1;
}
}
return ((xn * xn) > x) ? --xn : xn;
} else {
if (x >= 0) {
return table[x] >> 4;
}
}
}
return -1;
}
public static void main(String[] args){
System.out.println(sqrt(65));
}
}测试结果：8
6.最快的sqrt算法
PS:此算法非博主所写
这个算法很有名，大家可能也见过，作者是开发游戏的，图形算法中经常用到sqrt，作者才写了一个神级算法，和他那神秘的0x5f3759df，代码如下
#include <math.h>
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
int main()
{
printf("%lf",1/InvSqrt(3));
return 0;
}
测试结果：
感兴趣的朋友可以参考http://wenku.baidu.com/view/a0174fa20029bd64783e2cc0.html
是作者解释这个算法的14页论文《Fast Inverse Square Root》
7.一个与算法6相似的算法
PS:此算法非博主所写
代码如下：
#include <math.h>
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
}
int main()
{
printf("%f",SquareRootFloat(3));
return 0;
}
测试结果：
==================================================================================================
作者：nash_ 欢迎转载，与人分享是进步的源泉！
转载请保留原文地址：http://blog.csdn.net/nash_/article/details/8217866
===================================================================================================
分享到：
相关推荐
FPGA\Verilog实现开方、平方、取余等数学算法，已经在硬件中实际验证过，计算没有问题，验证硬件是黑金的AX530
7.3.1 开平方算法 213 7.3.2 开平方示例 213 7.4 极值问题的求解算法 215 7.4.1 极值求解算法 215 7.4.2 极值求解示例 217 7.5 特殊函数的计算算法 221 7.5.1 伽玛函数 221 7.5.2 贝塔函数 224 7.5.3 正弦...
排序算法（平方排序算法的应用，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排 序，外部排序） 数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余...
11.1.1 用牛顿法开平方 243 11.1.2 二分查找 246 11.1.3 硬件算法 247 11.2 整数立方根 249 11.3 求整数幂 250 11.3.1 用n的二进制分解式计算xn 250 11.3.2 用Fortran语言计算2n 251 11.4 整数对数 252 ...
包含单一特征IntegerSquareRoot并为原始整数类型实现它。
jep,数学jep,数学最值有API帮助文档
8.3 迭代法开平方运算 8.4 牛顿法解方程 8.5 欧拉方法求解微分方程 8.6 改进的欧拉方法求解微分方程 8.7 雅可比迭代公式求解线性方程组 第9章 综合题 9.1 破碎的砝码 9.2 计算24的问题 9.3 马踏棋盘 9.4 0-1背包...
数学和算法拼图 简单的 找到 M 的第 N 个根 阶乘中的尾随零 重叠矩形 开门数 时针和分针之间的夹角 一周中的天 矩阵中的平方 中等的 Chrome 比赛 大批 简单的 中等的 股票买卖 查找缺失和重复 比赛 回溯 简单的 中等...
作品采用浮点算法，实现了7位数范围内的数学运算，整数、小数和负数皆可，并可以对正余弦函数，正切函数，开平方，反正余弦函数，反正切函数，对数函数，指数函数，平方和立方进行运算，如果有小数的话结果显示到四...
沃里克数学三年级作文项目 这将随机生成平面的正方形平铺。 当前，它会生成平面的非完美平方-每个正方形的大小不一定是唯一的。 当前，用户可以选择生成的唯一正方形的数量，范围为10-4000，但这是上限，因此，如果...
本书全面介绍了应用C语言进行开发的各种技术和技巧，全书共分12章，内容包括基础知识、指针、数据结构、算法、数学应用、文件操作、库函数应用、图形图像、系统调用、加解密与安全性、游戏、综合应用等。全书共提供...
下列是由固有数学函数派生的非固有数学函数： Secant（正割） Sec(X) = 1 / Cos(X) Cosecant（余割） Cosec(X) = 1 / Sin(X) Cotangent（余切） Cotan(X) = 1 / Tan(X) Inverse Sine（反正弦） Arcsin(X) = ...
0105 使用Sqr函数计算指定数的平方 70 0106 使用Mean函数计算平均数 70 0107 求最大浮点数和最小浮点数 71 4.3 序数函数 72 0108 使用Odd函数改变StringGrid组件的奇偶行颜色 72 0109 使用Pred函数获取...
0105 使用Sqr函数计算指定数的平方 70 0106 使用Mean函数计算平均数 70 0107 求最大浮点数和最小浮点数 71 4.3 序数函数 72 0108 使用Odd函数改变StringGrid组件的奇偶行颜色 72 0109 使用Pred函数获取...