平方根函数是如何实现的?

平方根函数是如何实现的?

来源于此 。

问题陈述:给定x> 0,findy使得y ^ 2 = x => y = x / y(这是关键步骤)。

1)猜测y的一些值g并testing它。
2)计算x / g。
3)如果x / g足够接近g,则返回g。 否则,请尝试更好的猜测。

double test(double x, double g) { if closeEnough(x/g, g) return g; else return test(x, betterGuess(x, g)); } boolean closeEnough(double a, double b) { return (Math.abs(a - b) < .001); } double betterGuess(double x, double g) { return ((g + x/g) / 2); } 

在这里输入图像说明

在英特尔硬件上,通常是在硬件SQRT指令的基础上实现的。 一些图书馆只是使用这个结果,有些可能会通过几轮牛顿优化,使其在angular落案件更准确。

有很多方法来计算平方根。 维基百科也具有伪计算机algorithm的细节。 你正在寻找在特定的图书馆或具体精度的实施?

使用二进制search与C + +的简单实现

 double root(double n){ double lo = 0, hi = n, mid; for(int i = 0 ; i < 1000 ; i++){ mid = (lo+hi)/2; if(mid*mid == n) return mid; if(mid*mid > n){ hi = mid; }else{ lo = mid; } } return mid; } 

请注意while循环是最常见的二进制search,但个人而言,我更喜欢for处理十进制数时,它节省了一些特殊情况下处理,并得到相当准确的结果从小循环,如1000甚至500 (两者会给出相同的结果几乎所有的数字,但只是为了安全)

FDLIBM(可自由分发的LIBM)有一个相当不错的文档版本的sqrt。 e_sqrt.c 。

有一个版本使用整数运算和recursion公式一次修改一位。

另一种方法使用牛顿的方法。 它从一些黑魔法和一个查找表开始,得到前8位,然后应用递推公式

  y_{i+1} = 1/2 * ( y_i + x / y_i) 

其中x是我们开始的数字。 这是Heron方法的巴比伦方法。 它可以追溯到公元一世纪的亚历山德拉英雄。

还有另一种方法叫做快速倒数平方根或者倒数。 它使用一些“恶意浮点比特级黑客”来find1 / sqrt(x)的值。 i = 0x5f3759df - ( i >> 1 ); 它利用mantisse和exponent来利用float的二进制表示。 如果我们的数字x是(1 + m)* 2 ^ e,其中m是尾数,e是指数,结果y = 1 / sqrt(x)=(1 + n)* 2 ^ f。 以日志

 lg(y) = - 1/2 lg(x) f + lg(1+n) = -1/2 e - 1/2 lg(1+m) 

所以我们看到结果的指数部分是数的指数的-1/2。 黑魔法基本上对指数进行按位移,并在尾数上使用线性近似。

一旦你有了一个好的第一个近似值,你可以使用牛顿的方法来获得更好的结果,最后一些级别的工作来修复最后一个数字。

计算平方根(不使用内置math.sqrt函数):

SquareRootFunction.java

 public class SquareRootFunction { public double squareRoot(double value,int decimalPoints) { int firstPart=0; /*calculating the integer part*/ while(square(firstPart)<value) { firstPart++; } if(square(firstPart)==value) return firstPart; firstPart--; /*calculating the decimal values*/ double precisionVal=0.1; double[] decimalValues=new double[decimalPoints]; double secondPart=0; for(int i=0;i<decimalPoints;i++) { while(square(firstPart+secondPart+decimalValues[i])<value) { decimalValues[i]+=precisionVal; } if(square(firstPart+secondPart+decimalValues[i])==value) { return (firstPart+secondPart+decimalValues[i]); } decimalValues[i]-=precisionVal; secondPart+=decimalValues[i]; precisionVal*=0.1; } return(firstPart+secondPart); } public double square(double val) { return val*val; } } 

MainApp.java

 import java.util.Scanner; public class MainApp { public static void main(String[] args) { double number; double result; int decimalPoints; Scanner in = new Scanner(System.in); SquareRootFunction sqrt=new SquareRootFunction(); System.out.println("Enter the number\n"); number=in.nextFloat(); System.out.println("Enter the decimal points\n"); decimalPoints=in.nextInt(); result=sqrt.squareRoot(number,decimalPoints); System.out.println("The square root value is "+ result); in.close(); } } 

SQRT(); function在幕后。

它总是检查图中的中点。 例如:sqrt(16)= 4; SQRT(4)= 2;

现在,如果你给任何input16或4像sqrt(10)==?

它find2和4的中点,即= x,然后再找出x和4的中点(它不包括在这个input中的下界)。 它重复这个步骤一次又一次,直到它得到完美的答案,即sqrt(10)== 3.16227766017。它位于B / W 2和4.所有这个内置函数是使用微积分,微分和积分创build的。