Dos Batch Math Library

Discussion forum for all Windows batch related topics.

Moderator: DosItHelp

Message
Author
dbenham
Expert
Posts: 2270
Joined: 12 Feb 2011 21:02
Location: United States (east coast)

Re: Dos Batch Math Library

#16 Post by dbenham » 11 Aug 2014 07:08

Done - post has been edited :)


Also, abs() of a 32bit integer is trivial to implement. Here is a version.

Code: Select all

@echo off

:ABS  InExpr  [OutVar]
::
:: Compute the absolute value of expression InExpr
:: and store the result in variable OutVar.
:: Write the result to stdout if OutVar not specified.
::
:: InExpr may be a valid SET /A mathematical expression.
::
:: An error is raised if an attempt is made to get the
:: absolute value of the smallest negative integer.
::
setlocal
set /a "rtn=%~1"
set /a "rtn=%rtn:-=%" || exit /b
endlocal & if "%~2" equ "" (echo %rtn%) else set "%~2=%rtn%"
exit /b

einstein1969
Expert
Posts: 763
Joined: 15 Jun 2012 13:16
Location: Italy, Rome

Re: Dos Batch Math Library

#17 Post by einstein1969 » 13 Aug 2014 07:57

well done. Soon i propose an alternate method (faster) for the sqrt.

Francesco Poscetti

trebor68
Posts: 146
Joined: 01 Jul 2011 08:47

Re: Dos Batch Math Library

#18 Post by trebor68 » 17 Aug 2014 15:45

Calculating Square Root

Here the mathematic rules:
    (a + b)^2 = a^2 + 2ab + b^2
    = a^2 + (2a + b) * b

    (a + b + c)^2 = a^2 + 2ab + b^2 + 2ac + 2bc + c^2
    = a^2 + (2a + b) * b + (2a + 2b + c) * c

Here my code

Code: Select all

@echo off
echo Square Root
set para=%1
if %1# equ # (echo ERROR no number or negativ number) & echo. & goto :eof
if %1 lss 0 (echo ERROR no number or negativ number) & echo. & goto :eof
if %1 equ 0 echo sqrt(0) = 0 & goto :eof

set result=0
set var2=%para%
set "hvar= "
:bnum
set /a var1="var2 %% 100", var2= var2 / 100
set hvar=%var1% %hvar%
if %var2% geq 1 goto :bnum
call :wurzelber %hvar%
echo sqrt(%para%) = %result%
goto :eof

:wurzelber
rem echo %*
set digit=1
set zahl2=0
set zahl1=%1
for %%a in (1 4 9 16 25 36 49 64 81) do if %zahl1% geq %%a set /a zahl2+=1
set /a zahl1=zahl1 - zahl2*zahl2

:next1
if %2# neq # (set zahln=%2) else (set /a zahln=0, digit*=10)
set /a zahl1=zahl1 * 100 + zahln, zahlh = zahl1 / zahl2 / 20, zahl3 = (20 * zahl2 + zahlh) * zahlh

if %zahl1% lss %zahl3% set /a zahlh-=1, zahl3 = (20 * zahl2 + zahlh) * zahlh

set /a zahl2 = 10 * zahl2 + zahlh, zahl1 -= zahl3
shift /2

if %digit% equ 1 if %zahl1% equ 0 (set result=%zahl2%) & goto :eof
if %zahl1% geq 1000000 (
  set /a zahla = zahl2 / digit, zahlb = "(zahl2 %% digit) + digit"
) & (set result=!zahla!.!zahlb:~1!) & goto :eof
goto :next1

dbenham
Expert
Posts: 2270
Joined: 12 Feb 2011 21:02
Location: United States (east coast)

Re: Dos Batch Math Library

#19 Post by dbenham » 18 Aug 2014 09:32

@tebor68 - I'm afraid that is a significant step backwards.

- You forgot SetLocal EnableDelayedExpansion

- It fails with perfect squares: 1, 4, 9, 25, etc.

- The last decimal digit(s) are not always correct

- Using test values of 11, 110, 1100, 11000, 110000, 1100000, 11000000, 110000000, 1100000000, I find it to be 75% slower than my most recent version


Dave Benham

trebor68
Posts: 146
Joined: 01 Jul 2011 08:47

Re: Dos Batch Math Library

#20 Post by trebor68 » 19 Aug 2014 02:01

