|
|
本帖最后由 aoe1981 于 2022-2-16 16:06 编辑
我至少是受下面3个帖子的影响，对巨大数的运算产生了好奇，满腹疑问。
按时间顺序：
1.2011年8月
自定义函数，位数超长数字的加减乘除计算。
https://club.excelhome.net/thread-748124-1-1.html
(出处: ExcelHome技术论坛)
2.2013年11月
[开_145-2]计算根号2，比精度比速度[已总结]
https://club.excelhome.net/thread-1075113-1-1.html
(出处: ExcelHome技术论坛)
3.2014年4月
二个巨大数的三則運算
https://club.excelhome.net/thread-1108590-1-1.html
(出处: ExcelHome技术论坛)
百度搜索了一阵子，找到一个网站，有“大数计算器”（TKCB），样子如图：
用着不错，也很羡慕。我测试了一下竞赛帖中的开根号2，开1000位时很快，但测试开10000位时，耗时约在1000秒。而竞赛帖中大神jsxjd的优秀代码开根号2到10000位，在我现在的电脑上只需要0.18秒，让人咋舌。不过，TKCB开发的“大数计算器”是可以针对巨大数开方的，这也是很了不起的。
我愈发好奇。开始搜各种视频教程，研读竞赛帖，学习CSDN上的免费算法帖子。
折腾半月余，总算做了个VBA版的“巨大数运算”，一并发在我的EH账号里，作为记录。
模样如图：
共有7个模块：
一、加法模块HugeNumberPlus
（1）Public Function HNPlus(ByVal a As String, ByVal b As String) As String
巨大数运算之巨大数加法（加数a，加数b）
二、减法模块HugeNumberSubtract
（2）Public Function HNSubtract(ByVal a As String, ByVal b As String) As String
巨大数运算之巨大数减法（被减数a，减数b）
三、乘法模块HugeNumberMultiply
（3）Public Function HNMultiply(ByVal a As String, ByVal b As String) As String
巨大数运算之巨大数乘法（因数a，因数b）
（4）Public Function StringCheck(ByRef str As String) As Boolean
（公用1）字符串检查（字符串str）
（5）Public Function StringToArray(ByVal str As String, ByVal n As Long, Optional ByVal tf As Boolean = False)
（公用2）将字符串截断装入数组（字符串str，每组字符个数n，True倒序False顺序）
（6）Public Function StringReplaceHTSame(ByVal str As String, ByVal s As String, Optional ByVal ht As Boolean = True) As String
（公用3）替换字符串首尾相同的指定字符（字符串str，指定字符s，首True尾False）
四、除法模块HugeNumberDivide
（7）Public Function HNDivide(ByVal a As String, ByVal b As String, Optional ByVal n As Long = 0, Optional ByVal ys As Boolean = False) As String
巨大数运算之巨大数除法（末位四舍五入）（被除数a，除数b，限制小数位数n，输出余数ys）
五、平方根模块SquareRoot
（8）Public Function SQROOT(ByVal c As Double, Optional ByVal Lenght As Long = 15) As String
迭代法开平方根（被开方正数c，计算精度Lenght）
迭代关系式：x1=x0*(1.5-c/2*x0^2)
（9）Public Function SQROOT2(ByVal c As String, Optional ByVal ws As Long = 15) As String
迭代法开平方根（被开方大正数c，小数位数ws）
迭代关系式：x1=x0*(1.5-c/2*x0^2)
（10）Public Function SQROOT3(ByVal c As String, Optional ByVal ws As Long = 15) As String
手算法开平方根（被开方大正数c，小数位数ws）
（11）Public Function SQROOT4(ByVal c As String, Optional ByVal n As Long = 15) As String
二分法开平方根（被开方大正数c，迭代次数n）
六、立方根模块CubeRoot
（12）Public Function CUROOT(ByVal c As Double, Optional ByVal Lenght As Long = 15) As String
迭代法开立方根（被开方正数c，计算精度Lenght）
迭代关系式：x1=x0*(4-c*x0^3)/3
（13）Public Function CUROOT2(ByVal c As String, Optional ByVal ws As Long = 15) As String
迭代法开立方根（被开方大数c，小数位数ws）
迭代关系式：x1=x0*(4-c*x0^3)/3
七、测试模块Test
（14）Public Function GenerateHugeNumber(ByVal n As Long, Optional ByVal xs As Long = 0, Optional ByVal fs As Boolean = False) As String
随机生成巨大数（位数n，小数部分位数xs，输出负数fs）
（15）Public Function CheckStringDifferent(ByVal a As String, ByVal b As String) As String
检查并返回两个字符串首次出现不同的位置及相应字符（字符串a，字符串b）
（16……）一众test1、test2、……、test7、test71、test72、test73、test74、test8、test81、test82
说说效果：
1.所谓“巨大数”，包含正数、负数、0，整数、小数。
2.我测试了32767位×32767位的乘法，在我现在的电脑上用时15.43秒。由于单元格最大输入32767字符，测试更长数位需在代码中引用变量，而且输出至“立即窗口”，同时要专门写代码调用“比对函数”，以确保结果的正确性。在帖首给出的竞赛帖中，大神lee1892给出了一段当时4秒参照代码，那段代码在我现在的机子上约需0.4秒，快了10倍，放在当时，这道乘法需要150多秒。
3.我测试了16000位÷2位的除法，约需4.5秒，香川大侠在帖首2014年4月的帖子中上传的巨大数除法仅需0.03秒，速度是我的除法的150倍以上。我很好奇，没研究懂，只发现，香川的除法一次可以出12位商，而我的除法就像小学生列竖式一样，从高到低，一位一位往下除，每循环一次，出一位商，所以效率天壤之别。设若我采用香川大侠的除法代码，我的开平方、开立方的算法效率也会提升。不过，我还是不喜欢用不懂的东西，想着以后有可能了学习、优化除法。但是，我的除法比“大数计算器”强。话说回来，香川大侠前后做了两个版本的乘法吧，TM()和TM2()，版本2更高效，但在负数乘正数时会出错，TM()却是对的。（友情提示，我自然找不出原因）
4.开平方算法我尝试了“手算法”（效率低，但结果是百分之百正确的，可以校验其他算法）、“二分法”（效率更低，有点垃圾），最后还是学习了lee1892大师讲解的“牛顿迭代法”，链接如下：
https://club.excelhome.net/forum ... 1075113&pid=7426754
感谢lee1892大师。囫囵吞枣，只得皮毛。我一开始针对Double范围内的数开方，居然用2.97秒开出了根号2后10000位，这并不算是达到了当时竞赛帖中“4秒计算万位”的拔高要求，因为实则相当于当时的29.7秒。后来，我又做了针对“巨大数”的开方，为了平衡“整数部分很大的”、“0.0000000000……”这样很小的数，在迭代终止条件上、有效数字增长控制上，尽量取了一些平衡的策略，这个版本的开根号2到10000位，目前需要33.4秒，可以提速至18秒，但在开大整数时，精度又会下降。如何平衡？我始终是以“大数计算器”做对比的。
5.开立方运算无可避免的在迭代过程内部需要做除法，一个“巨大数除以3”的除法，这使得这个算法效率惨不忍睹，不如“大数计算器”，向TKCB致敬。一个2开立方根至1000位小数，约需44秒。说这些，是为了给大家一些思想准备，否则，大家不吝测试时，急于上巨大数，电脑假死了，大家会骂死我的。
7.加减乘除的正确性，目前我会说“应该是百分之百”，我已修复了许多隐秘的bug。关于求余数，遵循“被减数-除数×商”，正常，余数与被除数同号（这与mod函数是有区别的，mod函数的余数与除数同号），但由于我将求商的“截断法”，改为末位“四舍五入法”，当商五入时，会出现反方向的余数，大家明白以后就忍受下。
8.开平方、开立方的正确性，目前我会说“百分之九十九点九九”，万足金吧，嘿嘿。关于“牛顿迭代法”，有三个关键点，也是难点：
（1）迭代初值的选取。这个初值要与目标值比较接近，否则越过函数的“收敛半径”，值会发散的，比如，开根号2时，初值选为2，结果变成巨大数了，初值选成1.4，居然出现负数根了。对于一个巨大数，我略用下面的方法产生初值，还凑和。
“一个整数部分ws位的巨大数开n次方，其根的整数部分位数是：int((ws+n-1)/n)位”
（2）迭代关系式的优化。应该尽量避免巨大数除法运算，减少巨大数乘法次数，但是我也只是空想而已。
（3）迭代终止条件。简单化的、固定的“迭代次数”是比较傻的，要么迭代不够，要么迭代过火，浪费算力。合适的终止条件需要把握迭代过程中“有效数字”增长的规律，也不知道有没有这样的规律，我是不知道的，便做了一个实践派，反正有诸路大神的代码结果做保证，便反复测试，加上平衡各种数的考虑，最终在代码中选用的是64%精度。也即：假设迭代一次的值x1的小数部分位数的前64%是精确的，后面36%是近似的，将后面的截掉，从而避免小数部分位数增长过快，在较少的迭代次数下提前退出，精度严重不够的情况发生。这是我对我的开方算法保有一些“谨慎态度”的根本原因。不过，在发帖的今天，我的开方算法还是经受住了我的各种检验和对比的。
头都大了。只为了兴趣，发帖也是为了借用EH归类整理一下自己的东西。有想到不一样的了，后面再说吧。
附件如下：
HugeNumberOperation_by aoe1981.zip
(100.4 KB, 下载次数: 87)
（2022.02.16对上面附件作了更新，修复了对“4”这样的完全平方数开方运行出错的问题，原因是第一次的初值x0已经是准确值了，后续x1根本不会产生新的迭代变化，导致程序无法退出，陷入死循环。另外，测试出了程序的一个小问题吧，比如构造一个数：2^6=729，这个数在整数范围内既可以开平方（27），也可以开立方（9），用上面附件得出的结果却是：26.9999999……、8.999999……。本想修复，但这并不是程序的错误，而是在算法中采用了“优化迭代关系式”所产生的副作用。因为所谓“优化”，其实是为了避免迭代过程中产生巨大数除法或者减少巨大数乘法而事先将初值x0求其倒数，这样一来，对于有些数，原本是准确数的，变成了近似数。想了想，就不更改了。TKCB的“大数计算器”不存在这个问题。）
|
评分
-
7
查看全部评分
-
|
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2022-2-14 00:17
楼主
