计算平方根的算法非常多,wiki上有详细的解释:Methods_of_computing_square_roots。
本文使用C语言实现Bakhshali近似算法。
Bakhshali近似算法:
1 2 3 4 5 6 7 |
计算S的平方根: 第一步: 计算最最接近S的平方根(N) 第二步: 计算差值 d = S - (N^2) 第三步: 计算 P = d/(2*N) 第四步: 计算 A = N + P 第五步: S的平方根近似值等于 A - (P2/2*A) |
C代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <stdio.h> #include <math.h> float my_sqrt(float S) { int s = 0; int N = 0; for (int i = S; i > 0; i--) { for (int j = 1; j < i; j++) { if (j*j == i) { s = i; N = j; break; } } if (s > 0) break; } float d = S - s; float P = d/(2.0*N); float A = N+P; return A-((P*P)/(2.0*A)); } int main() { printf("%lf\n", my_sqrt(17.34)); // 4.164134 printf("%lf\n", sqrt(17.34)); // 4.164133 使用C库计算的值 return 0; } |
计算过程:
1 2 3 4 5 6 7 8 |
要计算sqrt(17.34) > s = 17.34 > N = 4 > d = 17.34 – (4^2) = 1.34 > P = 1.34/(2*4) = 0.1675 > A = 4 + 0.1675 = 4.1675 > sqrt(17.34) = 4.1675 – (0.1675*0.1675/(2*4.1675)) = 4.16413392322 |