I have changed the code.
Now the pure square numbers less than 100 are also correct.
The result has now less one decimal place, but this is rounded.

Code: Select all

@echo off
SetLocal EnableDelayedExpansion
echo Square Root
set para=%1
if %1# equ # (echo ERROR no number or negativ number) & echo. & goto :eof
if %1 lss 0 (echo ERROR no number or negativ number) & echo. & goto :eof
if %1 equ 0 echo sqrt(0) = 0 & goto :eof

set result=0
set var2=%para%
set "hvar= "
:bnum
set /a var1="var2 %% 100", var2= var2 / 100
set hvar=%var1% %hvar%
if %var2% geq 1 goto :bnum
call :wurzelber %hvar%
echo sqrt(%para%) = %result%
goto :eof

:wurzelber
rem echo %*
set digit=1
set zahl2=0
set zahl1=%1
for %%a in (1 4 9 16 25 36 49 64 81) do if %zahl1% geq %%a set /a zahl2+=1
set /a zahl1=zahl1 - zahl2*zahl2
if %2# equ # if %zahl1% equ 0 (set result=%zahl2%) & goto :eof

:next1
if %2# neq # (set zahln=%2) else (set /a zahln=0, digit*=10)
set /a zahl1=zahl1 * 100 + zahln, zahlh = zahl1 / zahl2 / 20, zahl3 = (20 * zahl2 + zahlh) * zahlh

if %zahl1% lss %zahl3% set /a zahlh-=1, zahl3 = (20 * zahl2 + zahlh) * zahlh

set /a zahl2 = 10 * zahl2 + zahlh, zahl1 -= zahl3
shift /2

if %digit% equ 1 if %zahl1% equ 0 (set result=%zahl2%) & goto :eof
if %zahl1% geq 1000000 (
  set /a zahla = zahl2 / digit, zahlb = "((zahl2 + 5) %% digit) + digit"
) & (set result=!zahla!.!zahlb:~1,-1!) & goto :eof
goto :next1

dbenham
Expert
Posts: 2270
Joined: 12 Feb 2011 21:02
Location: United States (east coast)

Re: Dos Batch Math Library

#21 Post by dbenham » 19 Aug 2014 05:14

@trebor68

Perfect square multiples of 100 are wrong.

Examples:
10000, 1000000 both compute as 10
40000, 4000000 both compute as 20


Dave Benham

trebor68
Posts: 146
Joined: 01 Jul 2011 08:47

Re: Dos Batch Math Library

#22 Post by trebor68 » 19 Aug 2014 08:18

@dbenham

Thank you.
The code has previously worked well up to this point. But after the code change I have probably not tested again this part.


Change the condition for the perfect squares greater 100.

Also change condition for the not perfect squares (now checked with variable zahl2).
The result with 8 significant digits, last digit is rounded.

Code: Select all

@echo off
SetLocal EnableDelayedExpansion
echo Square Root
set para=%1
if %1# equ # (echo ERROR no number or negativ number) & echo. & goto :eof
if %1 lss 0 (echo ERROR no number or negativ number) & echo. & goto :eof
if %1 equ 0 echo sqrt(0) = 0 & goto :eof

set result=0
set var2=%para%
set "hvar= "
:bnum
set /a var1="var2 %% 100", var2= var2 / 100
set hvar=%var1% %hvar%
if %var2% geq 1 goto :bnum
call :wurzelber %hvar%
echo sqrt(%para%) = %result%
goto :eof

:wurzelber
rem echo %*
set digit=1
set zahl2=0
set zahl1=%1
for %%a in (1 4 9 16 25 36 49 64 81) do if %zahl1% geq %%a set /a zahl2+=1
set /a zahl1=zahl1 - zahl2*zahl2
if %2# equ # if %zahl1% equ 0 (set result=%zahl2%) & goto :eof

:next1
if %2# neq # (set zahln=%2) else (set /a zahln=0, digit*=10)
set /a zahl1=zahl1 * 100 + zahln, zahlh = zahl1 / zahl2 / 20, zahl3 = (20 * zahl2 + zahlh) * zahlh

if %zahl1% lss %zahl3% set /a zahlh-=1, zahl3 = (20 * zahl2 + zahlh) * zahlh

set /a zahl2 = 10 * zahl2 + zahlh, zahl1 -= zahl3
shift /2

