Thanks , the algorithm is clear and if I found the source I will post.
Antonio, The sqrt algorithm with many decimal is very good! I will study for increment my knowledge.
The last Integer SQRT 32Bit is very fast and stable. I have try to optimize but for now is unbeatable.
Code: Select all
@echo off
setlocal EnableDelayedExpansion
for /f "delims==" %%v in ('set') do set "%%v="
for /F %%a in ('copy /Z "%~F0" NUL') do set "CR=%%a"
rem The unbeatable!!
set "Sqrt(N)=( M=(N),x=M/(11*1024)+40, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem set "Sqrt(N)=( M=(N), guess=x=(((M-1529513880)>>31)+1)*(4096)+(((M-12752040)>>31)+1)*(8192+2048+1024+512+256+128+64+32+4+1)+(((M-29928)>>31)+1)*(512+256+128+32+4+1)+31, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem set "Sqrt(N)=( M=(N), x=(((M-1529513880)>>31)+1)*4096+(((M-12752040)>>31)+1)*12261+(((M-29928)>>31)+1)*933+31, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem set "Sqrt(N)=( M=(N), guess=x=(((M-798345024)>>31)+1)*(16384)+(((M-84015555)>>31)+1)*(8192+2048+1024+256+128+64+32+16+8+4+2+1)+(((M-5904899)>>31)+1)*(2048+1024+512+128+64+32+16+2+1)+(((M-226575)>>31)+1)*(512+256+128+64+16+8+2+1)+(((M-2915)>>31)+1)*(128+32+16+1)+15, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem i guess con intervalli sono più lenti!
rem http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm
rem http://www.mathpages.com/home/kmath190.htm
Rem accelerate, 1 accelerate. Se N < 715827882 posso usare la convergenza geometrica. Altrimenti uso quella lineare.
set "Sqrt(N)=( M=(N), g0=40+N/7000, q1=(0x7FFFFFFF-g0*g0*g0)/(3*g0), overflow=-(M-q1>>31), guess=x=overflow*( p=(g0*(p1=(g0*g0+3*M))/(3*g0*g0+M)) )+(2200+N/29500)*(1-overflow)+1, x1=x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
Rem questa e' quella stabile.
set "Sqrt(N)=( M=(N), g0=40+N/7000, overflow=-(M-(0x7FFFFFFF-g0*g0*g0)/(3*g0)>>31), x=overflow*(g0*(g0*g0+3*M)/(3*g0*g0+M))+(2200+N/29500)*(1-overflow)+1, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem fisso N=2086000 overflow
set "Sqrt(N)=( M=(N), g0=40+N/7000, overflow=-(M-2086000>>31), x=-(M-2086000>>31)*(g0*(g0*g0+3*M)/(3*g0*g0+M))+(2200+N/29500)*(1+(M-2086000>>31))+1, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem ottimizzo la precedente
set "Sqrt(N)=( M=(N), g0=40+N/7000, x=-(M-2086000>>31)*(g0*(g0*g0+3*M)/(3*g0*g0+M))+(2200+N/29500)*(1+(M-2086000>>31))+1, x=(M/x+x)>>1, x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem lenta/slow
rem provo con meno iterazioni! una semplice nella quadratica
set "Sqrt(N)=( M=(N), g0=23+N/1466, q1=(0x7FFFFFFF-g0*g0*g0)/(3*g0), overflow=-(M-q1>>31), guess=x=overflow*( p=(g0*(p1=(g0*g0+3*M))/(3*g0*g0+M)) )+(((M/(2151+N/29265)+(2151+N/29265))>>1 )+1)*(1-overflow), x1=x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem ottimizzo precedente
set "Sqrt(N)=( M=(N), g0=23+N/1466, x=-(M-(0x7FFFFFFF-g0*g0*g0)/(3*g0)>>31)*( p=(g0*(p1=(g0*g0+3*M))/(3*g0*g0+M)) )+(((M/(2151+N/29265)+(2151+N/29265))>>1 )+1)*(1+(M-(0x7FFFFFFF-g0*g0*g0)/(3*g0)>>31)), x=(M/x+x)>>1, x=(M/x+x)>>1, x+=(M-x*x)>>31 )"
rem lenta/slow
rem for %%s in (-2147483647, -1, 0, 1, 2, 3, 4, 9, 10, 16, 25, 100, 511, 512, 1000, 10000,
for %%s in (0, 1, 2, 3, 4, 9, 10, 16, 25, 100, 511, 512, 1000, 10000,
65535, 65536, 100000, 131071, 131072, 262143, 262144, 393215, 393216,
1000000, 2085999, 2086000, 5000000, 10000000, 100000000, 200000000, 1000000000, 2147395600, 2147483647) do (
set /A "sqrt=!Sqrt(N):N=%%s!"
rem echo Sqrt(%%s^)=!sqrt! - g0:!g0! q1:!q1! overflow:!overflow! p=!p! p1:!p1! guess:!guess! x1:!x1!
if !overflow! equ 0 echo(
echo Sqrt(%%s^)=!sqrt! - g0:!g0! overflow:!overflow! guess:!guess! x1:!x1!
)
pause
set "t1=!time: =0!"
rem < NUL (for /L %%n in (2,1,46340) do (
(for /L %%n in (2,1,46340) do (
rem set /P "=%%n!CR!" <nul
set /A "Num2=%%n*%%n, Num2M1=Num2-1, NM1=%%n-1"
set /A "sqrt=%Sqrt(N):N=Num2M1%"
if !sqrt! neq !NM1! echo failed on %%n- sqrt(!Num2M1!^) = !sqrt! & pause
set /A "sqrt=%Sqrt(N):N=Num2%"
if !sqrt! neq %%n echo failed on %%n- sqrt(!Num2!^) = !sqrt! & pause
))
rem if !overflow! equ 0 echo %%n & pause
for /F "tokens=1-8 delims=:.," %%a in ("!t1!:!time: =0!") do set /a "a=(((1%%e-1%%a)*60)+1%%f-1%%b)*6000+1%%g%%h-1%%c%%d, a+=(a>>31)&8640000, FPS=10000/a"
Title Time Elapsed:!a!0ms - FPS: !FPS:~0,-2!.!FPS:~-2!
set a=&set t1=&set FPS=
pause
exit/b
- Divide the interval to guess in more part. For better Guess.
- Accelerate the convergency. Via Halley's method (Householder)
- Mix.
These work well but the performance are lower.
The trick is guessing better. I have found a guess method that use LOG_x(N) (base x logarithm) but I have problem to implement.
- Compact two step of newton's method into one.