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

本帖最后由 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-24 16:32 编辑

回复 35# SQYSQYSQY

    查阅 ASCII 字符表,如果想学习更多关于字符编码,建议:学习 python,用python去读写各种网页文件。
关键词:Encode, Decode, Unicode, UTF8, UTF16, GBK, CP936

用其他语言显示数字符号对应的ASCII码。
  1. >perl -e "grep {printf qq('%d' - %d\n), $_, ord($_) } (0..9)"
  2. '0' - 48
  3. '1' - 49
  4. '2' - 50
  5. '3' - 51
  6. '4' - 52
  7. '5' - 53
  8. '6' - 54
  9. '7' - 55
  10. '8' - 56
  11. '9' - 57
复制代码

TOP

回复 38# SQYSQYSQY

非常短(难道是受到了27楼小朋友的刺激?他短任他短,清风拂山冈。他横任他横,明月照大江)。可能有小细节需要完善:
1.414找不到操作数。
999999999999999999

    不打算先把大数和浮点数做进去再精简吗。

浮点数版本,效率老样子,代码不打算优化了,要也用Perl,或者换C艹
1

评分人数

    • SQYSQYSQY: 浮点数也能计算啊。(其实就是对整数计算, ...技术 + 1

TOP

本帖最后由 523066680 于 2019-1-17 20:23 编辑

回复 40# SQYSQYSQY

      你这起跑线多好,我那会儿没零钱,严重的时候一周只有1元上一个小时网吧,要做点什么得在稿纸上写好,不然刷的一小时没了。

空间换时间/时间换空间
查表就是为了"空间换时间",几百个上千元素的数组查询都会慢的也就是批处理了,不如趁早换用自由度高的语言。

那个例子可以用函数表达,x^2,和 5*x 赛跑,一开始 5*x 比较快,后来 x^2 …… 这俩太陡了,应该有更合适的曲线,暂时先这样


浮点数版本补充在39楼。

TOP

本帖最后由 523066680 于 2019-1-17 23:14 编辑

1月17日
补充 —— 是楼层穿越问题。此信息PASS

TOP

本帖最后由 523066680 于 2019-1-18 11:40 编辑

回复 37# SQYSQYSQY

      关于自由度,我不说数独,你用批处理做一做猜数字游戏的搜索树就知道了,但凡跟递归、多重镶嵌数据结构有关的东西,用批处理都不划算。
http://bbs.bathome.net/thread-49436-1-2.html
(非杠,我就是觉得你学其他语言,起跑线就会有一个质的飞跃。也不推荐Perl,现在的主流推荐就是Python,Java,C)

百度百科的描述
https://baike.baidu.com/item/%E7 ... 97/83200?fr=aladdin

举一个简单的例子:
我要生成50个随机字符,内容可以是数字和小写字母;将字符串拆割重组、输出显示整个数组:
  1. use Modern::Perl;
  2. # 生成 50 个随机字符,范围是数字和小写字母
  3. my @arr = map { ('0'..'9', 'a'..'z')[rand(36)] } (1 .. 50 );
  4. my $s = "bathomenet";
  5. say join(",", @arr);
  6. say join(",", split //, $s);
  7. print length($s);
复制代码
输出
  1. j,x,c,z,7,k,u,p,d,w,u,k,d,0,s,9,l,a,7,n,i,9,h,s,l,5,1,q,d,m,j,i,p,m,3,x,4,h,s,d,r,s,3,q,w,i,d,z,f,y
  2. b,a,t,h,o,m,e,n,e,t
  3. 10
复制代码
这些在 python ruby perl 里面都是常规操作,字符串长度允许范围几乎就是对应内存的剩余空间。

批处理可以做到,但是会很烦,vbs同样烦,js、Powershell应该好写

回复 39# SQYSQYSQY

      我也是业余的,工作和IT不相关。可以预见的是你的路线可以是 x^2。
而我这种职业不相关的,路线基本就只能是平缓直线甚至是上下波动了

TOP

回复 40# SQYSQYSQY

    先写一个测试模块,发布前测试过会比较妥。更新后的代码测试26,37,50,65,82不通过。更新前测试通过(精确到80位)。
  1. for /l %%a in (1,1, 100%或者其他数字%) do ( call :开根函数 )
  2. exit/b
  3. :开根函数
  4. setlocal
  5. endlocal& goto :eof
复制代码

TOP

本帖最后由 523066680 于 2019-1-24 21:48 编辑

回复 28# search_Sudoku

    将手算法原样撸了一个C++初始版本,未优化,1W精度(含输出)0.9秒。

返回来看gmp库的说明,这理论好深(估计happy能看懂,我只能看看概述)
Introduction
The current asymptotically fastest known method to compute the square-root of a n-word number is using Fast Fourier Transform (FFT) multiplication and Newton'smethod,
with a complexity of 5M(n)' [1, p. 155].2 The algorithm presented here is basedon Burnikel-Ziegler Karatsuba division [2].
这里面用到 快速傅里叶变换乘法、牛顿迭代法,以及 Burnikel-Ziegler Karatsuba 除法。

牛顿迭代法的精度增长很快(差不多翻倍增长),需要用到大数除法。实践起来,具体的精度不太好确定,因此迭代到一定次数后,除法的精度取舍也是个问题,
我也发现引用了牛顿迭代法的方案大多是给出一个预判的精度,
比如 gmp 中设置 mpf_set_default_prec (10000);  开根后 gmp_printf ("Square root: %.10000Ff\n\n", sq_out);
实际有效数字只有3068位,末尾由大量的0填充。

几种接口效率对比(i7 8核 4GHz)
Perl bignum 模块,1W精度 耗时4.5s
Python Decimal 模块,10W精度 耗时 1.0s
C++ 使用 GMP库,100W有效精度,含输出,1.5秒;不含输出,0.2秒
                           1000W位有效精度,不含输出, 2.5秒。

libgmp太凶悍

C++ 测试GMP速度以及判断有效精度的代码:
  1. #include <iostream>
  2. #include <sstream>
  3. #include <iomanip>
  4. #include <chrono>
  5. #include "gmpxx.h"
  6. #include "gmp.h"
  7. using namespace std;
  8. int main(int argc, char *argv[] )
  9. {
  10.     ostringstream os;
  11.     mpf_class n(2, 10), r(1, 3600000);
  12.     auto start = chrono::system_clock::now();
  13.         r = sqrt(n);
  14.         os << setprecision(10000000) << r;
  15.     auto end = chrono::system_clock::now();
  16.     chrono::duration<double> diff = end-start;
  17.     cout << "Actual length of r: " << os.str().length() << endl;
  18.     cout << "Time Used: " << setprecision(3) << diff.count() << " s" << endl;
  19.     return 0;
  20. }
复制代码
Actual length of r: 1083710
Time Used: 0.561 s (这里包含 os << r 产生的时间)

GNU MP 库中用到的算法和理论,完整版:
《Modern Computer Arithmetic》
http://maths.anu.edu.au/~brent/pd/mca-cup-0.5.9.pdf

TOP

本帖最后由 523066680 于 2019-1-25 20:38 编辑

用了两天 VS2015,不愧是宇宙最强编辑器(是我墨守成规,一直装在系统,从来不用)

s_minus 函数和 vec_minus 函数性能分析,1W位数,各调用2W次的分析结果:





可以看到涉及数组[]操作的语句消耗较高,采用高的进制(base)处理势在必行。

再聊聊《Modern Computer Arithmetic》(后面简称MCA)
对于64位平台 unsigned long long int 支持的最大数字是 2^64-1=18446744073709551615,20位,如果我们充分利用,使用2^64作为进制,或者10^19作为进制,
很容易会遇到溢出问题,MCA中给出了几种方案:
Let T be the number of different values taken by the data type representing the coefficients ai, bi. (Clearly, β ≤ T, but equality does not necessarily hold,
for example β = 10^9 and T = 2^32.) At step 3, the value of s can be as large as 2β − 1, which is not representable if β = T. Several workarounds
are possible:
either use a machine instruction that gives the possible carry of ai + bi,
or use the fact that, if a carry occurs in ai + bi, then the computed sum – if performed modulo T – equals t := ai +bi −T < ai; thus, comparing t and ai will determine if a carry occurred.
A third solution is to keep a bit in reserve, taking β ≤ T/2.

用 T 表示一个存储单元所能表示的数的量,则有 β <= T (这里 β 表示采用的进制,以及β不一定等于T,例如T=2^32,但采用的进制为10^9)。
考虑加法操作 s=a+b+d (d为1或0,是上一次加法补进的数值),s的最大可能值为 2*β-1,当 β = T 时该公式无法正确计算。考虑以下方案:
1. 内部编码实现 (水平有限,暂时这么翻译)
2. 通过-T取余数判断,t := a + b - T < a ,对比 t 和 a 断定是否进 1
3. 采用一个保守的进制数 β,令 β ≤ T/2.

TOP

贴吧吧友写的(Q群里聊天得知,感谢小程)
可开开方后结果为整数的整数
  1. @set /p a=输入a=
  2. @set /a b=a
  3. @for /l %%a in (1,1,30) do @set /a b=(b+a/b)/2
  4. @set b
复制代码

TOP

这贴的楼层有毒吧,看的好蛋疼

TOP

回复 44# 老刘1号

      这个牛跌前面楼层有提到过呀。
我们主要在折腾大数字和浮点数。如果只在signed int范围内开整数根,早就可以结帖了。
小程说他要写一个版本的时候我以为“硬核”要来了,结果 ……
那本《MCA》非常硬核!打算用C艹实践其中一小部分算法(大部分看不懂,小部分似懂非懂)。

回复 43# SQYSQYSQY

批处理的“数组”属于伪数组,和其他语言的数组有本质的区别,因为批的“索引”不只是数字,还有字母和符号,变量长度亦不确定,这和其他语言的哈希表(hash table)相似。
在C/C++里面的数组操作不需要“搜索”,可直接通过计算偏移量取内存地址,因为定长的数组在初始化后占用一段连续内存空间,且每个单元占用相同字节,
给定一个编号,通过 编号*字节大小+起点地址 可得目标内存地址,直接存取。
C++ vector容器的 [] 操作符消耗占用高,和其独立的实现有关(可能做了各种判断和转换处理),换用更纯粹的C语言数组可以减少这种消耗。

实测,元素数量为80W的容器/数组,1000次遍历每一个元素并写入int值,
  1. #include <iostream>
  2. #include <vector>
  3. #include <chrono>
  4. using namespace std;
  5. using namespace std::chrono;
  6. const int SIZE = 800000;
  7. void vec_test(void);
  8. void c_array_test(void);
  9. void c_pointer_test(void);
  10. void time_used(system_clock::time_point& time_a);
  11. vector<int> vec(SIZE);
  12. int array1[SIZE];
  13. int array2[SIZE];
  14. int main(int argc, char *argv[])
  15. {
  16.     system_clock::time_point start = system_clock::now();
  17.     for (int i = 0; i < 1000; i++) vec_test();
  18.     time_used(start);
  19.     for (int i = 0; i < 1000; i++)  c_array_test();
  20.     time_used(start);
  21.     for (int i = 0; i < 1000; i++)  c_pointer_test();
  22.     time_used(start);
  23.     return 0;
  24. }
  25. void vec_test(void) {
  26.     register int it;
  27.     for (it = 0; it < SIZE; it++) vec[it] = it;
  28. }
  29. void c_array_test(void) {
  30.     register int it;
  31.     for (it = 0; it < SIZE; it++) array1[it] = it;
  32. }
  33. void c_pointer_test(void) {
  34.     register int it;
  35.     register int *pt = array2;
  36.     for (it = 0; it < SIZE; it++) *(pt + it) = it;
  37. }
  38. void time_used(system_clock::time_point& time_a) {
  39.     duration<double> diff;
  40.     diff = chrono::system_clock::now() - time_a;
  41.     cout << "Time used: " << diff.count() << endl;
  42.     time_a = chrono::system_clock::now();
  43. }
复制代码
g++编译测试结果:
Time used: 1.24807
Time used: 0.400023
Time used: 0.393022

Visual Studio编译,差距更明显
Time used: 3.92722
Time used: 0.0410024
Time used: 0.0360021


如果一定要用 vector 又不想用它的 [] ,可以申请一个指针,int *vp = vec.data()
通过*vp指针直接算地址读写内存,速度和c_array一样快,想要更快,申请一个寄存器指针 register int *vp。
这就是自由度,可定制,可接管。

讨论算法,可以不分语言。谈论模块化思想,也可以不分语言,用批处理同样可以表达。
但要说极限压榨性能,怎么也轮不到批处理。

TOP

本帖最后由 老刘1号 于 2019-1-26 19:26 编辑

回复 46# SQYSQYSQY
回复 47# 523066680


    哈哈发现了,我大致扫了一遍回帖没注意到,就贴了一下
没专门研究过这个算法,不知是牛跌

TOP

本帖最后由 523066680 于 2019-2-9 21:35 编辑

回复 48# 老刘1号


      这都是牛顿的功劳呀,牛迭是N次方,1/N次方都可以算,很多其他方程的根也可以算。因为他是在一个函数曲线任意一点(x)上求切线,然后这个切线不断迭代,向函数曲线和x轴的交点(根或者函数的解)逼近。
逼近速度非常快(差不多精度翻倍)。

现在回想,happy886r 当时写了好多大工程
happy886r - 数学计算工具 i 的重构版new i

TOP

返回列表