Board logo

标题: 批处理:素数堆垒及哥德巴赫猜想局部验证 [打印本页]

作者: willsort     时间: 2004-12-6 00:00    标题: 批处理:素数堆垒及哥德巴赫猜想局部验证

To All:
    这个程序是一个批处理程序设计数学问题的一个典型代表,它可以提供给我们一个解决一类问题的方式和方法。源程序来自比利时的一位编程专家,我对它进行了性能上的修改,核心算法思想基本不变。
   为了便于比较,我将更改的各个版本按顺序贴出,大家基本上可以看到改进一个程序尤其于批处理程序的性能,所能应用的一些方法和技巧。
    所有的代码版本及性能测试环境可以从此下载。打开附件

[此贴子已经被作者于2004-12-6 11:17:44编辑过]



作者: willsort     时间: 2004-12-6 00:00
:: Prime.bat - Generate a serial prime number
:: Dirk van Deun - Will Sort Modified 2004/11/18
::
:: 改进: 将源码的所有函数并入主程序中并套了个控制性外壳
:: 效果: 程序文件减少, 运行速度没有明显变化, 测试运行时间超过6分钟
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:5000 /c %0 $ run
goto end:: 对整数 %prime-in% (2 to n) 调用素数判断(prime)进程
:: 若返回真值(素数)则显示此整数, 否则跳过
:run
set prime-num=
set prime-in=I I
:runloop
call %0 $ isprime
if "%prime-out%"=="true" echo %prime-in%
if "%prime-out%"=="true" set prime-num=I%prime-num%
if "%prime-num%"=="IIIIIIIIII" goto end
set prime-in=I %prime-in%
goto runloop:: 对传入的整数 %prime-in% 从n-1到2循环调用除法(divide)函数
:: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法
:isprime
call %0 $ dec %prime-in%
:isprimeloop
set dividend=%prime-in%
set divisor=%dec-out%
call %0 $ dec %dec-out%
if "%dec-out%"=="" set prime-out=true
if "%dec-out%"=="" goto end
call %0 $ divide
if %div-out%==true set prime-out=false
if %div-out%==true goto end
call %0 $ dec %divisor%
goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 递归调用减法函数
:: 若减为零则返回真(整除), 若下溢则返回假, 否则继续递归减法
:divide
if "%dividend%"=="" set div-out=true
if "%dividend%"=="" goto end
set min-in1=%dividend%
set min-in2=%divisor%
call %0 $ minus
if "%min-err%"=="underflow" set div-out=false
if "%min-err%"=="underflow" goto end
set dividend=%min-out%
%0 $ divide:: 对传入的 %min-in1%(被减数) %min-in2%(减数) 递归调用自减函数
:: 若 %min-in2% 为0则无错返回, 若 %min-in1% 为0则返回下溢错(%min-err%)
:: 否则继续递归自减
:minus
if "%min-in2%"=="" set min-out=%min-in1%
if "%min-in2%"=="" set min-err=
if "%min-in2%"=="" goto end
if "%min-in1%"=="" set min-err=underflow
if "%min-in1%"=="" goto end
call %0 $ dec %min-in1%
set min-in1=%dec-out%
call %0 $ dec %min-in2%
set min-in2=%dec-out%
%0 $ minus:: 对传入的整数 %3 %4 %5... 进行自减操作
:: 将整数减一后存入 %dec-out% 中返回
:dec
set dec-out=%4
:decloop
shift
if "%4"=="" goto end
set dec-out=%dec-out% %4
goto decloop:end

