The usual way to perform operations on Big Numbers is to split the number in "chunks" of an appropriate size suitable to be managed by the available operations. In assembly language there are instructions that aids to perform operations on a number written as a BCD string with an unlimited number of digits. In Batch files the usual method consist in split the big number in groups of 4 digits (that we called "Quads") because if we use 5 digits and perform a multiplication, the result exceed the maximum 32 bits integer number. We could manage more digits for other operations (like groups of 9 digits for addition and sustraction), but the conversion between number representations for different operations makes the process slower.
Some time ago I started writing a Big Numbers program in a Batch file. I then modified my method to make it more efficient by taking ideas from this topic, and later modified it further more to a significant degree by adapting this method to it. A couple days ago I saw this einstein1969's post about Big Numbers, so I dusted off my method and posted it here.
The core point of my method is not to perform the operations on the series of Quads via a FOR loop, but on a single long SET /A expression instead; of course, this implies making some adjustments prior to the operation itself. Also, I've simplified the way to manage a BigNum via a list of Quads stored as a string in a single variable. This point simplifies the management of several Big Numbers. For example:
Code: Select all
call :NumToBig bigA=123456789012345678901.161718
Code: Select all
bigA=1 2345 6789 123 4567 8901 1617 1800
Code: Select all
call :BigToNum num=bigA
Code: Select all
@echo off
setlocal EnableDelayedExpansion
rem BigNumbers.bat: Fast Arithmetic Operations on Big Numbers
rem Antonio Perez Ayala
rem In this program a "BigNum" is a variable that contains *a list* of "Quads" (four digits values) from the original Big Number;
rem the longest BigNum can contain up to 29 Quads (in current version) = 116 digits (that include any desired number of decimals).
rem Two BigNum's are operated for Add and Subtract operations in just *one* long SET /A command nested in two FOR /F (no loop) commands
rem and a multiplication just takes as many SET /A commands as the number of Quads in the shorter operand.
rem The division is currently under construction.
rem These FOR tokens comprises the longest contiguous set of chars (29 each) that can also serve as *variable names*:
set "tokens1=? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ "
set "tokens2=_ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { "
set "reversed1=? "
for %%a in (%tokens1:~1%) do set "reversed1=%%a !reversed1!"
set "reversed2="
for %%a in (%tokens2%) do set "reversed2=%%a !reversed2!"
rem Assemble the "GETRESULT" macro that creates a BigNum from the auxiliary variables that get the results of tokens operations
set "GETRESULT=^!?^!"
for %%a in (%tokens1:~1%) do set "GETRESULT=!GETRESULT! ^!%%a^!"
rem Assemble the "INITRESULT" macro that initializes to zero all the auxiliary variables
set "INITRESULT=?=0"
for %%a in (%tokens1:~1%) do set "INITRESULT=!INITRESULT!,%%a=0"
rem Assemble the MAKE variable that is an intermediate step that allows to generate another variable (ADD29 in this case)
rem that contains a series of operations over pair of tokens in order to execute they in a long SET /A command.
rem For further details on this method, see: https://www.dostips.com/forum/viewtopic.php?f=3&t=10214#p65156
rem Variable # is carry, variable $ is 10000
set "p=%%"
SET MAKE=set "ADD29=#=0" ^& set "x=%reversed1: =" ^& for /F "tokens=1*" !p!a in ("^!reversed2^!") do (set "ADD29=^!ADD29^!,^!x^!=!p!^!x^!+!p!!p!a+#,#=^!x^!/$,^!x^!!p!=$" ^& set "reversed2=!p!b") ^& set "x=%"
rem Run created MAKE variable to generate ADD29 variable containing ADD operations for 29 FOR /F tokens as Quads of two BigNum's
rem and preserve "reversed2" tokens string
(
%MAKE%
set "reversed2=%reversed2%"
)
rem Assemble MAKE variable to generate SUB29 variable to subtract two BigNum's, and create it (# is borrow, $ is 10000)
SET MAKE=set "SUB29=#=0" ^& set "x=%reversed1: =" ^& for /F "tokens=1*" !p!a in ("^!reversed2^!") do (set "SUB29=^!SUB29^!,^!x^!=!p!^!x^!-!p!!p!a-#,#=(^!x^!>>31)&1,^!x^!+=#*$" ^& set "reversed2=!p!b") ^& set "x=%"
(
%MAKE%
set "reversed2=%reversed2%"
)
rem Assemble MAKE variable to generate MUL[i] array to multiply a BigNum by *one term* of the other BigNum (specified by %%#), and create they
rem There is a different formula for each term in the second BigNum because the position of the summations change with each term
set "reversed1Cut=%reversed1%"
set "imul=0"
:nextMUL
SET MAKE=set "MUL=#=0" ^& set "x=%reversed1Cut: =" ^& for /F "tokens=1*" !p!a in ("^!reversed1^!") do (set "MUL=^!MUL^!,^!x^!+=!p!!p!a*!p!#+#,#=^!x^!/$,^!x^!!p!=$" ^& set "reversed1=!p!b") ^& set "x=%"
(
%MAKE%
set "reversed1=%reversed1%"
)
set "reversed1Cut=%reversed1Cut:* =%"
set /A imul+=1
set "MUL[%imul%]=!MUL!"
if %imul% lss 29 goto nextMUL
set "MUL="
rem End of initializations
rem =====================================
rem Process data part
set "spaces="
for /L %%i in (1,1,65) do set "spaces=!spaces! "
set "decimals=4"
set /P "decimals=Enter the number of decimals [4]: "
set /A "decimals=(decimals-1)/4+1, point=decimals*4"
echo/
echo Enter two Big Numbers with NO sign and optional decimal point
echo and the first one GREATER THAN the second one
verify > NUL
:loop
echo/
echo -------------------------------------------
echo/
set /P "one=One: "
if errorlevel 1 goto :EOF
set /P "two=Two: "
call :NumToBig BigOne=%one%
if errorlevel 1 echo Number too big & goto :EOF
call :NumToBig BigTwo=%two%
if errorlevel 1 echo Number too big & goto :EOF
echo/
call :BigToNum one=BigOne
call :BigToNum two=BigTwo
set "one=%spaces%%one%"
set "two=%spaces%%two%"
echo One= %one:~-65%
echo Two= %two:~-65%
echo/
rem Add the BigNum's
for /F "tokens=1-29" %%? in ("%BigOne%") do for /F "tokens=1-29" %%_ in ("%BigTwo%") do set /A "$=10000,%ADD29%"
set "BigAdd=%GETRESULT%"
call :BigToNum add=BigAdd
set "add=%spaces%%add%"
echo One+Two=%add:~-65%
echo/
rem Subtract the BigNum's
for /F "tokens=1-29" %%? in ("%BigOne%") do for /F "tokens=1-29" %%_ in ("%BigTwo%") do set /A "$=10000,%SUB29%"
set "BigSub=%GETRESULT%"
call :BigToNum sub=BigSub
set "sub=%spaces%%sub%"
echo One-Two=%sub:~-65%
echo/
rem Multiply the BigNum's
set /A "%INITRESULT%,$=10000,imul=0"
rem Process the second BigNum *in reversed order* (the same order of the formulae)
set "reversedBigTwo="
for %%# in (%BigTwo%) do set "reversedBigTwo=%%# !reversedBigTwo!"
rem Process ony-by-one the Quads of second BigNum
for %%# in (%reversedBigTwo%) do (
rem Multiply all the first BigNum by one Quad of second BigNum
set /A imul+=1
if %%# neq 0 call :MulTerm !imul!
)
set "BigMul=%GETRESULT%"
set /A point*=2 & call :BigToNum mul=BigMul & set /A point/=2
set "mul=!mul:~0,-%point%!"
set "mul=%spaces%%mul%"
echo One*Two=%mul:~-65%
echo/
goto loop
:MulTerm imul
set "MULTERM=!MUL[%1]!"
for /F "tokens=1-29" %%? in ("%BigOne%") do set /A "%MULTERM%"
exit /B
:NumToBig big=####.####
for /F "tokens=1,2 delims=." %%a in ("%~2") do set "int=%%a" & set "frac=%%b"
set "%1="
if not defined frac for /L %%i in (1,1,%decimals%) do set "frac=!frac!0000"
set /A "fracs=0, quads=0"
:nextFrac
set "quad=1%frac:~0,4%000"
set /A quad=%quad:~0,5%-10000, fracs+=1, quads+=1
set "%1=!%1! %quad%"
if %fracs% equ %decimals% goto nextInt
set "frac=%frac:~4%"
if defined frac goto nextFrac
if %fracs% equ %decimals% goto nextInt
set /A fracs+=1
for /L %%i in (%fracs%,1,%decimals%) do set "%1=!%1! 0" & set /A quads+=1
:nextInt
set "quad=1%int:~-4%"
if %quad% geq 10000 (set /A quad-=10000) else set "quad=%int%"
set "%1=%quad% !%1!"
set /A quads+=1
set "int=%int:~0,-4%"
if defined int goto nextInt
if %quads% gtr 29 exit /B 2
for /L %%i in (%quads%,1,28) do set "%1=0 !%1!"
exit /B
:BigToNum num=big
set "%1="
for %%a in (!%2!) do (
if not defined %1 (
if %%a neq 0 set "%1=%%a"
) else (
set /A "quad=10000+%%a"
set "%1=!%1!!quad:~1!
)
)
if "!%1:~0,-%point%!" equ "" (
for /L %%i in (1,1,%point%) do set "%1=0!%1!"
set "%1=0!%1:~-%point%!"
)
set "%1=!%1:~0,-%point%!.!%1:~-%point%!"
exit /B
- Manage negative numbers.
- A more flexible management of the number of decimals.
- Extend the number of Quads in a BigNum variable (and hence the number of digits per Big Number) using the techniques described at this post.
- Extend one Big Number to have several BigNum variables. This could manage an unlimited number of digits in a Big Number.
Antonio