返回列表 发帖
本帖最后由 523066680 于 2019-4-12 10:17 编辑

测试效率和 happy886rr 的大数加法耗时几乎一样。从代码上看,思路都是以更大的基数进行分段处理。
http://www.bathome.net/viewthrea ... mp;page=1#pid195561
set num_a=456456521000210000000000000000874112115674511111111111111110019999999
set num_b=923451344221111111111111111000000000001
for /l %%a in (1,1,6) do set num_a=!num_a!!num_a!
for /l %%a in (1,1,6) do set num_b=!num_b!!num_b!COPY
happy代码测试
@echo off&setlocal enabledelayedexpansion
title By Happy
REM 大数长度
set "MAX=5000" ^位
REM 分割大小
set "K=8"      ^位
set /a CYC=MAX/K
:MAIN
cls
set num_a=456456521000210000000000000000874112115674511111111111111110019999999
set num_b=923451344221111111111111111000000000001
for /l %%a in (1,1,6) do set num_a=!num_a!!num_a!
for /l %%a in (1,1,6) do set num_b=!num_b!!num_b!
set A=%num_a%
set B=%num_b%
REM 优化字符
setlocal
CALL :POINT !A! A N1
CALL :POINT !B! B N2
set /a B1=N1*K
set /a B2=N2*K
echo ======================================
echo 被加数信息:  预估!B1!
echo   加数信息:  预估!B2!
echo ======================================
echo 计算结果
REM 加法核心
if !N1! gtr !N2! (set RM=!N1! &set dx=B) else (set RM=!N2! &set dx=A)
for /l %%i in (1 1 !RM!) do (
if not defined !dx![%%i] (set "!dx![%%i]=00000000")
set /a sum=1!A[%%i]!+1!B[%%i]!+sum
set S=!sum:~-%K%!!S!
set /a sum=!sum:~0,1!-2
)
REM 显示
:DISP
for /l %%i in (1 1 8) do (if "!S:~0,1!"=="0" (set S=!S:~1!))
if "!S!"=="" (set S=0)
echo,!S!
endlocal
goto :eof
REM 分割数位
:POINT
set num=%1
for /l %%i in (1 1 !CYC!) do (
set %2[%%i]=!num:~-%K%!
set num=!num:~0,-%K%!
if "!num!"=="" (
set /a CU=!%2[%%i]!+100000000
set %2[%%i]=!CU:~-%K%!
set /a %3=%%i
goto :eof
)
)COPY
Sublime_text 显示的运行时间 [Finished in 0.6s]

hongrk 的测试代码
@echo off
setlocal enabledelayedexpansion
set num_a=456456521000210000000000000000874112115674511111111111111110019999999
set num_b=923451344221111111111111111000000000001
for /l %%a in (1,1,6) do set num_a=!num_a!!num_a!
for /l %%a in (1,1,6) do set num_b=!num_b!!num_b!
call :jia %num_a% %num_b% P
echo %P%
exit
:jia
setlocal enabledelayedexpansion&set c1=%~1&set c2=%~2&set c=0&set t=
:j
    if %c%==0 (
        if "%c1%"=="" endlocal &set %~3=%c2%%t%&goto :eof
        if "%c2%"=="" endlocal &set %~3=%c1%%t%&goto :eof
    )
    ::此句为“加速版”增添的代码。
    set c1=000000000%c1%
    set c2=000000000%c2%
    set /a t=1!c1:~-9!-1000000000+1!c2:~-9!-1000000000+c,c=0&set c1=!c1:~9,-9!&set c2=!c2:~9,-9!&if "!c1!!c2!"=="" (set t=!t!%t%) else (if not "!t:~9!"=="" set c=1)&set t=00000000!t!&set t=!t:~-9!%t%&goto j
    endlocal&set %~3=%t%&goto :eofCOPY
Sublime_text 显示的运行时间 [Finished in 0.6s]
[url=][/url]

TOP

本帖最后由 523066680 于 2019-4-12 21:54 编辑

循着 Modern Computer Arithmetic 的方案:

β 就是 Base,对于 int32 尺寸的容器可以选 10^9 作为 Base。