作者: willsort     时间: 2004-12-6 00:00
:: Prime.bat - Generate a serial prime number
:: Dirk van Deun - Will Sort Modified 2004/11/18
::
:: 改进: 将主循环起始值改为3, 步进值改为2, 也即只判断大于2的奇数
:: 效果: 理论上速度应增加一倍, 实际运行时间4分钟多
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:5000 /c %0 $ run
goto end:: 对整数 %prime-in% (3 to n step 2) 调用素数判断(prime)进程
:: 若返回真值(素数)则显示此整数, 否则跳过
:run
echo I I
set prime-num=I
set %prime-num%=I I
set prime-in=I I I
:runloop
call %0 $ isprime
if "%prime-out%"=="true" echo %prime-in%
if "%prime-out%"=="true" set prime-num=I%prime-num%
if "%prime-num%"=="IIIIIIIIII" goto end
if "%prime-out%"=="true" set %prime-num%=%prime-in%
set prime-in=I I %prime-in%
goto runloop:: 对传入的整数 %prime-in% 从n-1到2循环调用除法(divide)函数
:: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法
:isprime
call %0 $ dec %prime-in%
:isprimeloop
set dividend=%prime-in%
set divisor=%dec-out%
call %0 $ dec %dec-out%
if "%dec-out%"=="" set prime-out=true
if "%dec-out%"=="" goto end
call %0 $ divide
if %div-out%==true set prime-out=false
if %div-out%==true goto end
call %0 $ dec %divisor%
goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 递归调用减法函数
:: 若减为零则返回真(整除), 若下溢则返回假, 否则继续递归减法
:divide
if "%dividend%"=="" set div-out=true
if "%dividend%"=="" goto end
set min-in1=%dividend%
set min-in2=%divisor%
call %0 $ minus
if "%min-err%"=="underflow" set div-out=false
if "%min-err%"=="underflow" goto end
set dividend=%min-out%
%0 $ divide:: 对传入的 %min-in1%(被减数) %min-in2%(减数) 递归调用自减函数
:: 若 %min-in2% 为0则无错返回, 若 %min-in1% 为0则返回下溢错(%min-err%)
:: 否则继续递归自减
:minus
if "%min-in2%"=="" set min-out=%min-in1%
if "%min-in2%"=="" set min-err=
if "%min-in2%"=="" goto end
if "%min-in1%"=="" set min-err=underflow
if "%min-in1%"=="" goto end
call %0 $ dec %min-in1%
set min-in1=%dec-out%
call %0 $ dec %min-in2%
set min-in2=%dec-out%
%0 $ minus:: 对传入的整数 %3 %4 %5... 进行自减操作
:: 将整数减一后存入 %dec-out% 中返回
:dec
set dec-out=%4
:decloop
shift
if "%4"=="" goto end
set dec-out=%dec-out% %4
goto decloop:end

作者: willsort     时间: 2004-12-6 00:00
:: Prime.bat - Generate a serial prime number
:: Dirk van Deun - Will Sort Modified 2004/11/18
::
:: 改进: 判断素数时, 不再除以从2到n-1的所有数, 改为从2到n-1的所有素数
:: 效果: 理论上速度将得到数量级的提升, 测试运行时间约1分钟
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:5000 /c %0 $ run
del ~prime.bat
goto end:: 对整数 %prime-in% (3 to n step 2) 调用素数判断(prime)进程
:: 若返回真值(素数)则显示此整数, 否则跳过
:run
echo I I
set prime-num=I
set %prime-num%=I I
set prime-in=I I I
:runloop
call %0 $ isprime
if "%prime-out%"=="true" echo %prime-in%
if "%prime-out%"=="true" set prime-num=I%prime-num%
if "%prime-num%"=="IIIIIIIIII" goto end
if "%prime-out%"=="true" set %prime-num%=%prime-in%
set prime-in=I I %prime-in%
goto runloop:: 将传入的整数 %prime-in% 与已知的所有素数循环相除(调用divide函数)
:: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法
:isprime
set divisor-no=I
:isprimeloop
set dividend=%prime-in%
echo set divisor=%%%divisor-no%%%>~prime.bat
call ~prime.bat
::echo %prime-in% - %divisor-no% : %dividend% / %divisor%
::pause
call %0 $ divide
if %div-out%==true set prime-out=false
if %div-out%==true goto end
if "%divisor-no%"=="%prime-num%" set prime-out=true
if "%divisor-no%"=="%prime-num%" goto end
set divisor-no=I%divisor-no%
goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 递归调用减法函数
:: 若减为零则返回真(整除), 若下溢则返回假, 否则继续递归减法
:divide
if "%dividend%"=="" set div-out=true
if "%dividend%"=="" goto end
set min-in1=%dividend%
set min-in2=%divisor%
call %0 $ minus
if "%min-err%"=="underflow" set div-out=false
if "%min-err%"=="underflow" goto end
set dividend=%min-out%
%0 $ divide:: 对传入的 %min-in1%(被减数) %min-in2%(减数) 递归调用自减函数
:: 若 %min-in2% 为0则无错返回, 若 %min-in1% 为0则返回下溢错(%min-err%)
:: 否则继续递归自减
:minus
if "%min-in2%"=="" set min-out=%min-in1%
if "%min-in2%"=="" set min-err=
if "%min-in2%"=="" goto end
if "%min-in1%"=="" set min-err=underflow
if "%min-in1%"=="" goto end
call %0 $ dec %min-in1%
set min-in1=%dec-out%
call %0 $ dec %min-in2%
set min-in2=%dec-out%
%0 $ minus:: 对传入的整数 %3 %4 %5... 进行自减操作
:: 将整数减一后存入 %dec-out% 中返回
:dec
set dec-out=%4
:decloop
shift
if "%4"=="" goto end
set dec-out=%dec-out% %4
goto decloop:end