if %digit% equ 1 if %zahl1% equ 0 if %2# equ # (set result=%zahl2%) & goto :eof

rem break calc when: zahl2 GEQ 100,000,000  ##  result with 8 significant digits, last digit is rounded
if %zahl2% geq 100000000 (
  set /a zahla = "(zahl2 + 5) / digit", zahlb = "((zahl2 + 5) %% digit) + digit"
) & (set result=!zahla!.!zahlb:~1,-1!) & goto :eof
goto :next1

trebor68
Posts: 146
Joined: 01 Jul 2011 08:47

Re: Dos Batch Math Library

#23 Post by trebor68 » 02 Sep 2014 14:47

Here a batch file to calculate the Square root.
The steps correspond to the calculation with decimal numbers, but here the calculations on binary numbers are optimized.

BATCH value
BATCH value IEEE

value
"Value" is an integer from 0 through 2147483647.
The result is calculated to four decimal places.

value IEEE
"Value" is a number in floating-point representation.
For some values ​​of all results are not yet available. These values ​​are quite small numbers, the really big numbers and the number 0.


EDIT
The revision of the values ​​"inf" and "NaN" incorporated.
The results of the values ​​greater than zero and less 2^-127 (1.1754944 e-38; IEEE 0x00800000) incorrect.

Code: Select all

@echo off
SetLocal EnableExtensions
:: EnableDelayedExpansion
echo Square Root (version binary^)
echo.
set "IEEE="
if /i "%2" equ "IEEE" (set IEEE=IEEE) & goto :ieee1

set /a para=%1 >nul 2>&1
if errorlevel 1 (echo ERROR - wrong value:   %1) & goto :eof

if %para%#==# (echo ERROR - no parameter) & goto :eof
if %para% lss 0 (echo ERROR - no negative numbers) & goto :eof
if %para% equ 0 (echo SQRT(%para%^) = 0) & goto :eof

rem  ##  33222222 22221111 11111100 00000000   ###   33222222 22221111 11111100 00000000
rem  ##  10987654 32109876 54321098 76543210   ###   10987654 32109876 54321098 76543210   Bits in variable num and num2
rem  ##  lxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx   ###   iixxxxxx xxxxxxxx xxxxxxxx xxxxxxxx   Integer value; l - not used (minus bit); ii - used when num2 less than 0
rem  ##  leeeeeee exxxxxxx xxxxxxxx xxxxxxxx   ###   iixxxxxx xxxxxxxx xxxxxxxx xxxxxxxx   IEEE value; l - not used (minus bit); e - exponent; ii - used when num2 less than 0
rem  result of Integer value      :  (1098 7654 3210 9876  543 2109 8765 4321) * 2^-15   <==>  result with max 31 bits
rem  result of floting point value:  (     7654 3210 9876  543 2109 8765 4321) * 2^-15   <==>  any result with 27 bits
rem  IEEE calcuting with the xxx and bit 23 (in variable num): 2^23 + xxx

rem bit = max 15 in 32-Bit-system; Integer (max = 2147483647)
:ieee1
set /a res = 1, bit = 15, num = %1, "block = (1 << (2 * bit))", blplus = 0x40000000, num2 = 0, ERRcode = -1


if defined IEEE set /a "sgn = (%1 >> 31) & 1", "exp = (%1 & 0x7F800000) >> 23", "man = %1 & 0x7FFFFF"

rem test value with special values: NaN, inf and 0
rem   SQRT(NaN) and SQRT(-NaN)  --  not possible then value is not a number
rem   SQRT(inf) and SQRT(-inf)  --  not possible then value is infinity
rem   SQRT(0)   and SQRT(-0)    --  definated as Zero  --  definated: SQRT(-0) = -0
if defined IEEE (
  if %1 equ 0x7FFFFFFF set /a result2 = 0x7FFFFFFF, ERRcode = 1
  if %1 equ 0xFFFFFFFF set /a result2 = 0xFFFFFFFF, ERRcode = 1
  if %1 equ 0x7F800000 set /a result2 = 0x7FFFFFFF, ERRcode = 2
  if %1 equ 0xFF800000 set /a result2 = 0xFFFFFFFF, ERRcode = 2
  if %1 equ 0x00000000 set /a result2 = 0x00000000, ERRcode = 0
  if %1 equ 0x80000000 set /a result2 = 0x80000000, ERRcode = 0
)
if %ERRcode% neq -1 goto :next5

