einstein1969 wrote:The Sqrt(65535) return 256 and not 255. I have not checked other value.
I don't know if the problem is the number of iteration because:
The Newton method on integer sqrt is not stable.
Right, the Newton method (aka Heron of Alexandria method) is not stable in
N:
But it is not "too unstable".
The value x could trigger (only) between the solution sqrt(N) (==roundOff(sqrt(N)) in integral number systems) and the successor of the solution (sqrt(N)+1):
If N=x*x => x==sqrt(N), and no trigger possible.
If N<x*x => x > N/x, more iterations required, but no trigger possible.
If N>x* => trigger possible between roundOff(sqrt(N)) and (roundOff(sqrt(N))+1);
because of the iteration step in this case the following is true when triggering:
- roundOff(sqrt(N)) < sqrt(N) < roundOff(sqrt(N))+1,
- roundOff(sqrt(N)) == N/(roundOff(sqrt(N))+1), and
- roundOff(sqrt(N)+1) == N/roundOff(sqrt(N)).
So in your algorithm (using int calculus) you could test if (N-x*x) is greater than or equal to 0;
if this is true then sqrt(N)=x, else sqrt(N)=x-1.
This value could be computed using set /A (but the max value is a trap; possible: x*x>maxInt):
Code: Select all
set /a "x+=((N-((x-1)*(x-1)+(x+x-1)))>>31)"
So the whole code should be:
Code: Select all
@echo off
setlocal enableDelayedExpansion
set "Sqrt(N)=( x=(N)/(11*1024)+40-^!(N)*9, x=((N)/x+x)/2, x=((N)/x+x)/2, x=((N)/x+x)/2, x=((N)/x+x)/2, x=((N)/x+x)/2, x+=(((N)-((x-1)*(x-1)+(x+x-1)))>>31))/(1+((N)>>31))"
for %%s in (-2147483647, -1, 0, 1, 4, 9, 16, 25, 35, 48 65535, 65536, 65537, 131072, 262144, 393216, 2147395600, 2147483647) do (
(
2>nul set /A "num=!Sqrt(N):N=%%~s!"
) && (
echo Square root of %%~s is : !num!
) || (
setlocal enableDelayedExpansion
set /A "num=!Sqrt(N):N=-%%~s!"
echo Square root of %%~s is !num!i ^(not in R^).
endlocal
)
)
endlocal
goto :eof
Note:
I have not tested, if this algorithm computes always the correct result.
Some values within [0:2^31-1] may need more iterations.
Because of the starting value the number of iterations is not monotonically increasing anymore
(if i remember right then the original algorithm (initial x=N) needs a maximum of 19 iterations).
But you should check this using c++/java/similar... batch is much too slow to check all numbers within [0:2^32-1];
my pc would take >300 days, but it isn't the fastest... .
penpen
