08-27-2019, 06:32 PM
Hi All,
Most of us are familiar with the second order converging algorithm for obtaining the square root of N:
X(n+1) = (X(n) + N/X(n)) / 2
where X(0) is the initial guess for the square root of N.
I stumbled on a third order converging algorithm in an book about ODEs and PDEs. The algorithm is:
X(n+1) = X(n)*(X(n)^2 + 3*N)(3*X(n)^2 + N)
where X(0) is the initial guess for the square root of N.
I compared the two algorithms using Excel and the second one does converge faster than the first one.
The pseudo-code for the second algorithm is:
Given N and X (initial guess) and tolerance toler:
Enjoy!
Namir
Most of us are familiar with the second order converging algorithm for obtaining the square root of N:
X(n+1) = (X(n) + N/X(n)) / 2
where X(0) is the initial guess for the square root of N.
I stumbled on a third order converging algorithm in an book about ODEs and PDEs. The algorithm is:
X(n+1) = X(n)*(X(n)^2 + 3*N)(3*X(n)^2 + N)
where X(0) is the initial guess for the square root of N.
I compared the two algorithms using Excel and the second one does converge faster than the first one.
The pseudo-code for the second algorithm is:
Given N and X (initial guess) and tolerance toler:
Code:
Repeat
Y = X*X;
X = X * (Y + 3*N) / (3*Y + N)
Until Abs(X*X-N) <= toler
Enjoy!
Namir