if defined IEEE set /a  "num = man | 0x800000"
if defined IEEE set /a  para2=num, exp2 = exp - 127, sgn2 = -1 * sgn
:: if defined IEEE (echo IEEE  sgn = %sgn%  ==^>  %sgn2%  #  exp = %exp%  ==^>  %exp2%  #  man = %man%  ==^>  %num%) & echo.

rem WHEN exp = 2n+1 IS num = 1.xxx * 2^23 THEN exp ==> 2n TO num ==> 1x.xxx * 2^22
if defined IEEE set /a "hvar = exp & 1", "num2 = hvar * (num & 1) * 0x20000000", "num = num >> (hvar & 1)"
:: if defined IEEE echo calculating with: num = %num%  #  num2 = %num2%  #  exph = %exph% + 127 (testen^)

if defined IEEE set /a  exph = (exp+1) / 2 + 63 - 127

rem   SQRT(-xxx)  --  SQRT from negative numbers not possible
if defined IEEE if "%sgn%" equ "1" (set /a result2 = 0x7FFFFFFF, ERRcode = 3) & goto :next5

:next1
if %block% gtr %num% (set /a "block >>= 2", bit -= 1) & goto :next1

rem first one or two bits; xx * 4^bit, with: 1 LEQ xx LSS 4; bith: bits in front of the point (comma)
set /a num = num - block, bith = bit

:next2
if %bit% equ 0 goto :next3

set /a "block >>= 2", bit -= 1, "vh = ((res << 2) + 1) << (2 * bit)"
if %num% geq %vh% (
  set /a num -= vh, "res = (res << 1) + 1"
) else set /a "res <<= 1"
goto :next2

:next3
rem calculating bits after the point
:: echo SQRT(%para%^) = %res%.xxxx
:: echo.

:next4
set /a bit -= 1, "vh = (res << 2) + 1", "vh1 = vh >> (-2 * bit)", "vh2 = (vh & ((1 << (-2 * bit)) - 1)) << (30 + 2 * bit)", hvar = 0

if %num% gtr %vh1% set hvar=2
if %num% equ %vh1% if %num2% gtr %vh2% set hvar=1
:: if %num% lss %vh1% echo ###  num kleiner vh1  ###

if %hvar% equ 2 set /a num2 -= vh2, "num -= vh1 - (num2 >> 31)", "num2 -= (num2 >> 31) * blplus", "res = (res << 1) + 1"
if %hvar% equ 1 set /a num = 0, num2 -= vh2, "res = (res << 1) + 1"
if %hvar% equ 0 set /a "res <<= 1"

if %bit% gtr -15 goto :next4

:: echo SQRT(%para%^) = %res% * 2^^(%exph%-15)     (%bith%+1 digits point 15 digit binary^)
:: echo.

rem convert to decimal value
set /a "r0 = res >> 15", "rr = 1000 * (res & 0x7fff)", "r1 = rr >> 15", "rr = 1000 * (rr & 0x7fff)", "r2 = rr >> 15", rr = 10000 + 10 * r1 + (r2 + 50) / 100
set result=%r0%.%rr:~-4%
if not defined IEEE echo SQRT(%para%^) = %result%

:: set /a "rest = res & 7"
:: echo Rest = %rest% / 8   #   num = %num%  #  num2 = %num2%  #  bith = %bith%

set /a "resieee = ((res + 0) >> 3) ^0x800000", exph = exph + 127
:: if defined IEEE echo.
:: if defined IEEE echo man = %resieee%  #  exp = %exph%
if defined IEEE set /a "result2 = (sgn << 31) | (exph << 23) | resieee"

:next5
if defined IEEE (echo Result in IEEE = %result2%) & echo.
if defined IEEE if %ERRcode% equ 1 echo  ERROR: not possible then value is not a number
if defined IEEE if %ERRcode% equ 2 echo  ERROR: not possible then value is infinity
if defined IEEE if %ERRcode% equ 3 echo  ERROR: SQRT from negative numbers not possible

EndLocal & (set SQRT=%result%) & set ISQRT=%result2%



The calculating of the reciprocal Sqaure root can see in this batch.

Code: Select all

@echo off
SetLocal EnableExtensions
echo Reciprocal Square Root (version IEEE^)
echo.
set intnum=3

:: load all macros, and exit if it has failed for whatever reasons
call "loadFloat.bat"
if errorLevel 1 exit /b 1

:: use the macros (names are similar to the function names)
for %%a in (operand1 operand2 result string) do set "%%~a="


set /a half=1056964608, threehalf=1069547520

:: set xstr=15625e-5
:: set xstr=25

set xstr=%1
%$str2float% "%xstr%" x

:: echo Eingabewert x: %xstr%   #  dec: %x%
:: echo.
set /a "y_n = 0x5f3759df - (x >> 1)"
%$floatmul% %x% %half% x2
set result=%y_n%

:next
set y_n=%result%
%$floatmul% %y_n% %y_n% y_n2
%$floatmul% %x2% %y_n2% zn
%$floatsub% %threehalf% %zn% zn
%$floatmul% %zn% %y_n% result

:: %$float2str% %result% string
:: echo Zwischenergebnis : %string%

set /a intnum -= 1
if not %intnum% equ 0 goto :next

echo Ergebnis result  : dec %result%
echo.
%$float2str% %result% string
echo Endergebnis      : %string%
EndLocal

einstein1969
Expert
Posts: 763
Joined: 15 Jun 2012 13:16
Location: Italy, Rome

Re: Dos Batch Math Library

#24 Post by einstein1969 » 13 Nov 2015 11:08

Hi,

I'm going to optimize the 32 bit Integer SQRT

This trick down the maximum iteration from 20 to 10, I think that I doubled the speed.

The idea is to use this trick for go down

Code: Select all

@echo off
setlocal EnableDelayedExpansion

Echo Partition the 32bit. Use 512 or 1024 guess!

Set /a N=1
For /L %%N in (1,1,10) do (
  call :sqrt N
  set /A N=N*10
  pause
)
rem MaxINT
call :sqrt 65536*32768-1
pause
exit /b

:sqrt
set /A N=%1
if !N! neq 0 (

  set /A guess=1024, iter=0, x=guess & rem max 10 iteration
  For /L %%I in (1,1,10) do (

    set /A "x=(N/x+x)/2, iter+=1"
    echo Sqrt(%N%^)=!x!  Iter:!iter!
  )
)
exit/b


@trebor68
Very nice work on IEEE sqrt 8)

