巴比伦的aka-Heron方法似乎是寻找n的平方根的快速算法之一。它的收敛速度取决于你最初猜测的距离。
现在,随着数字n的增加,根x的百分比减少。
根(10):10-31%
10:100-10%
根部(100):100-3%
根(1000):1000-1%
基本上每个数字除以3。那就用它作为你的最初猜测。例如-
public static double root(double n ) {
//If number is 0 or negative return the number
if(n<=0)
return n ;
//call to a method to find number of digits
int num = numDigits(n) ;
double guess = n ;
//Divide by 0.3 for every digit from second digit onwards
for (int i = 0 ; i < num-1 ; ++i )
guess = guess * 0.3;
//Repeat until it converges to within margin of error
while (!(n-(guess*guess) <= 0.000001 && n-(guess*guess) >= 0 )) {
double divide = n/guess ;
guess = Math.abs(0.5*(divide+guess)) ;
}
return Math.abs(guess) ;
}
这是否有助于优化算法这是O(n)吗?
最佳答案
对。更有效的方法是利用浮点表示法,通过将二进制指数除以2,因为在浮点位上操作非常快。见Optimized low-accuracy approximation to `rootn(x, n)`。