也写了一个for版本,其实和已经出现的代码都是差不多的:
@echo off
setlocal enabledelayedexpansion
::constant
set /a BASE=1000000000, LEN=9
set MASK=!BASE:~1!
::test
set num_a=456456521000210000000000000000874112115674511111111111111110019999999
set num_b=923451344221111111111111111000000000001
for /l %%a in (1,1,6) do set num_a=!num_a!!num_a!
for /l %%b in (1,1,6) do set num_b=!num_b!!num_b!
call :plus %num_a% %num_b% sum
echo %sum%
exit /b
:plus
    setlocal enabledelayedexpansion
    set "sum=" & set "va=%1" & set "vb=%2"
    set /a carry=0
    :: 1 to 1000, because max strlen < 8192
    for /l %%a in (1,1,1000) do (
        set /a a=1!va:~-%LEN%, %LEN%!-BASE, b=1!vb:~-%LEN%,%LEN%!-BASE
        set /a t=a+b+carry, carry=t/BASE, head=t
        set t=!MASK!!t!
        set va=!MASK!!va:~0,-%LEN%!
        set vb=!MASK!!vb:~0,-%LEN%!
        if "!va:0=!!vb:0=!" == "" (goto :next)
        set sum=!t:~-%LEN%!!sum!
    )
    :next
    endlocal&set %3=%head%%sum%&goto :eofCOPY
Sublime_Text 显示耗时:[Finished in 0.5s]

各位大神拍砖轻点,批处理这门语言我很久都没学会,经常写出很长很臃肿的代码,所以早就换成其他语言了,语法糖很甜的那种。

补充:
    并不香,写了我也用不着。
以前的那些帖子,过去式,人家也没有那么刻意地去追求速度,实现就足够了。特别地,批处理只是批处理,有自己的定位,
一个连运算符重载都没有的脚本语言,搞四则运算,又要当坠吼的那个 —— 写到 karatsuba 乘法方案的时候你就知道烦了。
4

评分人数

[url=][/url]

TOP