EDIT:
output:

Code: Select all

Partition the 32bit. Use 512 or 1024 guess
Sqrt(1)=512  Iter:1
Sqrt(1)=256  Iter:2
Sqrt(1)=128  Iter:3
Sqrt(1)=64  Iter:4
Sqrt(1)=32  Iter:5
Sqrt(1)=16  Iter:6
Sqrt(1)=8  Iter:7
Sqrt(1)=4  Iter:8
Sqrt(1)=2  Iter:9
Sqrt(1)=1  Iter:10
Premere un tasto per continuare . . .
Sqrt(10)=512  Iter:1
Sqrt(10)=256  Iter:2
Sqrt(10)=128  Iter:3
Sqrt(10)=64  Iter:4
Sqrt(10)=32  Iter:5
Sqrt(10)=16  Iter:6
Sqrt(10)=8  Iter:7
Sqrt(10)=4  Iter:8
Sqrt(10)=3  Iter:9
Sqrt(10)=3  Iter:10
Premere un tasto per continuare . . .
Sqrt(100)=512  Iter:1
Sqrt(100)=256  Iter:2
Sqrt(100)=128  Iter:3
Sqrt(100)=64  Iter:4
Sqrt(100)=32  Iter:5
Sqrt(100)=17  Iter:6
Sqrt(100)=11  Iter:7
Sqrt(100)=10  Iter:8
Sqrt(100)=10  Iter:9
Sqrt(100)=10  Iter:10
Premere un tasto per continuare . . .
Sqrt(1000)=512  Iter:1
Sqrt(1000)=256  Iter:2
Sqrt(1000)=129  Iter:3
Sqrt(1000)=68  Iter:4
Sqrt(1000)=41  Iter:5
Sqrt(1000)=32  Iter:6
Sqrt(1000)=31  Iter:7
Sqrt(1000)=31  Iter:8
Sqrt(1000)=31  Iter:9
Sqrt(1000)=31  Iter:10
Premere un tasto per continuare . . .
Sqrt(10000)=516  Iter:1
Sqrt(10000)=267  Iter:2
Sqrt(10000)=152  Iter:3
Sqrt(10000)=108  Iter:4
Sqrt(10000)=100  Iter:5
Sqrt(10000)=100  Iter:6
Sqrt(10000)=100  Iter:7
Sqrt(10000)=100  Iter:8
Sqrt(10000)=100  Iter:9
Sqrt(10000)=100  Iter:10
Premere un tasto per continuare . . .
Sqrt(100000)=560  Iter:1
Sqrt(100000)=369  Iter:2
Sqrt(100000)=320  Iter:3
Sqrt(100000)=316  Iter:4
Sqrt(100000)=316  Iter:5
Sqrt(100000)=316  Iter:6
Sqrt(100000)=316  Iter:7
Sqrt(100000)=316  Iter:8
Sqrt(100000)=316  Iter:9
Sqrt(100000)=316  Iter:10
Premere un tasto per continuare . . .
Sqrt(1000000)=1000  Iter:1
Sqrt(1000000)=1000  Iter:2
Sqrt(1000000)=1000  Iter:3
Sqrt(1000000)=1000  Iter:4
Sqrt(1000000)=1000  Iter:5
Sqrt(1000000)=1000  Iter:6
Sqrt(1000000)=1000  Iter:7
Sqrt(1000000)=1000  Iter:8
Sqrt(1000000)=1000  Iter:9
Sqrt(1000000)=1000  Iter:10
Premere un tasto per continuare . . .
Sqrt(10000000)=5394  Iter:1
Sqrt(10000000)=3623  Iter:2
Sqrt(10000000)=3191  Iter:3
Sqrt(10000000)=3162  Iter:4
Sqrt(10000000)=3162  Iter:5
Sqrt(10000000)=3162  Iter:6
Sqrt(10000000)=3162  Iter:7
Sqrt(10000000)=3162  Iter:8
Sqrt(10000000)=3162  Iter:9
Sqrt(10000000)=3162  Iter:10
Premere un tasto per continuare . . .
Sqrt(100000000)=49340  Iter:1
Sqrt(100000000)=25683  Iter:2
Sqrt(100000000)=14788  Iter:3
Sqrt(100000000)=10775  Iter:4
Sqrt(100000000)=10027  Iter:5
Sqrt(100000000)=10000  Iter:6
Sqrt(100000000)=10000  Iter:7
Sqrt(100000000)=10000  Iter:8
Sqrt(100000000)=10000  Iter:9
Sqrt(100000000)=10000  Iter:10
Premere un tasto per continuare . . .
Sqrt(1000000000)=488793  Iter:1
Sqrt(1000000000)=245419  Iter:2
Sqrt(1000000000)=124746  Iter:3
Sqrt(1000000000)=66381  Iter:4
Sqrt(1000000000)=40722  Iter:5
Sqrt(1000000000)=32639  Iter:6
Sqrt(1000000000)=31638  Iter:7
Sqrt(1000000000)=31622  Iter:8
Sqrt(1000000000)=31622  Iter:9
Sqrt(1000000000)=31622  Iter:10
Premere un tasto per continuare . . .
Sqrt(2147483647)=1049087  Iter:1
Sqrt(2147483647)=525567  Iter:2
Sqrt(2147483647)=264826  Iter:3
Sqrt(2147483647)=136467  Iter:4
Sqrt(2147483647)=76101  Iter:5
Sqrt(2147483647)=52159  Iter:6
Sqrt(2147483647)=46665  Iter:7
Sqrt(2147483647)=46342  Iter:8
Sqrt(2147483647)=46340  Iter:9
Sqrt(2147483647)=46340  Iter:10
Premere un tasto per continuare . . .


