Fast Division Program

[timbertuck]

Here is a fast division program, with decimal places tested to 4096 (takes about 10 seconds), at 1024 it takes 2-3 seconds and 100 or less it is instantaneous. My Windows Calc only does 32 (and that is in scientific mode), so this program is quite a bit more accurate.

The initial post that prompted this development was a ptyhon program found here: https://github.com/DoctorLai/PyUtils/bl ... er/zDiv.py - so the algorithm credit belongs to him and not me.

file:Divide.cmd
usage: Divide Number Number Precision

Code: Select all

@echo off
echo.
:: catch missing parameters
if "%3"=="" goto help
if "%2"=="" goto help
if "%1"=="" goto help
:: check for positive integers
if not %1 GTR 0 goto help
if not %2 GTR 0 goto help
if not %3 GTR 0 goto help

goto :continue

:help
echo You need three parameters, Top Divisor, Bottom Divisor and ^# of decimal places
echo Example: %0 387 41 20, will divide 387 by 41 out to 20 decimal places. Now you try.
echo Tip: You cannot use a zero "0" for any parameter, all parm's must be positive integers.
goto end

:continue
setlocal enableextensions enabledelayedexpansion

   :: all Variables are self explained 
    set /a TopDiv=%1
    set /a BotDiv=%2
    set /a Precis=%3 + 1
    set /a DivRsl=TopDiv / BotDiv
    set Solution=%TopDiv% / %BotDiv%=%DivRsl%.
  
:DivideMe   
    set /a TopDiv=(TopDiv - DivRsl * BotDiv) * 10
    if "%TopDiv%"=="0" goto Finished
    set /a DivRsl=TopDiv / BotDiv
    set /a Precis=Precis - 1
    if "%Precis%"=="0" goto Finished
    set Solution=%Solution%%DivRsl%
    goto DivideMe
   
:Finished
    for /f "tokens=1-3* delims==."  %%a in ('echo "!Solution!"') do (
      set Problem=%%a
      set Answer=%%b.%%c
      echo The solution to !Problem:~1! is !Answer:~0,-1!
   )
   
endlocal

:end
echo.

I hope that it passes muster!

[Squashman]

I use Judago's math scripts. Will have to put them head to head to see how they each do.
http://judago.webs.com/batchfiles.htm

[Judago]

It will be faster than my scripts for numbers it can handle because I tried to make str_math.bat "just work" with big numbers, floating point and negatives.

My division routine is very inefficient, particularly with a large number of decimal places because it just multiplies the first number by ten(appends a zero) for every decimal place added. I should really replace my routine but I just don't have the time any more.

This routine is very efficient at outputting a large number of decimal places, but can't handle large/floating or negative input as it is.

Still a good job though, very good for high precision output on integers within the limitations of "set /a".

[Squashman]

It will be faster than my scripts for numbers it can handle because I tried to make str_math.bat "just work" with big numbers, floating point and negatives.

My division routine is very inefficient, particularly with a large number of decimal places because it just multiplies the first number by ten(appends a zero) for every decimal place added. I should really replace my routine but I just don't have the time any more.

This routine is very efficient at outputting a large number of decimal places, but can't handle large/floating or negative input as it is.

Still a good job though, very good for high precision output on integers within the limitations of "set /a".

But I like that your divide.bat script provides the remainder(leftover). It comes in quite handy for one of the scripts that I use. Yours is also a little more flexible with the usage.

[timbertuck]

I use Judago's math scripts. Will have to put them head to head to see how they each do.
http://judago.webs.com/batchfiles.htm

Ahh a new place to pillage. Thanks squashman!

[einstein1969]

I have tried.

I think we should always try first to comment.

It seem don't work...

Code: Select all

divide_fast_orig.cmd 1 314159265 40

The solution to 1 / 314159265 is 0.0000000031-5-3-6-1-4-14-66125042455-544362-5-1-5-50-4

the windows's calc return: 3,183098865475127719056765682209e-9

I will try to patch...

einstein1969

[Aacini]

The modification below run much faster:

Code: Select all

@echo off
setlocal EnableDelayedExpansion

:: catch missing parameters
if "%3"=="" goto help

:: check for positive integers
if %1 GTR 0 if %2 GTR 0 if %3 GTR 0 goto continue

:help
echo You need three parameters, Top Divisor, Bottom Divisor and ^# of decimal places
echo Example: %0 387 41 20, will divide 387 by 41 out to 20 decimal places. Now you try.
echo Tip: You cannot use a zero "0" for any parameter, all parm's must be positive integers.
goto :EOF

:continue