早就脱坑,对我个人而言,没有任何理由再讨论bat。(一句话:我走错片场了
523066680 发表于 2019-4-6 17:41



    真香现场

TOP

回复 17# 523066680


    出门前看到你的回帖,很想立刻回复并改进代码,但时间不够。现在补上。

Bat在效率上天生就不敌很多语言,但毕竟还有能力尽可能追求完美,当然还是想尽量写得好一些。
实用性来讲的话,我目前帖子里的加法函数和除法函数我自己就在用,正好满足需求。不过更多算是练习吧,毕竟Bat算再慢也已经比输入快了啊。

从你的代码里面意识到自己代码里还有一些可以优化的地方,比如进位符的处理,用除法比置0再检测要简洁很多。
还有一个就是那个for指令;我曾也想过用for,因为goto效率确实低些,但for循环不管怎样都要运行完 的特性实在是太不人性了。比如说算一个1+1和算几百位数加减,时间只有1倍左右的差距。happy的代码里用的是先测长度,再根据长度定循环次数,但我觉得那样的话测长度就得费很多时间了,最后还是用了最原始的goto循环。

发现call+goto可以成功跳出for循环。
代码已改进。

TOP

本帖最后由 523066680 于 2019-4-13 12:24 编辑

No.1,你的第三版代码和第二版结果不一致,相同参数
[url=][/url]

TOP

回复 20# 523066680


    我检查了一遍,没发现有错啊。是不是加数有变,我记不清了。

TOP

本帖最后由 523066680 于 2019-4-13 16:13 编辑
use List::MoreUtils qw/pairwise mesh/;
my ($f1, $f2) = ("hongrk2.bat", "hongrk3.bat");
my @s1 = `$f1`;
my @s2 = `$f2`;
my @foo = unpack("(A40)*", $s1[1]);
my @bar = unpack("(A40)*", $s2[1]);
printf "%40s   %40s\n", $f1, $f2;
pairwise { printf "%s %s %s\n", $a, $a eq $b?" ":"!", $b } @foo, @bar;COPY
                             hongrk2.bat                                hongrk3.bat
4564565210002100000000000000008741121156   4564565210002100000000000000008741121156
7451111111111111111001999999945645652100   7451111111111111111001999999945645652100
0210000000000000000874112115674511111111   0210000000000000000874112115674511111111
1111111100199999994564565210002100000000   1111111100199999994564565210002100000000
0000000087411211567451111111111111111001   0000000087411211567451111111111111111001
9999999456456521000210000000000000000874   9999999456456521000210000000000000000874
1121156745111111111111111100199999994564   1121156745111111111111111100199999994564
5652100021000000000000000087411211567451   5652100021000000000000000087411211567451
1111111111111110019999999456456521000210   1111111111111110019999999456456521000210
0000000000000008741121156745111111111111   0000000000000008741121156745111111111111
1111001999999945645652100021000000000000   1111001999999945645652100021000000000000
0000874112115674511111111111111110019999   0000874112115674511111111111111110019999
9994564565210002100000000000000008741121   9994564565210002100000000000000008741121
1567451111111111111111001999999945645652   1567451111111111111111001999999945645652
1000210000000000000000874112115674511111   1000210000000000000000874112115674511111
1111111111100199999994564565210002100000   1111111111100199999994564565210002100000
0000000000087411211567451111111111111111   0000000000087411211567451111111111111111
0019999999456456521000210000000000000000   0019999999456456521000210000000000000000
8741121156745111111111111111100199999994   8741121156745111111111111111100199999994
5645652100021000000000000000087411211567   5645652100021000000000000000087411211567
4511111111111111110019999999456456521000   4511111111111111110019999999456456521000
2100000000000000008741121156745111111111   2100000000000000008741121156745111111111
1111111001999999945645652100021000000000   1111111001999999945645652100021000000000
0000000874112115674511111111111111110019   0000000874112115674511111111111111110019
9999994564565210002100000000000000008741   9999994564565210002100000000000000008741
1211567451111111111111111001999999945645   1211567451111111111111111001999999945645
6521000210000000000000000874112115674511   6521000210000000000000000874112115674511
1111111111111100199999994564565210002100   1111111111111100199999994564565210002100
0000000000000087411211567451111111111111   0000000000000087411211567451111111111111
1110019999999456456521000210000000000000   1110019999999456456521000210000000000000
0008741121156745111111111111111100199999   0008741121156745111111111111111100199999
9945645652100021000000000000000087411211   9945645652100021000000000000000087411211
5674511111111111111110019999999456456521   5674511111111111111110019999999456456521
0002100000000000000008741121156745111111   0002100000000000000008741121156745111111
1111111111001999999945645652100021000000   1111111111001999999945645652100021000000
0000000000874112115674511111111111111110   0000000000874112115674511111111111111110
0199999994564565210002100000000000000008   0199999994564565210002100000000000000008
7411211567451111111111111111001999999945   7411211567451111111111111111001999999945
6456521000210000000000000000874112115674   6456521000210000000000000000874112115674
5111111111111111100199999994564565210002   5111111111111111100199999994564565210002
1000000000000000087411211567451111111111   1000000000000000087411211567451111111111
1111110019999999456456521000210000000000   1111110019999999456456521000210000000000
0000008741121156745111111111111111100199   0000008741121156745111111111111111100199
9999945645652100021000000000000000087411   9999945645652100021000000000000000087411
2115674511111111111111110019999999456456   2115674511111111111111110019999999456456
5210002100000000000000008741121156745111   5210002100000000000000008741121156745111
1111111111111001999999945645652100021000   1111111111111001999999945645652100021000
0000000000000874112115674511111111111112   0000000000000874112115674511111111111112
0334713442205675676321113210000000000019   0334713442205675676321113210000000000019
2432545633678562222222222211111002000192 ! 2432545633678562222222222211111001900192
2907800742111321111111111000000874114039 ! 2907800742111321111111111000000874114038
1258553322222222222211309999994564584444 ! 1258553322222222222211309999994564574444
5155422111111111111198511211567451303456   5155422111111111111198511211567451303456
2455332221131111110567456521000211923451   2455332221131111110567456521000211923451
3442211119852232267855111111111130345613 ! 3442211119852232267855111111111120345613
6422111056756763211121000000000192345221 ! 6322111056756763211121000000000192345121
8333226785622222222111111110021923450800 ! 8333226785622222222111111110021922450800
6776321113211111110000000008760355670187 ! 6776321113211111110000000008750355670187
3222222222222222101999999945837997234443   3222222222222222101999999945837997234443
1111111111111111874112115676434562455332   1111111111111111874112115676434562455332
2222211311111104564565210021334513442211 ! 2222211301111104564565210011334513442211
1111198522322667451111111303456245424111   1111198522322667451111111303456245424111
1110567567632000210000001923451345095223 ! 0110567567632000210000001923451345095223
2267856222221111111111119434513436775676   2267856222221111111111119434513436775676
3211132111100000000000279756345989562222   3211132111100000000000279756345989562222
2222222222110020000001379907865221321111 ! 2222222222110019000001379907865221321111
1111111110008741121175979624553322222222 ! 1111111110008741121165979624553322222222
2113111099945645652292366134422111111111   2113111099945645652292366134422111111111
1985223115674511113034562455331131111110   1985223115674511113034562455331131111110
5675675210002100019234513442219852232267   5675675210002100019234513442219852232267
8562211111111111303347134422056756763211 ! 8562211111111111303347034422056756763211
1321000000000001924325456336785622222222 ! 1321000000000001923325456336785622222222
2221111100200019229078007421113211111111 ! 2221111100200009229078007421113211111111
1100000087411403912585533222222222222113   1100000087411403912585533222222222222113
0999999456458444451554221111111111111985   0999999456458444451554221111111111111985
1121156745130345624553322211311111105674 ! 1121156745120345624553322211301111105674
5652100021192345134422111198522322678551   5652100021192345134422111198522322678551
1111111113034561364221110567567632111210 ! 1111111113034561364220110567567632111210
0000000019234522183332267856222222221111   0000000019234522183332267856222222221111
1111002192345080067763211132111111100000   1111002192345080067763211132111111100000
0000876035567018732222222222222221019999   0000876035567018732222222222222221019999
9994583799723444311111111111111118741121 ! 9994573799723444311111111111111118741121
1567643456245533222222113111111045645652 ! 1567643456245533222222113111011045645652
1002133451344221111111985223226674511111   1002133451344221111111985223226674511111
1130345624542411111105675676320002100000 ! 1120345624542411111105675676320002100000
0192345134509522322678562222211111111111   0192345134509522322678562222211111111111
1943451343677567632111321111000000000002 ! 1942451343677567632111321111000000000001
7975634598956222222222222221100200000013 ! 7975634598956222222222222221100199990013
7990786522132111111111111100087411211759   7990786522132111111111111100087411211759
7962455332222222221131110999456456522923   7962455332222222221131110999456456522923
6613442211111111119852231156745111130345   6613442211111111119852231156745111130345
6245533113111111056756752100021000192345 ! 6245533113011111056756752100021000192345
1344221985223226785622111111111113033471 ! 1344221985223226785622111111111112033471
3442205675676321113210000000000019243254 ! 3432205675676321113210000000000019243254
5633678562222222222211111002000192290780   5633678562222222222211111002000192290780
0742111321111111111000000874114039125855 ! 0742111321111111111000000874113039125855
3322222222222211309999994564584444515542   3322222222222211309999994564584444515542
2111111111111198511211567451303456245533   2111111111111198511211567451303456245533
2221131111110567456521000211923451344221 ! 2221131110110567456521000211923451344221
1119852232267855111111111130345613642211   1119852232267855111111111130345613642211
1056756763211121000000000192345221833322   1056756763211121000000000192345221833322
6785622222222111111110021923450800677632 ! 6785622222222111111110020923450800677632
1113211111110000000008760355670187322222 ! 1113211111110000000008760355660187322222
2222222222101999999945837997234443111111   2222222222101999999945837997234443111111
1111111111874112115676434562455332222221 ! 1111111111874112115675434562455332222221
1311111104564565210021334513442211111119   1311111104564565210021334513442211111119
8522322667451111111303456245424111111056 ! 8522322667451111111303456245424011111056
7567632000210000001923451345095223226785 ! 7567632000210000001923451344095223226785
6222221111111111119434513436775676321113 ! 6222221111111111119434503436775676321113
2111100000000000279756345989562222222222   2111100000000000279756345989562222222222
2222110020000000   2222110020000000COPY
[url=][/url]

TOP

本帖最后由 523066680 于 2019-4-13 21:48 编辑

写了一个很冗长的版本,按之前的测试数值 4416位数 + 2496位数,耗时200ms
顺带用其他脚本写了一个效率和准确性测试,
use Time::HiRes qw/time/;
use bigint 'a'=>9000;
STDOUT->autoflush(1);
srand(1);
for (1..50) { check() }
sub check
{
    my $a = int(rand(9))+1 .join "", map { int(rand(10)) } ( 1 .. rand(4100) );
    my $b = int(rand(9))+1 .join "", map { int(rand(10)) } ( 1 .. rand(4100) );
    if ( length($b) > length($a) ) { ($a, $b) = ($b, $a); }
    my $ta = time();
    my $res = `plus_vec4.bat $a $b`;
    my $dt = time()-$ta;
    my $check = (0+$a)+$b;
    $res =~s/\r?\n$//;
    if ( $res eq $check ) {
        printf "%4d, %4d, correct, %.2f\n", length($a), length($b), $dt;
    } else {
        printf "%4d, %4d, wrong, %.2f\n", length($a), length($b), $dt;
    }
}COPY
左边是两个数值的长度,最右是耗时
3327, 1864, correct, 0.17s
2627, 2125, correct, 0.13s
4067, 1529, correct, 0.20s
3224,  558, correct, 0.16s
1716,    7, correct, 0.08s
4056, 3309, correct, 0.22s
2429,  566, correct, 0.12s
717,  443, correct, 0.04s
3880, 2849, correct, 0.20s
2459,   95, correct, 0.12s
1212,  998, correct, 0.06s
3908, 1325, correct, 0.19s
3219,  392, correct, 0.15s
3483, 1089, correct, 0.17s
137,    9, correct, 0.04s
2306, 2297, correct, 0.12s
2308, 1083, correct, 0.12s
3207, 1677, correct, 0.16s
1919, 1862, correct, 0.09s
1071,   14, correct, 0.05s
3823, 3439, correct, 0.20s
3750,  448, correct, 0.18s
2067, 1724, correct, 0.10s
1565, 1469, correct, 0.07s
2388, 2052, correct, 0.12s
2271, 1209, correct, 0.11s
2642,  403, correct, 0.12s
2352, 1198, correct, 0.11s
4087, 2076, correct, 0.21s
1917,  349, correct, 0.08s
3579,  882, correct, 0.17s
2276, 1315, correct, 0.11s
3243, 2225, correct, 0.17s
735,  543, correct, 0.04s
3111, 2193, correct, 0.16s
2992, 1849, correct, 0.15s
3672, 3562, correct, 0.20s
3729, 1593, correct, 0.18s
4000, 3199, correct, 0.22s
3888, 2476, correct, 0.20s
2899, 1969, correct, 0.15s
2548, 1586, correct, 0.13s
3407,  383, correct, 0.16s
2608,  210, correct, 0.13s
4022,  792, correct, 0.19s
4022, 1176, correct, 0.20s
3376, 2227, correct, 0.17s
1978,   84, correct, 0.09s
1510,  304, correct, 0.07s
2602, 1592, correct, 0.13sCOPY
最后,随手写一个 50000 位随机数相加,我写的很冗长
use bigint;
srand(1);
my $gener = sub { int(rand(9))+1 .join "", map {int(rand(10))} (2 .. shift) };
my $a = $gener->(50000);
my $b = $gener->(50000);
print 0+$a+$b;COPY
[url=][/url]

TOP

回复 22# 523066680


    第二版试了好几次,都是提示过长闪退,不知道具体结果多少。不过在你给出的2个结果中,第三版的那个是对的,是第二版错了。

自然,其他语言快得多也方便得多;但目前我还只想先练好Bat。发出来主要还是想让别人指出问题方便改进,而这点基本达到了。肯定迟早会去试着用其他语言,但顺其自然吧。至少先把手头的做掉

TOP

回复 22# 523066680


    后来更新的时候发现确实是有问题,很抱歉。不过已经处理好了。
二分法数位数的效率极佳,而goto循环的效率极差,二者相较下,采取数位以便改用for循环才是最合适的,我之前的想法有些偏颇。
改写后的代码计算之前那个例子,1次所需时间在110-120ms左右,有四五倍的提升。
1

评分人数

TOP

返回列表