einstein1969

einstein1969
Expert
Posts: 763
Joined: 15 Jun 2012 13:16
Location: Italy, Rome

Re: Dos Batch Math Library

#25 Post by einstein1969 » 14 Nov 2015 10:55

There are news on speeding research.

I have used a linear equation ( a line Y=N/(11*1024)+40 ) for guessing the square root and the I have insert in the Newthon algorithm.

The guessing is nice and I doubled another time the speed.

Now with 5 iterations is possible calculate integer 32bit square roots.

new code:

Code: Select all

:sqrt0
set /A N=%1
if !N! neq 0 (

  rem set /A "guess=N/(40*1024)+128, x=guess" & rem max 7 iterations
  rem set /A "guess=N/(35*1024)+64, x=guess" & rem max 6
  rem set /A "guess=N/(12*1024)+32, x=guess" & rem max 6
  set /A "guess=N/(11*1024)+40, x=guess" & rem max 5


  For /L %%I in (1,1,5) do (

    set /A "x=(N/x+x)/2"
    echo Sqrt(%N%^)=!x!  Iter:%%I guess:!guess!
  )
)
exit/b


Now it is possible using the Aacini method in this thread Definition and use of arithmetic "functions" in Batch files.

Code: Select all

@echo off

set "Sqrt(N)=( x=(N)/(11*1024)+40, 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 )"

