penpen wrote:. . .

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

Well, that is not really neccessary... The problems with these

*iterative*methods appears at the limits of a range of results. For example, the Sqrt from 25 to 35 is 5, so it is enough to test the method with 25 and 35 to know that all values in this range will return the same result. This way, the test should be done on the square of a number and this value minus one for all numbers from 2 up to Sqrt(2^31-1), that is 46340. I wrote the program below to perform this test over both methods:

Code: Select all

`@echo off`

setlocal EnableDelayedExpansion

for /F %%a in ('copy /Z "%~F0" NUL') do set "CR=%%a"

rem Aacini's method:

set "Sqrt1(Num)=set /A "M=(Num),sqrt=M/(11*1024)+40,sqrt=(M/sqrt+sqrt)/2"&(for /L %%i in (1,1,5) do set /A "x2=(M/sqrt+sqrt)/2"^&if ^!x2^! leq ^!sqrt^! set /A sqrt=x2)"

echo Aacini start @ %time%

< NUL (for /L %%n in (2,1,46340) do (

set /P "=%%n!CR!"

set /A "Num2=%%n*%%n, Num2M1=Num2-1, NM1=%%n-1"

%Sqrt1(Num):Num=Num2M1%

if !sqrt! neq !NM1! echo Aacini failed on %%n- sqrt(!Num2M1!^) = !sqrt!

%Sqrt1(Num):Num=Num2%

if !sqrt! neq %%n echo Aacini failed on %%n- sqrt(!Num2!^) = !sqrt!

))

echo Aacini end @ %time%

echo =====================

rem penpen's method:

set "Sqrt2(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))"

echo penpen start @ %time%

< NUL (for /L %%n in (2,1,46340) do (

set /P "=%%n!CR!"

set /A "Num2=%%n*%%n, Num2M1=Num2-1, NM1=%%n-1"

set /A "sqrt=!Sqrt2(N):N=Num2M1!"

if !sqrt! neq !NM1! echo penpen failed on %%n- sqrt(!Num2M1!^) = !sqrt!

set /A "sqrt=!Sqrt2(N):N=Num2!"

if !sqrt! neq %%n echo penpen failed on %%n- sqrt(!Num2!^) = !sqrt!

))

echo penpen end @ %time%

Each test takes less than 5 minutes; this is the output:

Code: Select all

`Aacini start @ 23:50:44.84`

Aacini end @ 23:55:04.78

=====================

penpen start @ 23:55:04.79

penpen end @ 23:57:23.93

My method is slower because it have a FOR command; I will try to eliminate it in order to speed up the method.

Antonio