How to find large factorials using a batch script

Question

@echo off
if %1.==. ( echo Missing parameter! Try passing the number as a parameter     like   'factorial   10' without the quotes.
goto end )
setlocal enabledelayedexpansion
set /a count=0
set /a temp=0
set /a digits=1
set /a array1=1
for /L %%i IN (2,1,%1) do (
set /a temp=0
for /L %%j IN ( 1,1,!digits! ) do (
set /a temp=!temp!+!array%%j!*%%i
set /a array%%j=!temp!%%10
set /a temp=!temp!/10   ) 

set /a index=!digits!+1

for /L %%v IN (!index!,1,!index! ) do (
if !temp! NEQ 0 (
set /a array!index!=!temp!%%10
set /a temp/=10
set /a index+=1 ))
set /a digits=!index!-1)
for /l %%v IN ( !digits!,-1,1 ) do set array=!array!!array%%v!
echo !array!
echo Total # of decimal digits = !digits!
:end
pause

This is what i have gotten so far. It is quite stable under 10! but once i reach 15 or 20 it starts missing out a few digits.

My edit....

@echo off
if %1.==. ( echo Missing parameter! Try passing the number as a parameter  like   'factorial   10' without the quotes.
goto end )
setlocal enabledelayedexpansion
set /a count=0
set /a temp=0
set /a digits=1
set /a array1=1
for /L %%i IN (2,1,%1) do (
set /a temp=0
for /L %%j IN ( 1,1,!digits! ) do (
set /a temp=!temp!+!array%%j!*%%i
set /a array%%j=!temp!%%10
set /a temp=!temp!/10   ) 

for /l %%v IN ( 1,1,30 ) do (
if !temp! neq 0 (
set /a digits+=1
set /a array!digits!=!temp!%%10
set /a temp=!temp!/10
)))
for /l %%v IN ( !digits!,-1,1 ) do set array=!array!!array%%v!
echo !array!
echo Total # of decimal digits = !digits!
:end
pause

Now i am forcing the the last inner loop to run 30 times eventhough temp would have been zero way before that. Is there any way to write a snippet that would be analogous to the following c code while (temp) {/code goes here/}

This execute only as long as temp is non zero.

Is there any partyicular limit to how big a variable can be in a batch? I know it is a pain * to debug computational programs in a batch, I'm just trying to code this in all programming languages i know, Just so i could compare their speeds. Can somebody Please point out what i'm doing wrong here.

edit........22/12/13

@echo off
if %1.==. ( echo Missing parameter! Try passing the number as a parameter like   'factorial   10' without the quotes.
goto end )
setlocal enabledelayedexpansion

set /a count=0
set /a tempo=0
set /a digits=1
set /a array1=1

for /f "tokens=1-4 delims=:.," %%a IN ("%time%") do (     
set /a "start=(((%%a*60)+1%%b %% 100)*60+1%%c %%100)*100+1%%d %% 100"
)

for /L %%i IN (2,1,%1) do (
set /a tempo=0
for /L %%j IN ( 1,1,!digits! ) do (
set /a tempo=!tempo!+!array%%j!*%%i
set /a array%%j=!tempo!%%10000
set /a tempo=!tempo!/10000   ) 

for /l %%v IN (1,1,2) do (
if !tempo! neq 0 (
set /a digits+=1
    set /a array!digits!=tempo%%10000
set /a tempo=tempo/10000
))
)

for /l %%v IN ( !digits!,-1,1 ) do set array=!array!!array%%v!
echo !array!  
echo Total # of decimal digits = !digits!

for /f "tokens=1-4 delims=:.," %%a in ("%time%") do (
set /a "end=(((%%a*60)+1%%b %% 100)*60+1%%c %%100)*100+1%%d %% 100"
)

set /a elapsedcs=end-start
set /a elapseds=elapsedcs/100
set /a elapsedcs=elapsedcs%%100
echo %elapseds%.%elapsedcs% seconds
:end
rem label should never be the last statement

Is this what you meant aacini?

Answer 1

In order to achieve fast arithmetic operations on Big numbers in Batch, you must split the Bignum in groups of digits that can be managed via the 32-bits operations of set /A command. The maximum 32-bits signed integer is 2147483647, so the largest group of digits that can be multiplied this way is 4, because 5 digits (99999 x 99999) exceed the maximum number. Addition and multiplication must be achieved from right to left translating a "carry" to the next group to the left. Subtraction and division must be achieved from left to right translating a "borrow" to the next group to the right. The Batch file below use this method to succesively multiply a Bignum by a 4 digits factor, so it can calculate up to 9999! as long as all variables that contain the groups of 4 digits fits in the 64 MB size limit of the environment (look for "65,536KB maximum size" under "Setting environment variables"). The result is directly output to the screen in order to avoid the 8192 digits limit of one Batch variable.

EDIT: I slightly modified the program in order to run faster and get the number of digits in the result.

@echo off

if "%1" equ "" (
   echo Missing parameter! Try passing the number as a parameter like 'factorial 10' without the quotes.
   goto end
)

setlocal EnableDelayedExpansion

rem Calculate the factorial
set /A g1=1, groups=1
for /L %%n in (2,1,%1) do (
   set carry=0
   for /L %%g in (1,1,!groups!) do (
      set /A group=g%%g*%%n+carry, g%%g=group%%10000, carry=group/10000
   )
   if !carry! neq 0 (
      set /A groups+=1
      set g!groups!=!carry!
   )
)

rem Show the factorial
set /P "=!g%groups%!" < NUL
set /A groupsM1=groups-1
for /L %%g in (%groupsM1%,-1,1) do (
   set group=000!g%%g!
   set /P "=!group:~-4!" < NUL
)
echo/

rem Get the number of digits
set digits=0
for /L %%i in (0,1,3) do if "!g%groups%:~%%i,1!" neq "" set /A digits+=1
set /A digits+=4*groupsM1
echo Total # of decimal digits = %digits%

:end
pause

Answer 2

I had to rereread the code to see what it is doing. Nice.

You have to face three limits on your code.

1 - In the inner %%j and %%v loop, where buffer is used to multiply the current value in %%i, you face the limit indicated by Magoo. You can not operate with set /a with values greater than 2^31. As the values in the array are limited to 0-9, this means that this limit will not let you calculate factorials of numbers greater than 214748364 (aprox)

2 - There is a limit in the size of a environment variable. It can not hold more than 32767 characters. As you are concatenating the digits to output to console (the next limit is related), this limits you to factorials of numbers below 9273 (aprox).

3 - There is a limit in the length of the lines cmd can handle. It is 8191 characters. This does not limit your calc, but you can not use the method of concatenating in a variable to represent the number. If the method is not changed, this limits you to factorials of numbers below 2727 (aprox).