set /A num=%Sqrt(N):N=25%
echo Square root of 25 is : %num%

result:

Code: Select all

Square root of 25 is : 5

There is only a problem with Sqrt(0).

This is the graphics with the absolute error in the guess calcolous.

einstein1969

penpen
Expert
Posts: 1713
Joined: 23 Jun 2013 06:15
Location: Germany

Re: Dos Batch Math Library

#26 Post by penpen » 14 Nov 2015 14:52

einstein1969 wrote:There is only a problem with Sqrt(0).
This should be relatively easy to solve, just add one more iteration step.
You could also provoke an error/exception (division by zero), when processing negative integers:

Code: Select all

@echo off
setlocal enableDelayedExpansion
set "Sqrt(N)=( x=(N)/(11*1024)+40, 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+x)/2, x/=(1+(N>>31)))"

for %%s in (-2147483647, -1, 0, 1, 4, 9, 16, 25, 2147395600, 2147483647) do (
   (
      set /A "num=!Sqrt(N):N=%%~s!"
   ) && (
      echo Square root of %%~s is : !num!
   ) || (
      echo Square root of %%~s is not in R.
   )
)

endlocal
goto :eof


penpen

einstein1969
Expert
Posts: 763
Joined: 15 Jun 2012 13:16
Location: Italy, Rome

Re: Dos Batch Math Library

#27 Post by einstein1969 » 15 Nov 2015 08:40

Thanks penpen! I like the negative catch.

Code: Select all

  Rem NOTE: The equation of the line is y=mx+q. 
  Rem The maxim for q is 31 to achieve the 0 in the 5 iteration.
  Rem But for every m is not possible go down into 5 iteration.


... but I have found a patch for the ZERO using only 5 iteration (my goal is speeding).

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/=(1+(N>>31)))"

for %%s in (-2147483647, -1, 0, 1, 4, 9, 16, 25, 65536, 131072, 262144, 393216, 2147395600, 2147483647) do (
   (
      set /A "num=!Sqrt(N):N=%%~s!"
   ) && (
      echo Square root of %%~s is : !num!
   ) || (
      echo Square root of %%~s is not in R.
   )
)

endlocal
goto :eof


output:

Code: Select all

Errore di divisione per zero.
Square root of -2147483647 is not in R.
Errore di divisione per zero.
Square root of -1 is not in R.
Square root of 0 is : 0
Square root of 1 is : 1
Square root of 4 is : 2
Square root of 9 is : 3
Square root of 16 is : 4
Square root of 25 is : 5
Square root of 65536 is : 256
Square root of 131072 is : 362
Square root of 262144 is : 512
Square root of 393216 is : 627
Square root of 2147395600 is : 46340
Square root of 2147483647 is : 46340



einstein1969

einstein1969
Expert
Posts: 763
Joined: 15 Jun 2012 13:16
Location: Italy, Rome

Re: Dos Batch Math Library

#28 Post by einstein1969 » 16 Nov 2015 09:21

I have done some test and there is a problem on the proposed code.

The Sqrt(65535) return 256 and not 255. I have not checked other value. :shock:

I don't know if the problem is the number of iteration because:

The Newton method on integer sqrt is not stable.

es.

Code: Select all

@echo off
setlocal EnableDelayedExpansion

call :sqrt0 65535 10
exit/b