作者: willsort     时间: 2004-12-6 00:00
:: Prime.bat - Generate a serial prime number
:: Dirk van Deun - Will Sort Modified 2004/11/18
::
:: 改进: 将除法函数的递归相减算法改为循环相减算法
:: 效果: 代码和call语句减少, 速度提升量与系统相关, 测试运行时间约 2.1s
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:5000 /c %0 $ run
del ~prime.bat
goto end:: 对整数 %prime-in% (3 to n step 2) 调用素数判断(prime)进程
:: 若返回真值(素数)则显示此整数, 否则跳过
:run
echo I I
set prime-num=I
set %prime-num%=I I
set prime-in=I I I
:runloop
call %0 $ isprime
if "%prime-out%"=="true" echo %prime-in%
if "%prime-out%"=="true" set prime-num=I%prime-num%
if "%prime-num%"=="IIIIIIIIII" goto end
if "%prime-out%"=="true" set %prime-num%=%prime-in%
set prime-in=I I %prime-in%
goto runloop:: 将传入的整数 %prime-in% 与已知的所有素数循环相除(调用divide函数)
:: 若整除则返回假(非素数), 若 %prime-in% 为1则返回真, 否则继续循环除法
:isprime
set divisor-no=I
:isprimeloop
set dividend=%prime-in%
echo set divisor=%%%divisor-no%%%>~prime.bat
call ~prime.bat
::echo %prime-in% - %divisor-no% : %dividend% / %divisor%
::pause
call %0 $ divide
if %div-out%==true set prime-out=false
if %div-out%==true goto end
if "%divisor-no%"=="%prime-num%" set prime-out=true
if "%divisor-no%"=="%prime-num%" goto end
set divisor-no=I%divisor-no%
goto isprimeloop:: 对传入的 %dividend%(被除数) %divisor%(除数) 调用循环减法函数
:: 若下溢则返回假, 否则返回真(整除)
:divide
call %0 $ minus %dividend%
set div-out=true
if "%min-out%"=="underflow" set div-out=false
goto end:: 对传入的 %dividend%(被除数) %divisor%(除数) 循环相减
:: 若不足相减 (%2!=I) 则返回下溢错, 否则直接返回空
:minus
::echo %3 %4 %5 %6
for %%n in (%divisor%) do shift
if not [%3]==[] goto minus
set min-out=
if [%2]==[] set min-out=underflow
::echo min-out: %min-out%
::pause
goto end:end

作者: willsort     时间: 2004-12-6 00:00