:: all Variables are self explained 
set /a TopDiv=%1, BotDiv=%2, Precis=(%3-1)/4 + 1, DivRsl=TopDiv / BotDiv
set Solution=%DivRsl%.

for /L %%d in (1,1,%Precis%) do (
   set /A "TopDiv=(TopDiv - DivRsl * BotDiv) * 10000"
   if "!TopDiv!" equ "0" goto Finished
   set /A DivRsl=TopDiv / BotDiv
   set Rsl=0000!DivRsl!
   set Solution=!Solution!!Rsl:~-4!
)
:Finished

echo The solution to %1 / %2 is %Solution%

However, this method have some limitations. I don't tested it completely, but it seems that the Top Divisor can not be more than 9 digits larger than the Bottom Divisor. If the Bottom Divisor is smaller, it can not be more than 7 digits smaller than the Top Divisor.

Antonio

[einstein1969]

However, this method have some limitations. I don't tested it completely, but it seems that the Top Divisor can not be more than 9 digits larger than the Bottom Divisor. If the Bottom Divisor is smaller, it can not be more than 7 digits smaller than the Top Divisor.

I can't see this.


but I think that I have found the problem.

The initial code and your code multiply the remainder for a quantity.

The initial code for 10 , your code for 10000 (is more fast for this trick).

If the remainder of the integer division multiply for this quantity is greater than 2147483647
than the result is dirty.

In your code for example, if the denominator is less or equal than 214748-50 the problem seem not to be for each numerator.

I don't tested negative operands

>divide_aacini_2.cmd 859002 214751 20
The solution to 859002 / 214751 is 3.9999847712001341-880 exact:(3,99999068688853602544)

>divide_aacini_2.cmd 859001 214751 20
The solution to 859001 / 214751 is 3.99998603033280403816 exact:(3,99998603033280403816)

einstein1969

[Roe5685]

very powerful and impressive.
thank you as a beginner user.
where are other fast math routines located?
i have add up routines for column totals and they are slow!!
not like this!!

[Aacini]

I reviewed my previous method. My first idea was to use groups of 4 digits to achieve the division ("quads", as briefly described in this post). However, in order to complete the division over all digits in just one pass (and not divide the numbers in quads and sum partial results) it is necessary to manage groups of digits of variable length in each iteration, whose length is given by the numbers themselves. The new version below do that.

Code: Select all

@echo off
setlocal EnableDelayedExpansion

rem Divide two integers with unlimited precision result

rem Check parameters
if "%3" equ "" goto help
ver > NUL
set /A TopDiv=%1, BotDiv=%2, Precis=%3  2>NUL
if not errorlevel 1 goto checkBotDiv

:help
echo You need three parameters: Top Divisor, Bottom Divisor and # of decimal places.
echo Example: %0 387 41 20, will divide 387 by 41 out to 20 decimal places.
echo The maximum number (in absolute value) is 2147483647.
goto :EOF

:checkBotDiv
if %BotDiv% neq 0 goto continue

:badNum
echo These numbers can not be divided; change one of them.
if defined Solution echo Partial result: %sign%%Solution%
goto :EOF

:continue
set "sign1=" & set "sign2=" & set "sign="
if "%TopDiv:~0,1%" equ "-" set "sign1=-" & set TopDiv=%TopDiv:~1%
if "%BotDiv:~0,1%" equ "-" set "sign2=-" & set BotDiv=%BotDiv:~1%
if "%sign1%" neq "%sign2%" set "sign=-"
set /A DivRsl=TopDiv / BotDiv, TopDiv-=DivRsl * BotDiv
set "Solution=%DivRsl%."
set "zeros=000000000"

:DivideMe

   if %TopDiv% equ 0 goto Finished
   set digits=0
   for /L %%a in (3,-1,0) do (
       set /A "digits|=1<<%%a"
       for %%b in (!digits!) do if "!TopDiv:~%%b,1!" equ "" set /A "digits&=~1<<%%a"
   )
   set /A digits+=1, wide=9-digits
   if %wide% leq 0 goto badNum
   set /A TopDiv=%TopDiv%!zeros:~%digits%!, DivRsl=TopDiv / BotDiv, TopDiv-=DivRsl * BotDiv, Precis-=wide
   set DivRsl=%zeros%%DivRsl%
   set Solution=%Solution%!DivRsl:~-%wide%!

if %Precis% gtr 0 goto DivideMe

:Finished
echo %sign%%Solution%
goto :EOF

This program may run faster if we change the goto-assembled loop by a while loop when the number of digits is large. However, if the number of digits is small, the startup code of the while loop may be slower than a direct goto-loop. Perhaps we may do a test to find the limit number of decimal digits in order to choose the fastest method in each case...

Antonio