[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖
本帖最后由 523066680 于 2019-1-13 19:07 编辑

回复 33# SQYSQYSQY

是的哟,if 在某些情况下会进行字符串对比。bbbbbbbbbbbbbbb gtr aaaaaaaaaaaaaaa 是成立的,换成数字,只要长度相同就会得到对的结果

42行是我用来校验结果是否正确的,调用 Perl 显示对应的开根结果。要正确执行需要安装 Perl 环境。
http://strawberryperl.com/releases.html 这玩意儿好像都不自带环境配置,装完还要自己把perl.exe执行路径添加到PATH中

对应的校验语句是临时注释掉的:
rem call :check_first %1 !precision!

TOP

本帖最后由 523066680 于 2019-1-9 09:40 编辑

改好了,去掉了二分搜索,5位以内的情况下粗暴遍历。
通过0到100的数字开根测试,支持大数字。在这个基础上再去优化会舒服很多,但还是要做出浮点数开根以后再说。

CPU: i7 4GHz
SQRT 2 精度 80 耗时约 2.3s。精度 300,耗时约 20s
  1. :: Bignum(integer) Square Root, Decimal Solution
  2. :: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Decimal_(base_10)
  3. :: 523066680/vicyang
  4. :: 2019-01
  5. @echo off
  6. setlocal enabledelayedexpansion
  7. :init
  8.     rem 创建用于计算字符串长度的模板,长度限制为 2^pow
  9.     set "sharp=#"
  10.     set "serial=9876543210"
  11.     set /a pow=11, maxlen=1^<^<pow
  12.     for /l %%a in (1,1,%pow%) do set sharp=!sharp!!sharp!
  13. set precision=80
  14. rem call :check_one 2
  15. call :check_all
  16. pause
  17. exit /b
  18. :: 独立测试
  19. :check_one
  20.     set ta=!time!
  21.     rem call :check_first %1 !precision!
  22.     call :decimal_solution %1
  23.     call :time_delta !ta! !time! tu
  24.     echo time used: !tu!
  25.     goto :eof
  26. :: 批量测试
  27. :check_all
  28.     for /l %%a in (1,1,99) do (
  29.         echo test number: %%a
  30.         rem call :check_first %%a !precision!
  31.         call :decimal_solution %%a
  32.         echo,
  33.     )
  34.     goto :eof
  35. :: 使用其他工具校验/对比结果
  36. :check_first
  37.     perl -Mbignum=p,-%2 -le "print sqrt(%1)" 2>nul
  38.     goto :eof
  39. :: 手算开根方案
  40. :decimal_solution
  41.     setlocal
  42.     set num=%1
  43.     set tnum=%1
  44.     :: 计算长度,判断需要截取的目标长度(1 or 2)
  45.     call :length %num% len
  46.     set /a mod=len %% 2, skip = 2 - mod
  47.     set target=!tnum:~0,%skip%!
  48.     set tnum=!tnum:~%skip%!
  49.     set "base="
  50.     :: prec 当前精度
  51.     set /a prec = 0, base_len=0, target_len=skip
  52.     :dec_loop
  53.         :: 推算下一个数
  54.         :estimate
  55.             :: 如果目标值 小于 基数,下一个数字判定为0
  56.             call :cmp %target% %base%0 %target_len% %base_len%+1 cmp
  57.             if !cmp! equ -1 (
  58.                 set /a mid=0, mp=0, mplen=0
  59.                 goto :out_estimate
  60.             )
  61.             if %base_len% gtr 5 (
  62.                 set /a est=!target:~0,6!/!base:~0,5!
  63.             ) else (
  64.                 :: 在set/a计算范围内的,[粗暴]遍历
  65.                 for /l %%a in (0,1,10) do (
  66.                     set /a mp=%base%%%a*%%a
  67.                     if !mp! gtr !target! (set /a est=%%a-1 &goto :out_est_for)
  68.                 )
  69.             )
  70.             :out_est_for
  71.             :: 199999996400/1999999988 = 99.9999988
  72.             :: but 199999/19999 = 10
  73.             if %est% geq 10 (
  74.                 set /a tbase_len=base_len+1
  75.                 if !target_len! gtr !tbase_len! (set /a est=9)
  76.             )
  77.             set /a mid=!est:~0,1!
  78.             call :bignum_mp_single !base!!mid! !mid! !base_len!+1 1 mp mplen
  79.             call :cmp !mp! !target! !mplen! !target_len! cmp
  80.             :: 如果mp超出目标范围
  81.             if !cmp! equ 1 (
  82.                 set /a mid-=1
  83.                 call :bignum_mp_single !base!!mid! !mid! !base_len!+1 1 mp mplen
  84.             )
  85.         :out_estimate
  86.         set /p inp="%mid%"<nul
  87.         rem echo,&echo tg !target!, mp !mp!, base !base!, mid !mid!, est !est!
  88.         if "%tnum%" == "" (
  89.             :: 如果target只剩下 00,方案结束
  90.             if "%target%" == "00" ( goto :dec_loop_out )
  91.             if %cmp% == 0 ( goto :dec_loop_out )
  92.         )
  93.         :: 计算下一段target的值
  94.         call :bignum_minus %target% %mp% %target_len% %mplen% target target_len
  95.         :: 扩充target,如果被开根数已经截取完,直接补0,精度+1
  96.         if %skip% geq %len% (
  97.             set target=%target%00
  98.             set /a prec+=1
  99.             if !prec! equ 1 set /p inp="."<nul
  100.         ) else (
  101.             if "%target%" == "0" (set target=!tnum:~0,2!
  102.                           ) else (set target=!target!!tnum:~0,2!)
  103.             set tnum=!tnum:~2!
  104.             set /a skip+=2
  105.         )
  106.         set /a target_len+=2
  107.         :: 更新基数 - base
  108.         rem base=base*10+mid*2
  109.         if "%base%" == "0" (
  110.             set /a base=mid*2, base_len=1+base/10
  111.         ) else (
  112.             set /a db_mid=mid*2, dbmidlen=1+db_mid/10
  113.             call :bignum_plus !base!0 !db_mid! !base_len!+1 !dbmidlen! base base_len
  114.         )
  115.     if %prec% leq %precision% (goto :dec_loop)
  116.     :dec_loop_out
  117.     echo,
  118.     endlocal
  119.     goto :eof
  120. :: 比较
  121. :cmp
  122.     set /a La=%3, Lb=%4
  123.     if %La% gtr %Lb% (set /a %5=1&goto :eof)
  124.     if %La% lss %Lb% (set /a %5=-1&goto :eof)
  125.     :: 如果长度相同,直接按字符串对比
  126.     if "%1" gtr "%2" (set /a %5=1&goto :eof)
  127.     if "%1" lss "%2" (set /a %5=-1&goto :eof)
  128.     if "%1" equ "%2" (set /a %5=0&goto :eof)
  129. :: 大数 乘以 单位数
  130. :bignum_mp_single
  131.     setlocal
  132.     set num_a=%1
  133.     set num_b=%2
  134.     set /a pool = 0, maxid = %3
  135.     set "res="
  136.     for /l %%a in ( 1, 1, %maxid% ) do (
  137.         set /a mp = !num_a:~-%%a,1! * num_b + pool, t = mp %% 10, pool = mp / 10
  138.         set res=!t!!res!
  139.     )
  140.     if %pool% neq 0 (
  141.         set /a maxid+=1
  142.         set res=!pool!!res!
  143.     )
  144.     endlocal&set %5=%res%&set %6=%maxid%
  145.     goto :eof
  146. ::大数加法
  147. :bignum_plus
  148.     setlocal
  149.     set num_a=%1
  150.     set num_b=%2
  151.     set /a len_a=%3, len_b=%4
  152.     set /a max = len_a
  153.     if %len_b% gtr %len_a% (set /a max=len_b, len_b=len_a&set num_a=%num_b%&set num_b=%num_a%)
  154.     set /a pool=0
  155.     set res=
  156.     for /l %%n in ( 1, 1, %max% ) do (
  157.         if %%n leq %len_b% (
  158.             set /a t = !num_a:~-%%n,1! + !num_b:~-%%n,1! + pool
  159.         ) else (
  160.             set /a t = !num_a:~-%%n,1! + pool
  161.         )
  162.         set /a mod = t %% 10, pool = t / 10
  163.         set res=!mod!!res!
  164.     )
  165.     if %pool% gtr 0 (set /a max+=1 &set res=1%res%)
  166.     endlocal &set %5=%res%&set %6=%max%
  167.     goto :eof
  168. ::大数减法
  169. :bignum_minus
  170.     setlocal
  171.     set num_a=%1
  172.     set num_b=%2
  173.     set /a len_a=%3, len_b=%4
  174.     set /a max = len_a
  175.     if %len_b% gtr %len_a% (set /a max=len_b, len_b=len_a&set num_a=%num_b%&set num_b=%num_a%)
  176.     set /a minus = 0
  177.     set "res="
  178.     for /l %%n in ( 1, 1, %max% ) do (
  179.         if %%n leq %len_b% (
  180.             set /a dt = !num_a:~-%%n,1! - !num_b:~-%%n,1! - minus
  181.         ) else (
  182.             set /a dt = !num_a:~-%%n,1! - minus
  183.         )
  184.         if !dt! lss 0 (
  185.             set /a t = dt + 10, minus=1
  186.         ) else (
  187.             set /a t = dt, minus=0
  188.         )
  189.         set res=!t!!res!
  190.         if !t! equ 0 (set /a zero+=1) else (set /a zero=0)
  191.     )
  192.     set res=!res:~%zero%!
  193.     endlocal &set %5=%res%&set /a %6=%max%-%zero%
  194.     goto :eof
  195. ::字符串长度计算
  196. :length %str% %vname%
  197.     setlocal
  198.     set test=%~1_%sharp%
  199.     set test=!test:~0,%maxlen%!
  200.     set test=%test:*_=%
  201.     set /a len=maxlen-(%test:#=1+%1)
  202.     endlocal &set %2=%len%
  203.     goto :eof
  204. :: plp626的时间差函数 时间跨度在1分钟内可调用之;用于测试一般bat运行时间
  205. :time_delta <beginTimeVar> <endTimeVar> <retVar> // code by plp626
  206.     setlocal
  207.     set ta=%1&set tb=%2
  208.     set /a "c=1!tb:~-5,2!!tb:~-2!-1!ta:~-5,2!!ta:~-2!,c+=-6000*(c>>31)"
  209.     if defined %3 set /a c+=!%3!
  210.     endlocal&set %3=%c%
  211.     goto:eof
复制代码

TOP

回复 30# SQYSQYSQY

优化效率一时爽,添加功能火葬场。(就目前来说浮点数开根还没搞进去,也没有经过大量的数值测试BUG)
观点:功能完善前写给人看,方便调整,完善后再优化给机器看。

发现自己代码优化后有问题,29 26 开根会出现5.99999,29楼已经纠正,顺便提速,estimate 模块用于提前估值减少二分搜索次数。
在我的主机 80位 3.5s 300位 32s,手算法似乎不怎么需要二分,可以快速判定下一位数,绕了很大的弯路,修改中。

TOP

本帖最后由 523066680 于 2019-1-7 10:11 编辑

优化一波,没你的快。100位5.6秒,300位35秒 (CPU比较好,换一台机可能是8秒和45秒)
仍然使用逐位的计算,未使用连续N位数字为一段的处理方案,省心。

解决的问题:之前的代码对100开根会出现 10.0000000,现在不会了。
优化的部分:去掉了很多临时数组的操作特别是 buff[] 和与之对应的for循环
  1. :: Bignum(integer) Square Root, Decimal Solution
  2. :: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Decimal_(base_10)
  3. :: 523066680/vicyang
  4. :: 2019-01
  5. @echo off
  6. setlocal enabledelayedexpansion
  7. :init
  8.     rem 创建用于计算字符串长度的模板,长度限制为 2^pow
  9.     set "sharp=#"
  10.     set /a pow=11, maxlen=1^<^<pow
  11.     for /l %%a in (1,1,%pow%) do set sharp=!sharp!!sharp!
  12. set precision=80
  13. set num=2
  14. call :check_one %num%
  15. pause
  16. exit /b
  17. :: 独立测试
  18. :check_one
  19.     set ta=!time!
  20.     rem call :check_first %1 !precision!
  21.     call :decimal_solution %1
  22.     call :time_delta !ta! !time! tu
  23.     echo time used: !tu!
  24.     goto :eof
  25. :: 批量测试
  26. :check_all
  27.     for /l %%a in (1,1,99) do (
  28.         echo test number: %%a
  29.         call :check_first %%a !precision!
  30.         call :decimal_solution %%a
  31.         echo,
  32.     )
  33.     goto :eof
  34. :: 使用其他工具校验/对比结果
  35. :check_first
  36.     perl -Mbignum=p,-%2 -le "print sqrt(%1)" 2>nul
  37.     goto :eof
  38. :: 手算开根方案
  39. :decimal_solution
  40.     setlocal
  41.     set num=%1
  42.     set tnum=%1
  43.     call :length %num% len
  44.     set /a mod=len %% 2, tlen=len, base=0
  45.     if %mod% equ 1 (set /a skip=1) else (set /a skip=2)
  46.     set target=!tnum:~0,%skip%!
  47.     set tnum=!tnum:~%skip%!
  48.     set /a mp_0=0, mplen_0=1
  49.     set /a bstimes=0
  50.     rem prec 当前精度
  51.     set /a prec = 0
  52.     set /a base_len=0, equ=0, target_len=skip
  53.     :dec_loop
  54.         set /a min=0, max=10, mid=5, range=max-min, quit=0, equ=0
  55.         set /a tbase_len=base_len+1
  56.         :: 评估二分搜索的最大值
  57.         :guess
  58.         if %target_len% gtr 3 (
  59.         if %target_len% equ %tbase_len% (
  60.             set /a t_head = %target:~0,2%, b_head = %base:~0,2%
  61.         ) else (
  62.             set /a t_head = %target:~0,3%, b_head = %base:~0,2%
  63.         )
  64.         ) else (goto :out_of_guess)
  65.         for /l %%a in (0,1,9) do (
  66.             set /a t = %%a * b_head
  67.             if !t! gtr %t_head% (
  68.                 set /a max = %%a
  69.                 goto :out_of_guess
  70.             )
  71.         )
  72.         :out_of_guess
  73.         :: 做大致的除法预估 mid 值
  74.         :estimate
  75.         if %target_len% gtr 5 (
  76.             if %target_len% geq %tbase_len% (
  77.                 set /a est=!target:~0,6!/!base:~0,5!
  78.                 rem echo est - !est!
  79.                 set /a mid=!est:~0,1!
  80.                 rem echo,&echo %base% !target! !est! !mid! !target:~0,5!/!base:~0,5!
  81.             )
  82.         )
  83.         :: 如果预估max等于1,说明结果只能为0,跳过 bin_search
  84.         if %max% equ 1 (set /a mid=0& goto :out_bin_search )
  85.         rem echo, &echo %base%%mid% %target% %tbase_len% %target_len% max: %max%
  86.         set ta=%time%
  87.         :dec_bin_search
  88.             set /a bstimes+=1
  89.             :: mp = [base*10+mid] * mid
  90.             if "%base%" == "0" (
  91.                 set /a tbase = mid
  92.             ) else (
  93.                 set tbase=!base!!mid!
  94.             )
  95.             call :bignum_mp_single %tbase% %mid% %tbase_len% 1 mp mp_len
  96.             set mp_%mid%=%mp%
  97.             set mplen_%mid%=%mp_len%
  98.             :: 比较 - 判断是否超出
  99.             :cmp_begin
  100.             if %mp_len% gtr %target_len% (set /a cmp=1&goto :cmp_end)
  101.             if %mp_len% lss %target_len% (set /a cmp=-1&goto :cmp_end)
  102.             :: 如果长度相同,直接按字符串对比
  103.             if "%mp%" gtr "%target%" (set /a cmp=1&goto :cmp_end)
  104.             if "%mp%" lss "%target%" (set /a cmp=-1&goto :cmp_end)
  105.             if "%mp%" equ "%target%" (set /a cmp=0&goto :cmp_end)
  106.             :cmp_end
  107.             rem call :time_delta %ta% %time% bs_tu
  108.             if %cmp% equ 0 (set /a quit=1, equ=1)
  109.             if %cmp% equ 1 (set /a max=mid)
  110.             if %cmp% equ -1 (set /a min=mid)
  111.             if %range% leq 1 ( set /a quit=1 )
  112.             set /a mid=(max+min)/2, range=max-mid
  113.         if %quit% == 0 goto :dec_bin_search
  114.         :out_bin_search
  115.         rem echo, &echo est: %est%, act mid: %mid%
  116.         set /p inp="%mid%"<nul
  117.         if "%tnum%" == "" (
  118.             :: 如果target只剩下 00,方案结束
  119.             if "%target%" == "00" ( goto :dec_loop_out )
  120.             if %cmp% == 0 (
  121.                 goto :dec_loop_out
  122.             ) else (
  123.                 :: 当前精度
  124.                 if %prec% equ 0 set /p inp="."<nul
  125.                 set /a prec+=1
  126.             )
  127.         )
  128.         rem echo b=%base% tb=%tbase% tg=%target% mp=%mp% mid=%mid%
  129.         set ta=%time%
  130.         call :bignum_minus %target% !mp_%mid%! %target_len% !mplen_%mid%! target target_len
  131.         if %skip% geq %len% (
  132.             set target=%target%00
  133.         ) else (
  134.             if "%target%" == "0" (
  135.                 set target=!tnum:~0,2!
  136.             ) else (
  137.                 set target=!target!!tnum:~0,2!
  138.             )
  139.             set tnum=!tnum:~2!
  140.             set /a skip+=2
  141.         )
  142.         set /a target_len+=2
  143.         rem base=base*10+mid*2
  144.         if "%base%" == "0" (
  145.             set /a base=mid*2
  146.             if !base! geq 10 (set /a base_len=2) else (set /a base_len=1)
  147.         ) else (
  148.             set /a db_mid=mid*2
  149.             if !db_mid! geq 10 (set /a dbmidlen=2) else (set /a dbmidlen=1)
  150.             call :bignum_plus !base!0 !db_mid! !base_len!+1 !dbmidlen! base base_len
  151.         )
  152.     if %prec% leq %precision% (goto :dec_loop)
  153.     :dec_loop_out
  154.     echo,
  155.     echo search times: %bstimes%
  156.     endlocal
  157.     goto :eof
  158. :: 大数 乘以 单位数
  159. :bignum_mp_single
  160.     setlocal
  161.     set num_a=%1
  162.     set num_b=%2
  163.     set /a pool = 0, maxid = %3
  164.     set "res="
  165.     for /l %%a in ( 1, 1, %maxid% ) do (
  166.         set /a mp = !num_a:~-%%a,1! * num_b + pool, t = mp %% 10, pool = mp / 10
  167.         set res=!t!!res!
  168.     )
  169.     if %pool% neq 0 (
  170.         set /a maxid+=1
  171.         set res=!pool!!res!
  172.     )
  173.     endlocal&set %5=%res%&set %6=%maxid%
  174.     goto :eof
  175. ::大数加法
  176. :bignum_plus
  177.     setlocal
  178.     set num_a=%1
  179.     set num_b=%2
  180.     set /a len_a=%3, len_b=%4
  181.     set /a max = len_a
  182.     if %len_b% gtr %len_a% (set /a max=len_b, len_b=len_a&set num_a=%num_b%&set num_b=%num_a%)
  183.     set /a pool=0
  184.     set res=
  185.     for /l %%n in ( 1, 1, %max% ) do (
  186.         if %%n leq %len_b% (
  187.             set /a t = !num_a:~-%%n,1! + !num_b:~-%%n,1! + pool
  188.         ) else (
  189.             set /a t = !num_a:~-%%n,1! + pool
  190.         )
  191.         set /a mod = t %% 10, pool = t / 10
  192.         set res=!mod!!res!
  193.     )
  194.     if %pool% gtr 0 (set /a max+=1 &set res=1%res%)
  195.     endlocal &set %5=%res%&set %6=%max%
  196.     goto :eof
  197. ::大数减法
  198. :bignum_minus
  199.     setlocal
  200.     set num_a=%1
  201.     set num_b=%2
  202.     set /a len_a=%3, len_b=%4
  203.     set /a max = len_a
  204.     if %len_b% gtr %len_a% (set /a max=len_b, len_b=len_a&set num_a=%num_b%&set num_b=%num_a%)
  205.     set /a minus = 0
  206.     set "res="
  207.     for /l %%n in ( 1, 1, %max% ) do (
  208.         if %%n leq %len_b% (
  209.             set /a dt = !num_a:~-%%n,1! - !num_b:~-%%n,1! - minus
  210.         ) else (
  211.             set /a dt = !num_a:~-%%n,1! - minus
  212.         )
  213.         if !dt! lss 0 (
  214.             set /a t = dt + 10, minus=1
  215.         ) else (
  216.             set /a t = dt, minus=0
  217.         )
  218.         set res=!t!!res!
  219.         if !t! equ 0 (set /a zero+=1) else (set /a zero=0)
  220.     )
  221.     set res=!res:~%zero%!
  222.     endlocal &set %5=%res%&set /a %6=%max%-%zero%
  223.     goto :eof
  224. ::字符串长度计算
  225. :length %str% %vname%
  226.     setlocal
  227.     set test=%~1_%sharp%
  228.     set test=!test:~0,%maxlen%!
  229.     set test=%test:*_=%
  230.     set /a len=maxlen-(%test:#=1+%1)
  231.     endlocal &set %2=%len%
  232.     goto :eof
  233. :: plp626的时间差函数 时间跨度在1分钟内可调用之;用于测试一般bat运行时间
  234. :time_delta <beginTimeVar> <endTimeVar> <retVar> // code by plp626
  235.     setlocal
  236.     set ta=%1&set tb=%2
  237.     set /a "c=1!tb:~-5,2!!tb:~-2!-1!ta:~-5,2!!ta:~-2!,c+=-6000*(c>>31)"
  238.     if defined %3 set /a c+=!%3!
  239.     endlocal&set %3=%c%
  240.     goto:eof
复制代码
1

评分人数

TOP

最近看此帖, 然后搜索了一些高精度数学运算的资料, 发现深入学习需要高等数学知识, 本人高等数学待学习.

楼主看来近期对此范畴算法有高度兴趣, 所以我建议楼主查看开源软件的实现: GNU多重精度运算库

GNU Multiple Precision Arithmetic Library (GMP), 简称 GMP 是 GNU 的一部分, 并且为 Maple, Mathematica 这些专业数学软件提供 高精度数学运算 的实现

GMP 的平方根算法说明:
https://gmplib.org/manual/Square-Root-Algorithm.html

Paul Zimmermann, “Karatsuba Square Root”, INRIA Research Report 3805, November 1999,
http://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf

任意精度算术软件列表
https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software
1

评分人数

TOP

看了下楼主的程序。
330行之前的,换我写不超过100行。
任何重复性代码都应考虑for或if
连err都写五六个标签,有必要?
直接call err 1
:err
if %1==1 (echo ...)
if %1==2 ...
...
exit /b
也行啊?

TOP

本帖最后由 523066680 于 2019-1-29 18:46 编辑

nothing

TOP

本帖最后由 523066680 于 2019-1-5 23:07 编辑

回复 24# 小程936

    你是说Pi吗,很多大牛为此做过大的量工作。
传奇人物 Fabrice Ballard
有史以来最优秀的程序员有哪些? - absfree的回答 - 知乎

TOP

回复  SQYSQYSQY

     确实很快,在探索算法的层面上,用什么语言都可以探索,所以这点没什么反对的,批 ...
523066680 发表于 2019-1-5 17:26



   这么说的话,我想到一个软件 super pi
百度就有下载。
可以1分钟计算3200万位。

TOP

本帖最后由 523066680 于 2019-1-5 21:02 编辑

回复 35# SQYSQYSQY

    当我看了 happy886r 的乘法,已经知道划分为N位一段而非逐位的处理可以令速度翻倍。参考23楼 http://bbs.bathome.net/redirect. ... 1557&pid=216162
我当然也知道 for 比 goto 快, goto 比 call 快,但我是不会让我的代码变成这样的。

不过这是批处理,如果我不花时间继续优化,我就可以做别的有趣的事情了。
1

评分人数

    • 老刘1号: bat纠结什么效率,根本没有效率技术 + 1

TOP

手算开根方案的初步实现,有bug待修,支持大数开根,效率没有很高,先刷新16楼那段代码的时间。
精度80位大约耗时8秒。应该可以再改,再看看吧。
  1. :: Bignum(integer) Square Root, Decimal Solution
  2. :: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Decimal_(base_10)
  3. :: 523066680/vicyang
  4. :: 2019-01
  5. @echo off
  6. setlocal enabledelayedexpansion
  7. :init
  8.     rem 创建用于计算字符串长度的模板,长度限制为 2^pow
  9.     set "sharp=#"
  10.     set /a pow=11, maxlen=1^<^<pow
  11.     for /l %%a in (1,1,%pow%) do set sharp=!sharp!!sharp!
  12. set num=2
  13. rem set num=10
  14. rem call :get_int_of_root %num% int_root cmp
  15. set precision=80
  16. rem call :check_first %num% %precision%
  17. call :decimal_solution %num%
  18. pause
  19. exit /b
  20. :check_first
  21.     perl -Mbignum=p,-%2 -le "print sqrt(%1)" 2>nul
  22.     goto :eof
  23. :: 手算开根方案
  24. :decimal_solution
  25.     setlocal
  26.     set num=%1
  27.     set tnum=%1
  28.     call :length %num% len
  29.     set /a mod=len %% 2, tlen=len, base=0
  30.     if %mod% equ 1 (set /a skip=1) else (set /a skip=2)
  31.     set target=!tnum:~0,%skip%!
  32.     set tnum=!tnum:~%skip%!
  33.     set mp_0=0
  34.     rem prec 精度
  35.     set /a prec = 0
  36.     set /a tbase_len = 0, equ = 0
  37.     :dec_loop
  38.         set /a min=0, max=10, mid=5, range=max-min, quit=0, equ=0
  39.         set /a tbase_len+=1
  40.         call :length %target% target_len
  41.         :: 预估下一个可能的数,并限制二分搜索的最大值
  42.         :guess
  43.         if %target_len% gtr 3 (
  44.         if %target_len% equ %tbase_len% (
  45.             set /a t_head = %target:~0,2%, b_head = %base:~0,2%
  46.         ) else (
  47.             set /a t_head = %target:~0,3%, b_head = %base:~0,2%
  48.         )
  49.         ) else (goto :out_of_guess)
  50.         for /l %%a in (0,1,9) do (
  51.             set /a t = %%a * b_head
  52.             rem echo !t! !target:~0,2! %%a
  53.             if !t! gtr %t_head% (
  54.                 set /a max = %%a, mid = ^(min+max^)/2
  55.                 goto :out_of_guess
  56.             )
  57.         )
  58.         :out_of_guess
  59.         rem echo, &echo %base%%mid% %target% %tbase_len% %target_len% max: %max%
  60.         :dec_bin_search
  61.             :: mp = [base*10+mid] * mid
  62.             if "%base%" == "0" (
  63.                 set /a tbase = mid
  64.             ) else (
  65.                 set tbase=!base!!mid!
  66.             )
  67.             set ta=%time%
  68.             call :bignum_mp %tbase% %mid% %tbase_len% 1 mp mp_len
  69.             set mp_%mid%=%mp%
  70.             set mplen_%mid%=%mp_len%
  71.             rem call :cmp %mp% %target% %mp_len% %target_len% cmp
  72.             :: 比较 - 判断是否超出
  73.             :cmp_begin
  74.             if %mp_len% gtr %target_len% (set /a cmp=1&goto :cmp_end)
  75.             if %mp_len% lss %target_len% (set /a cmp=-1&goto :cmp_end)
  76.             :: 如果长度相同,直接按字符串对比
  77.             if "%mp%" gtr "%target%" (set /a cmp=1&goto :cmp_end)
  78.             if "%mp%" lss "%target%" (set /a cmp=-1&goto :cmp_end)
  79.             if "%mp%" equ "%target%" (set /a cmp=0&goto :cmp_end)
  80.             :cmp_end
  81.             rem call :time_delta %ta% %time% bs_tu
  82.             if %cmp% equ 0 (set /a quit=1, equ=1)
  83.             if %cmp% equ 1 (set /a max=mid )
  84.             if %cmp% equ -1 (set /a min=mid )
  85.             if %range% leq 1 ( set /a quit=1 )
  86.             set /a mid=(max+min)/2, range=max-mid
  87.         if %quit% == 0 goto :dec_bin_search
  88.         
  89.         set ta=%time%
  90.         set /p inp="%mid%"<nul
  91.         rem echo, &echo tnum %tnum%, cmp %cmp%, equ %equ%, tg %target%
  92.         if "%tnum%" == "" (
  93.             if %cmp% == 0 (
  94.                 goto :dec_loop_out
  95.             ) else (
  96.                 rem current precision
  97.                 if %prec% equ 0 set /p inp="."<nul
  98.                 set /a prec+=1
  99.             )
  100.         )
  101.         rem echo b=%base% tb=%tbase% tg=%target% mp=%mp% mid=%mid%
  102.         call :bignum_minus %target% !mp_%mid%! target
  103.         if %skip% geq %len% (
  104.             set target=%target%00
  105.         ) else (
  106.             if "%target%" == "0" (
  107.                 set target=!tnum:~0,2!
  108.             ) else (
  109.                 set target=!target!!tnum:~0,2!
  110.             )
  111.             set tnum=!tnum:~2!
  112.             set /a skip+=2
  113.         )
  114.         rem base=base*10+mid*2
  115.         if "%base%" == "0" (
  116.             set /a base=mid*2
  117.         ) else (
  118.             set /a db_mid=mid*2
  119.             call :bignum_plus !base!0 !db_mid! base
  120.         )
  121.         rem call :time_delta %ta% %time% else_tu
  122.     if %prec% leq %precision% (goto :dec_loop)
  123.     :dec_loop_out
  124.     endlocal
  125.     goto :eof
  126. ::大数乘法
  127. :bignum_mp
  128.     setlocal
  129.     set num_a=%1
  130.     set num_b=%2
  131.     set /a len_a=%3, len_b=%4
  132.     for /l %%b in ( 1, 1, %len_b% ) do ( set ele_b=!ele_b! !num_b:~-%%b,1! )
  133.     for /l %%a in ( 1, 1, %len_a% ) do ( set ele_a=!ele_a! !num_a:~-%%a,1! )
  134.     set /a id = 0, sid = 0, maxid = 0
  135.     for %%b in ( %ele_b% ) do (
  136.         set /a sid = id, id += 1
  137.         for %%a in ( %ele_a% ) do (
  138.             set /a buff[!sid!] += %%a * %%b, sid += 1, maxid = sid
  139.         )
  140.     )
  141.     rem Merge
  142.     set /a id = 0
  143.     for /l %%c in ( 0, 1, %maxid% ) do (
  144.         set /a next = %%c+1
  145.         set /a buff[!next!] += buff[%%c]/10, buff[%%c] = buff[%%c] %% 10
  146.     )
  147.     if "!buff[%maxid%]!" == "0" set /a maxid-=1
  148.     set product=
  149.     for /l %%n in (%maxid%, -1, 0) do set product=!product!!buff[%%n]!
  150.     endlocal &set %5=%product%&set /a %6=%maxid%+1
  151.     goto :eof
  152. ::大数加法
  153. :bignum_plus
  154.     setlocal
  155.     set num_a=%1
  156.     set num_b=%2
  157.     call :length %num_a% len_a
  158.     call :length %num_b% len_b
  159.     set /a max = len_a
  160.     if %len_b% gtr %len_a% (set /a max=len_b, len_b=len_a&set num_a=%num_b%&set num_b=%num_a%)
  161.     for /l %%n in ( 1, 1, %max% ) do (
  162.         if %%n leq %len_b% (
  163.             set /a buff[%%n] = !num_a:~-%%n,1! + !num_b:~-%%n,1!
  164.         ) else (
  165.             set buff[%%n]=!num_a:~-%%n,1!
  166.         )
  167.     )
  168.     set /a id = 0
  169.     for /l %%c in ( 0, 1, %max% ) do (
  170.         set /a next = %%c+1
  171.         set /a buff[!next!] += buff[%%c]/10, buff[%%c] = buff[%%c] %% 10
  172.     )
  173.     if "!buff[%next%]!" gtr "0" set /a max+=1
  174.     set sum=
  175.     for /l %%a in (%max%, -1, 1) do set sum=!sum!!buff[%%a]!
  176.     endlocal &set %3=%sum%
  177.     goto :eof
  178. ::大数减法
  179. :bignum_minus
  180.     setlocal
  181.     set num_a=%1
  182.     set num_b=%2
  183.     call :length %num_a% len_a
  184.     call :length %num_b% len_b
  185.     set /a max = len_a
  186.     if %len_b% gtr %len_a% (set /a max=len_b, len_b=len_a&set num_a=%num_b%&set num_b=%num_a%)
  187.     set /a minus = 0
  188.     for /l %%n in ( 1, 1, %max% ) do (
  189.         if %%n leq %len_b% (
  190.             set /a dt = !num_a:~-%%n,1! - !num_b:~-%%n,1! - minus
  191.         ) else (
  192.             set /a dt = !num_a:~-%%n,1! - minus
  193.         )
  194.         if !dt! lss 0 (
  195.             set /a buff[%%n] = dt + 10, minus=1
  196.         ) else (
  197.             set /a buff[%%n] = dt, minus=0
  198.         )
  199.     )
  200.     set delta=#
  201.     for /l %%a in (%max%, -1, 1) do set delta=!delta:#0=#!!buff[%%a]!
  202.     endlocal &set %3=%delta:#=%
  203.     goto :eof
  204. ::字符串长度计算
  205. :length %str% %vname%
  206.     setlocal
  207.     set test=%~1_%sharp%
  208.     set test=!test:~0,%maxlen%!
  209.     set test=%test:*_=%
  210.     set /a len=maxlen-(%test:#=1+%1)
  211.     endlocal &set %2=%len%
  212.     goto :eof
  213. :: plp626的时间差函数 时间跨度在1分钟内可调用之;用于测试一般bat运行时间
  214. :time_delta <beginTimeVar> <endTimeVar> <retVar> // code by plp626
  215.     setlocal
  216.     set ta=%1&set tb=%2
  217.     set /a "c=1!tb:~-5,2!!tb:~-2!-1!ta:~-5,2!!ta:~-2!,c+=-6000*(c>>31)"
  218.     if defined %3 set /a c+=!%3!
  219.     endlocal&set %3=%c%
  220.     goto:eof
复制代码

TOP

回复 28# SQYSQYSQY


    推荐用 Notepad++ 写代码试试,不用手工敲那么多空格。
2

评分人数

    • SQYSQYSQY: 谢提醒,我又忘了,对不起技术 + 1
    • 523066680: 关键是读代码的人痛苦好吗PB + 6
我帮忙写的代码不需要付钱。如果一定要给,请在微信群或QQ群发给大家吧。
【微信公众号、微信群、QQ群】http://bbs.bathome.net/thread-3473-1-1.html
【支持批处理之家,加入VIP会员!】http://bbs.bathome.net/thread-67716-1-1.html

TOP

本帖最后由 523066680 于 2019-1-6 16:29 编辑

回复 31# SQYSQYSQY

     确实很快,在探索算法的层面上,用什么语言都可以探索,所以这点没什么反对的,批处理还可以放大不同算法之间的效率差距。
但是在执行效率上,不能说比的上其他编程语言甚至是编译型语言吧?



我又试了一下 python,10000精度,酸爽

TOP

本帖最后由 523066680 于 2019-1-5 11:39 编辑

回复 26# SQYSQYSQY

    bat关于计算位数有限制,但是自己采用全套大数加、减、乘、大数比较,就不受这些限制啦。相应的会增加一些消耗。

TOP

你们是不是炫技?
写个几百上千行的代码,
然后计算速度10秒一位,有意思?

那我写一个。0.0001秒算完。

添加至bat末尾,调用方法call :s 数字
输出值为变量b和errorlevel
  1. :s
  2. set /a a=%1,b=a/2
  3. for /l %%a in (1,1,15) do set /a b=(b+a/b)/2
  4. exit /b %b%
复制代码
bug修正版
  1. 修正bug版
  2. :s
  3. if "#%1"=="#"  echo 未输入&set b=&exit /b
  4. set /a a=%1,b=a/2
  5. if "%a:~0,1%"=="-" echo 负数&set b=&exit /b
  6. if "%a%"=="0" set b=0&exit /b 0
  7. for /l %%a in (1,1,15) do set /a b=(b+a/b)/2
  8. exit /b %b%
复制代码
1

评分人数

TOP

返回列表