:: Prime.bat - Generate a serial prime number
:: Dirk van Deun - Will Sort Modified 2004/11/18
::
:: 改进: 将isprime和divided函数并入主函数以及其他一些风格上的改进
:: 效果: 函数,变量和代码均减少, 速度继续提升; 测试运行时间约 1.6秒
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:5000 /c %0 $ init
del ~prime.bat
goto end
:: 初始化: 产生素数2, 将它存为第一个素数, 设置循环起始值
:init
echo I I
set prime-num=I
set %prime-num%=I I
set prime-in=I
:: 对3~n的奇数 %prime-in% 与已产生的所有素数由小到大循环相除
:: 若全部未整除则显示此整数, 否则递增 %prime-in% 后继续循环
:runloop
set prime-in=I I %prime-in%
set divisor-no=I
    :divideloop
    echo set divisor=%%%divisor-no%%%>~prime.bat
    call ~prime.bat
    call %0 $ loopminus %prime-in%
    if "%min-out%"=="" goto runloop
    if "%divisor-no%"=="%prime-num%" goto isprime
    set divisor-no=I%divisor-no%
    goto divideloop
:isprime
echo %prime-in%
set prime-num=I%prime-num%
if "%prime-num%"=="IIIIIIIIII" goto end
set %prime-num%=%prime-in%
goto runloop
:: 对传入的 %dividend%(被除数) %divisor%(除数) 循环相减
:: 若不足相减 (%2!=I) 则返回下溢错, 否则直接返回空
:loopminus
for %%n in (%divisor%) do shift
if not [%3]==[] goto loopminus
set min-out=
if [%2]==[] set min-out=underflow
goto end
:end
───────────────── 版务记录 ─────────────────
执行:HAT
操作:[2009-04-24]由于willsort兄贴代码时未使用code标签,论坛解析代码时出现不少错误,现予以修正。
───────────────── 版务记录 ─────────────────


[ Last edited by HAT on 2009-4-24 at 12:16 ]
作者: willsort     时间: 2004-12-6 00:00
:: Prime.bat - Generate a serial prime number
:: Dirk van Deun - Will Sort Modified 2004/11/18
::
:: Contents of reference:
:: A system of batch files that generates prime numbers in "prisoners
:: notation". (It's rather sloooooooow.) END.BAT is really an empty
:: file, by the way.
:: http://student.vub.ac.be/~dvandeun
::
:: 素数堆垒程序修改版: 一个产生素数的程序, 因为其输出形似堆垒而名
::
:: 源代码正如上文所说,非常的慢,所以不得不做了一些修改
::
:: 主要的修改:
:: 1 将源码的所有函数并入主程序中, 加套控制性外壳
:: 2 将主循环起始值改为3, 步进值改为2, 也即只判断大于2的奇数
:: 3 判断素数时, 不再除以从2到n-1的所有数, 改为从2到n-1的所有素数
:: 4 将除法函数的递归相减算法改为循环相减算法
:: 5 将素数判断循环和除法循环并入主循环
:: 6 变量名, 标签名, 注释, 缩进等代码风格上的改动
::
:: 环境变量说明:
:: iTest:测试数, iPrime:素数序号
:: divisor:用以判断素数的除数, iDivisor:除数序号
:: less: 除法中不足除的标志
::
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:4096 /c %0 $ init
del ~prime.bat
goto end:: 初始化: 产生素数2, 将它存为第一个素数, 设置循环起始值为3
:init
set iTest=I
set iPrime=I
set %iPrime%=I I
echo I I:: 对3~n的奇数 %iTest% 与已产生的所有素数由小到大循环相除
:: 若全部未整除则显示此整数, 否则递增 %iTest% 后继续循环
:MainLoop
set iTest=I I %iTest%
set iDivisor=I
rimeLoop
echo set divisor=%%%iDivisor%%%>~prime.bat
call ~prime.bat
call %0 $ Divide %iTest%
if "%less%"=="" goto MainLoop
if "%iDivisor%"=="%iPrime%" goto IsPrime
set iDivisor=I%iDivisor%
goto PrimeLoop
:IsPrime
echo %iTest%
set iPrime=I%iPrime%
if "%iPrime%"=="IIIIIIIIIIII" goto end
set %iPrime%=%iTest%
goto MainLoop:: 将传入的被除数 %iTest% 除以(循环减)除数 %divisor%
:: 若不足除 (无法整除) 则返回不足信号 less, 否则直接返回
ivide
for %%n in (%divisor%) do shift
if not [%3]==[] goto Divide
set less=
if [%2]==[] set less=true
goto end:end