:sqrt0
set /A N=%1
if !N! geq 0 (

  Rem NOTE: The equation of the line is y=mx+q.
  Rem The maxim for q is 31 to achieve the 0 in the 5 iteration.
  Rem But for every m is not possible go down into 5 iteration.

  rem set /A "guess=N/(40*1024)+128, x=guess" & rem max 7 iterations
  rem set /A "guess=N/(35*1024)+64, x=guess" & rem max 6
  rem set /A "guess=N/(12*1024)+32, x=guess" & rem max 6
  rem set /A "guess=N/(11*1024)+40, x=guess" & rem max 6 better

  rem workaround for ZERO.
  set /A "guess=N/(11*1024)+40-^!N*9, x=guess" & rem max 5

  For /L %%I in (1,1,%2) do (
    set /A "x=(N/x+x)/2"
    echo Sqrt(%N%^)=!x!  Iter:%%I guess:!guess!
  )
)
exit/b

output:

Code: Select all

Sqrt(65535)=750  Iter:1 guess:45
Sqrt(65535)=418  Iter:2 guess:45
Sqrt(65535)=287  Iter:3 guess:45
Sqrt(65535)=257  Iter:4 guess:45
Sqrt(65535)=256  Iter:5 guess:45
Sqrt(65535)=255  Iter:6 guess:45
Sqrt(65535)=256  Iter:7 guess:45
Sqrt(65535)=255  Iter:8 guess:45
Sqrt(65535)=256  Iter:9 guess:45
Sqrt(65535)=255  Iter:10 guess:45


But the aacini integer sqrt return the exact result because there is a test of STOP. if !iter2! geq !iter1!

Code: Select all

:Sqrt_aacini
setlocal EnableDelayedExpansion

set /A number=%1
set /A iter1=number/2+1

rem The maximum number of iterations to calculate sqrt of a 32 bits integer number is 20
set "sqrt="
for /L %%i in (1,1,20) do if not defined sqrt (
   set /A "iter2=number/iter1, iter1=(iter1+iter2)/2"
   if !iter2! geq !iter1! set /A "sqrt=(iter1+iter2)/2"
)
echo Sqrt(%number%) = %sqrt%
exit/b

output:

Code: Select all

Sqrt(65535) = 255


I don't understand this test of exit.

If I don't resolve this question I don't go in this direction.

Einstein1969

Aacini
Expert
Posts: 1611
Joined: 06 Dec 2011 22:15
Location: México City, México

Re: Dos Batch Math Library

#29 Post by Aacini » 16 Nov 2015 13:43

einstein1969 wrote:I have done some test and there is a problem on the proposed code.

The Sqrt(65535) return 256 and not 255. I have not checked other value. :shock:

I don't know if the problem is the number of iteration because:

The Newton method on integer sqrt is not stable.

. . . .

If I don't resolve this question I don't go in this direction.

Einstein1969


Yes. Your method fails with numbers as less as 35 or 48. The method iterates on a series of values and in each step it must produce a value less or equal than the previous one, so the method may fail when a next value is greater. I inserted the required IF command, but then realized that the test must not be applied to the first value. I inserted the test from the second value on and cut the loop to 4 cycles, but then realized that in certain cases the result was wrong and it requires an additional step. This means that it needs a total of 6 cycles.

The code below includes all these points; it also includes the "function" method (although not for SET command, but as individual macro).

Code: Select all

@echo off
setlocal EnableDelayedExpansion

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


:loop
   echo/
   set "number="
   set /P "number=Enter number: "
   if not defined number goto :EOF
   call :sqrt0 %number%
   echo/
   %Sqrt(Num):Num=!number!%
   echo Function method: %sqrt%
   echo/
goto loop


:sqrt0
set /A N=%1
if %N% neq 0 (

  rem set /A "guess=N/(40*1024)+128, x=guess" & rem max 7 iterations
  rem set /A "guess=N/(35*1024)+64, x=guess" & rem max 6
  rem set /A "guess=N/(12*1024)+32, x=guess" & rem max 6
  set /A "guess=N/(11*1024)+40, x=(N/guess+guess)/2" & rem max 5

  echo guess = !guess!

  For /L %%I in (1,1,5) do (
    set /A "x2=(N/x+x)/2"
    if !x2! leq !x! set /A x=x2
    echo %%I- Sqrt(%N%^)=!x!
  )
)
exit/b

Antonio

penpen
Expert
Posts: 1713
Joined: 23 Jun 2013 06:15
Location: Germany

Re: Dos Batch Math Library

#30 Post by penpen » 16 Nov 2015 19:42

einstein1969 wrote:The Sqrt(65535) return 256 and not 255. I have not checked other value. :shock:

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

Post Reply