作者: willsort     时间: 2004-12-6 00:00

:: Solve.bat - 验证哥德巴赫猜想的程序
:: Will Sort - 2004/11/18
::
:: 从素数堆垒程序变化而来
:: 环境变量说明:
::   iTest:测试数, iPrime:素数序号
::   divisor:用以判断素数的除数, iDivisor:除数序号
::   Factor1&Factor2: 偶数的两个分解因子, iFactor1&iFicator2:因子序号
::   less: 除法中不足除的标志, diff: 减法中有差值的标志
::
@echo off
if [%1]==[$] goto %2
if [%1]==[] %comspec% /e:4096 /c %0 $ init
del ~Solve.bat
goto end
:: 初始化: 产生素数2, 将它存为第一个素数, 设置循环起始值为3
:init
set iTest=I I
set iPrime=I
set %iPrime%=I I
:: 对3~n的奇数 %iTest% 与已产生的所有素数由小到大循环相除
:: 若全部未整除则将 %iTest% 存入素数 %iPrime%, 否则跳至 Solve
:: 对3~n的偶数 %iTest% 分解为已产生的两个素数之和
:: 若恰好分解则显示此偶数和两个分解因子, 否则继续循环 MainLoop
:MainLoop
:Prime - 判断奇数是否为素数
set iTest=I %iTest%
set iDivisor=I
    :PrimeLoop
    echo set divisor=%%%iDivisor%%%>~Solve.bat
    call ~Solve.bat
    call %0 $ Divide %iTest%
    if "%less%"=="" goto Solve
    if "%iDivisor%"=="%iPrime%" goto IsPrime
    set iDivisor=I%iDivisor%
    goto PrimeLoop
:IsPrime
set iPrime=I%iPrime%
set %iPrime%=%iTest%
:Solve - 将偶数分解为素数之和
set iTest=I %iTest%
set iFactor1=
    :SolveLoop
    set iFactor1=I%iFactor1%
    if "%iFactor1%"=="I%iPrime%" goto SolveLoop
    set iFactor2=%iFactor1%
        :SolveSubLoop
        if "%iFactor2%"=="I%iPrime%" goto SolveLoop
        echo set Factor1=%%%iFactor1%%%>~Solve.bat
        echo set Factor2=%%%iFactor2%%%>>~Solve.bat
        call ~Solve.bat
        call %0 $ Minus %iTest%
        if "%diff%"=="" goto IsSolve
        set iFactor2=I%iFactor2%
        goto SolveSubLoop
:IsSolve
echo %iTest%
echo %Factor1% + %Factor2%
if "%iPrime%"=="IIIIIIIII" goto end
goto MainLoop
:: 将传入的被除数 %iTest% 除以(循环减)除数 %divisor%
:: 若不足除 (无法整除) 则返回不足信号 less, 否则直接返回
:Divide
for %%n in (%divisor%) do shift
if not [%3]==[] goto Divide
set less=
if [%2]==[] set less=true
goto end
:: 将传入的被减数 %iTest% 减去减数 %Factor1% 和 %Factor2%
:: 若有差值 (无法分解) 则返回相差信号 diff, 否则直接返回
:Minus
for %%n in (%Factor1%) do shift
for %%n in (%Factor2%) do shift
set diff=
if "%2"=="" set diff=true
if not "%3"=="" set diff=true
goto end
:end
───────────────── 版务记录 ─────────────────
执行:HAT
操作:[2009-04-24]由于willsort兄贴代码时未使用code标签,论坛解析代码时出现不少错误,现予以修正。
───────────────── 版务记录 ─────────────────


[ Last edited by HAT on 2009-4-24 at 12:22 ]